Clase 6c - Programacion Dinamica - Grafos

SAVE OFFLINE

Programación Dinámica Características La programación dinámica es una técnica matemática útil para la toma de decisiones secuenciales interrelacionadas. Proporciona un procedimiento sistemático para determinar la combinación óptima de decisiones. En contraste con la programación lineal, no cuenta con una formulación matemática estándar, sino que se trata de un enfoque de tipo general para solucionar problemas; además, las ecuaciones específicas que se usan deben ajustarse a la situación particular. Está basada en el principio de optimalidad de Bellman : “Cualquier subsecuencia de decisiones de una secuencia óptima de decisiones que resuelve un problema también debe ser óptima respecto al subproblema que resuelve.” Otra manera de expresar su principio es : 'Una política es óptima si en un periodo dado, cualquiera sean las decisiones precedentes, las decisiones que queden por tomar constituyen una política óptima teniendo en cuenta los resultados precedentes. Es decir se opera por fases o secuencias. Observaciones: • Técnica cuantitativa de toma de decisiones desarrollada por Bellman y Dantzig en 1957 • Se basa en una estructura de optimalidad que considera que una política óptima consiste de subpolíticas óptimas. (Recursividad). • Técnica matemática que resuelve una serie de decisiones secuenciales, cada una de las cuales afecta las decisiones futura. Supongamos que un problema se resuelve tras tomar un secuencia d1 , d2 , …, dn de decisiones. Si hay d opciones posibles para cada una de las decisiones, una técnica de fuerza bruta exploraría un total de dn secuencias posibles de decisiones. La técnica de programación dinámica evita explorar todas las secuencias posibles por medio de la resolución de subproblemas de tamaño creciente y almacenamiento en una tabla de las soluciones óptimas de esos subproblemas para facilitar la solución de los problemas más grandes. Los subproblemas se resuelven a su vez dividiéndolos en subproblemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial. Las características básicas que distinguen a los problemas de programación dinámica son 1. El problema se puede dividir en etapas, cada una de las cuales requiere de una política de decisión. 2. Cada etapa tiene cierto número de estados asociados con su inicio. 3. El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con el inicio de la siguiente etapa. 4. El procedimiento de solución está diseñado para encontrar una política óptima para manejar el problema completo, es decir, una receta para elaborar la política de decisión óptima para cada etapa en cada uno de los estados posibles. 5. Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores. Por tanto, la decisión inmediata óptima depende sólo del estado actual y no de cómo se llegó ahí. Éste es el principio de optimalidad de la programación dinámica 6. El procedimiento de solución comienza cuando se determina la política óptima para la última etapa. la política óptima para la última etapa prescribe la política óptima de decisión para cada estado posible en esa etapa. Es común que la decisión de este problema de una etapa sea trivial.

7. Se dispone de una relación recursiva que identifica la política óptima para la etapa n, dada la política óptima para la etapa (n+ 1)

Grafos Los grafos, resultan ser extremadamente útiles para analizar problemas muy diversos como Construcción de redes: tenemos una serie de ciudades que queremos conectar mediante un oleoducto; un estudio de ingeniería previo nos permite conocer el precio de cada conexión. Se trata de conectar todas las ciudades con el menor coste posible. Los grafos son, un lenguaje, una notación, que permite representar relaciones binarias, es decir, entre pares de objetos en un conjunto. De una manera informal, podríamos decir que un grafo es una colección de vértices y de aristas que unen estos vértices. Los vértices los dibujaremos como puntos del plano, y las aristas serán líneas que unen estos puntos. Vayamos con las definiciones formales: Definición Un grafo G es un conjunto no vacío V (de vértices) llamados nodos y un conjunto A que son las aristas (caso de grafos no orientados) o arcos (caso de grafos orientados) extraído de la colección de subconjuntos de dos elementos de V. Para ser precisos, deberíamos decir que esta definición se refiere a lo que se conoce como un grafo simple y sin lazos. Mientras no se diga lo contrario, cuando hablemos de un grafo siempre estaremos refiriéndonos a este caso sencillo. Por supuesto, diremos que dos grafos son iguales si tienen el mismo conjunto de vértices y la misma colección de aristas. Nombraremos un grafo G mediante G=(V,A). Vértices Conectados: dos vértices de un grafo se dice que están conectados Cuando existe una arista entre ambos;

a

b

