Grafos Arboles

PREGUNTAS

1. ¿Problema del camino más corto?

2. ¿Problema de Flujo Máximo?

3. ¿Planeación de Proyectos (PERT/CPM)?

4. ¿Problema de Flujo Costo Mínimo?

Adicional

 ¿Problema del Agente Viajero?

1. PROBLEMA DEL CAMINO MAS CORTO

El problema que consiste en encontrar un camino entre dos vértices (o nodos) de tal manera que la suma de los pesos de las aristas que lo constituyen es mínimo. Un ejemplo es encontrar el camino más rápido para ir de una ciudad a otra en un mapa. En este caso, los vértices representan las ciudades, y las aristas las carreteras que las unen, cuya ponderación viene dada por el tiempo que se emplea en atravesarlas.

Considere una red conexa y no dirigida con dos nodos especiales llamados origen y destino. A cada ligadura (arco no dirigido) se asocia una distancia no negativa. El objetivo es encontrar la ruta más corta (la trayectoria con la mínima distancia total) del origen al destino.

Ejemplo:

Se dispone de un algoritmo bastante sencillo para este problema. La esencia del procedimiento es que analiza toda la red a partir del origen; identifica de manera sucesiva la ruta más corta a cada uno de los nodos en orden ascendente de sus distancias (más cortas), desde el origen; el problema queda resuelto en el momento de llegar al nodo destino.

ALGORITMO DE LA RUTA MÁS CORTA

 Objetivo de la n-ésima iteración: encontrar el n-ésimo nodo más cercano al origen. (Este paso se repetirá para n=1,2,… hasta que el n-ésimo nodo más cercano sea el nodo destino.)

 Datos para la n-ésima iteración: n-1 nodos más cercanos al origen (encontrados en las iteraciones previas), incluida su ruta más corta y la distancia desde el origen. (Estos nodos y el origen se llaman nodos resueltos, el resto son nodos no resueltos.)

 Candidatos para el n-ésimo nodo más cercano: Cada nodo resuelto que tiene conexión directa por una ligadura con uno o más nodos no resueltos proporciona un candidato, y éste es el nodo no resuelto que tiene la ligadura más corta. (Los empates proporcionan candidatos adicionales.)

 Cálculo del n-ésimo nodo más cercano: para cada nodo resuelto y sus candidatos, se suma la distancia entre ellos y la distancia de la ruta más corta desde el origen a este nodo resuelto. El candidato con la distancia total más pequeña es el n-ésimo nodo más cercano (los empates proporcionan nodos resueltos adicionales), y su ruta más corta es la que genera esta distancia.

Aplicaciones

Los algoritmos de los caminos más cortos se aplican para encontrar direcciones de forma automática entre localizaciones físicas, tales como direcciones en mapas callejeros.

Si un algoritmo representa una máquina abstracta no determinista como un grafo, donde los vértices describen estados, y las aristas posibles transiciones, el algoritmo de los caminos más cortos se usa para encontrar una secuencia óptima de opciones para llegar a un cierto estado final o para establecer límites más bajos en el tiempo, necesario para alcanzar un estado dado. Por ejemplo, si los vértices representan los estados de un puzzle como el Cubo de Rubik, cada arista dirigida corresponde a un simple movimiento o giro. El algoritmo de los caminos más cortos se usa para encontrar la solución que utiliza el mínimo número posible de movimientos.

Generalización:

 El problema de los caminos más cortos desde un origen en el cual tenemos que encontrar los caminos más cortos de un vértice origen v a todos los demás vértices del grafo.

 El problema de los caminos más cortos con un destino en el cual tenemos que encontrar los caminos más cortos desde todos los vértices del grafo a un único vértice destino, esto puede ser reducido al problema anterior invirtiendo el orden.

 El problema de los caminos más cortos entre todos los pares de vértices, el cual tenemos que encontrar los caminos más cortos entre cada par de vértices (v, v') en el grafo.

Ejemplo

Una persona tiene que desplazarse a diario de un pueblo 1 a otro 7. Está estudiando cual es el trayecto más corto usando un mapa de carreteras. Las carreteras y sus distancias están representadas en la figura siguiente:

Se determinan las variables de decisión, en este caso:

• Xij: acción de desplazarse del pueblo i al j (0 indica que no hay desplazamiento y 1 que sí hay desplazamiento)

Se determinan las restricciones y se expresan como ecuaciones o inecuaciones de las variables de decisión. Dichas restricciones se deducen del balance entre los posibles caminos que parten desde cada pueblo y los que llegan hasta él (obviando los caminos que nos devuelvan al punto de partida y los que provengan del punto de destino):

 Balance de caminos del pueblo 1: X12 + X13 = 1

 Balance de caminos del pueblo 2: X24 + X25 – X12 – X42 – X52 = 0

 Balance de caminos del pueblo 3: X34 + X36 – X13 – X43 – X63 = 0

 Balance de caminos del pueblo 4: X42 + X43 + X45 – X24 – X34 – X54 = 0

 Balance de caminos del pueblo 5: X52 + X54 + X57 – X25 – X45 =

 Balance de caminos del pueblo 6: X63 + X67 – X36 = 0

 Balance de caminos del pueblo 7: – X57 – X67 = -1

 Se expresan todas las condiciones implícitamente establecidas por la naturaleza de las variables: que no puedan ser negativas, que sean enteras, que solo puedan tomar determinados valores,

En este caso las restricciones son que las variables deben ser booleanas (0 no se toma el camino, 1 se toma), y por lo tanto no pueden ser negativas:

 Xij ≥ 0

 Xij es booleano

Se determina la función objetivo:

Minimizar

...