Una arista de G es, pues, un subconjunto :{a, b}, con a, b ∈ V, a distinto de b En el caso de grafo orientado será: el arco que va del vértice a al vértice b ;

a

b

Donde el vértice a es el extremo inicial y el vértice b es el extremo final. Un arco de G se expresa como el par ordenado (a,b) Para grafos NO ORIENTADOS : Cadena : Es una sucesión de aristas de G, tal que cada arista de la secuencia tiene exactamente un vértice en común con la arista anterior.

Ejemplo: cadena

Ʋ=

{1, 3} , {4, 3} , {4, 5}

Largo de una cadena: es el número de aristas de la secuencia. Cadena elemental: es aquella que no repite vértices. Cadena simple: es aquella que no repite aristas. Ciclo : es una cadena que vincula un nodo con sigo mismo ejemplo ciclo: ß = {1, 3} , {4, 3} , {4, 5} , {5, 1} Ciclo elemental, es un ciclo donde no se repite ningún vértice (salvo el primer o que coincide con el último) Para grafos ORIENTADOS :

Ruta o camino : es una sucesión de arcos en la cual el nodo final de cada arco es igual al inicial del siguiente. Ejemplo: camino: Ɛ= (1,3), (3,4), (4,2) esta secuencia de arcos representa un camino para viajar del nodo 1 al nodo 2. Circuito : es un camino (ruta) cerrada, es decir el nodo inicial coincide con el nodo final. Ejemplo: en la red anterior, un circuito es ρ = (1,4), (4,2), (2,1). La siguiente red no tiene circuito.

Ejemplo 1 Consideremos un conjunto de vértices V = {1,2,3}. Construyamos algunos grafos distintos con ese conjunto de vértices. De los dos grafos dibujados surgen la siguiente forma de escribirlos G1 (V; A1) donde A1={ {1,2},{2,3} } y G2 (V; A2) donde A2 ={ {1,2} } G1

G2

1

2 3

1

2 3

En muchas ocasiones, conviene considerar grafos que están incluidos “dentro” de otros. Dado un grafo G=(V,A), formamos un subgrafo H=(V,A) de G seleccionando algunos de los vértices de G (esto es,V' ⊆ V). Y, de las aristas que unen vértices del conjunto V' en el grafo original G, nos quedamos con algunas de ellas (o todas) Grafo conexo; no-conexo

Un grafo se dice conexo si, para cualquier par de vértices 1 y 2 en G, existe al menos una cadena de 1 a 2.

Grafo Conexo, es aquel en el que, para cada par de vértices de G, existe una cadena que los une.

Un ejemplo cotidiano de un grafo conexo: seria el sistema de autopista y trasporte publico de la localidad. Existen Grafos que representan relaciones de equivalencias, ejemplo : la relación R: “estar conectado con” definida en el conjunto de sus vértices es una relación de equivalencia. Es decir es reflexiva, simétrica y transitiva. a) Reflexividad Sea u cualquiera vértice del conjunto. Entonces, la arista que conecta a u con u es, la arista : { {u,u} } es decir uRu Es decir, R es reflexiva. b) Simetría Sean u y v dos vértices cualquiera , Entonces si existe la arista o cadena que conecta los vértices u con v , la misma arista o cadena conecta el vértice v con el vértice u, entonces entonces podemos decir que si uRv entonces vRu Es decir, R es simétrica b) Transitividad Si u,v y w son tres vértices cuales quiera de el grafo G, entonces si existe la arista o cadena del vértice u al vértice v y también existe la arista o cadena de vértice v al vértice w, entonces existe la cadena del vértice u al vértice w. Bastaría, con unir las cadenas. Por lo tanto u R v ; v R w entonces uR w. Es decir, R es transitiva. En grafos orientados se definen 2 conceptos a) Débilmente conexo: si existe una cadena (sin tener en cuenta la orientación) que une cada par de nodos distintos. b)Fuertemente conexo: si para cada par ordenado de nodos x e y, existe un camino que va de x a y

Matrices asociadas a un grafo. Grado de un vértice Una forma muy útil de representar un grafo G=(V,A) es mediante su matriz de vecindades (o matriz de adyacencia). La idea, es formar una matriz de ceros y unos. Si el conjunto de vértices es V = {v1,...,vn}, el grafo se puede describir mediante una matriz n×n v1 v2 v3 …........ vn v1 1 v2 1 . . . vn 1

1 1

0 0

0 1

0

1

0