¿Qué algoritmo puedo usar para encontrar la ruta más corta entre tipos de nodos especificados en un gráfico?

Question

Este es el problema:

Tengo n puntos (p1, p2, p3, .. pn), cada uno de ellos se puede conectar a cualquier otro con un costo x determinado.

Cada punto pertenece a uno de un conjunto de tipos de puntos (por ejemplo, "A" "B" "C" "D" ...).

La entrada del método es la ruta que quiero seguir, por ejemplo "A-B-C-A-D-B".

La salida es la ruta más corta que conecta los puntos del tipo I give in input, por ejemplo "p1-p4-p32-p83-p43-p12" donde p1 es un tipo A, p4 un tipo B, p32 un tipo C, p83 un tipo A, p43 un tipo D y p12 un tipo B.

La solución "fácil" consiste en calcular TODAS las rutas posibles pero el costo computacional es muy alto.

¿Alguien puede encontrar un mejor algoritmo?

Como dije en el título, ¡no sé si existe!

Actualización:

El punto clave que me impide el uso de Dijkstra y los otros algoritmos similares es que tengo para enlazar los puntos según el tipo.

Como entrada tengo una variedad de tipos y tengo que enlazar en ese orden.

Esta es una imagen de Kent Fredric (muchas gracias) que describe la situación inicial (en enlaces rojos permitidos)!

alt text http://img13.imageshack.us/img13/3856/immagineaol.jpg

Un ejemplo de la vida real:

Un hombre quiere visitar una iglesia en la mañana, ir al restaurante y, finalmente, visitar un museo por la tarde.

En el mapa hay 6 iglesias, 30 restaurantes y 4 museos.

Quiere que la distancia church-rest-museum sea la mínima posible.

Answer 1

Hay muchos algoritmos que harán mejor que calcular todas las rutas posibles. Breadth-first search es el punto de partida básico para la familia de algoritmos que tengo en mente, Best-first search es apropiado porque tiene los costos de vértice definidos, y si puede obtener más información sobre su espacio problemático, puede usar A* o Dijkstra's algorithm. (En cada caso, encontrar las rutas desde el conjunto de nodos iniciales permitidos).

Vuelva a editar: la restricción de ruta (la matriz de tipos de nodos que necesita satisfacer) no le impide trabajar con estos algoritmos; todo lo contrario, les ayuda a todos a funcionar mejor. Solo necesita implementarlos de una manera que permita la incorporación de la restricción de ruta, limitando los vértices disponibles en cada paso de la búsqueda a aquellos que son válidos dada la restricción.

Answer 2

Por lo que entiendo su pregunta, necesita un camino más corto en un gráfico dirigido. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm debería darle una idea.

respecto, Jan

Answer 3

1. calcular todos los pares de trayectorias más cortas dentro de cada bloque de equivalencia.
2. Ahora construya un gráfico que NO tenga bordes entre clases, pero cuyos bordes entre las clases coincidan con la ruta más corta dentro de esa clase, lo que lleva al nodo específico de otra clase.

Espero que esto esté claro.

Esta solución no es particularmente eficiente, pero claramente polinómica.

Answer 4

Puede usar el algoritmo de Floyd-Warshall. Aquí está el pseudocódigo dada por Wikipedia:

/* Assume a function edgeCost(i,j) which returns the cost of the edge from i to 
    (infinity if there is none). 
    Also assume that n is the number of vertices and edgeCost(i,i)=0 
*/ 

int path[][]; 

/* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path 
    from i to j using intermediate vertices (1..k-1). Each path[i][j] is initialized to 
    edgeCost(i,j) or infinity if there is no edge between i and j. 
*/ 

procedure FloydWarshall() 
    for k: = 1 to n 
     for each (i,j) in {1,..,n}2 
      path[i][j] = min (path[i][j], path[i][k]+path[k][j]); 

que tenía que escribir un programa para un curso de algoritmos sobre este mismo problema. ¡Este algoritmo funcionó como un encanto! Buena suerte.

Answer 5

Al revisar su pregunta, parece que pide un nodo por letra, en ese caso es una solución de programación dinámica simple: calcule todos los caminos más cortos de longitud 1, que satisfacen el comienzo de su secuencia, entre cada par de nodos. Luego, teniendo para k todos estos caminos para todos los pares de nodos, es trivial construir para k + 1.

Answer 6

Como mencionó Jan, solo necesita un algoritmo de ruta más corto aburrido normal (como el algoritmo de Dijkstra o Floyd's); sin embargo, debe transformar su gráfica de entrada para que la ruta de salida respete su restricción de ruta.

dieron una restricción camino de: A - B - A

Crear un nuevo gráfico G e insertar todos los vértices de A en G con nuevos sellos como a_01. Luego inserte todos los vértices desde B en G y conecte los vértices A con los vértices B (los bordes deben dirigirse hacia los nodos recién insertados) y copie los costos del gráfico original. A continuación, repita este paso con A (y cualquier otro componente de ruta) conectando los vértices recién insertados a los que están en B. Por lo tanto, crea un gráfico donde solo las rutas que existen satisfacen la restricción de ruta. Puede usar algoritmos de ruta más cortos normales.

La idea clave es que cuando vuelves a visitar una clase, en realidad estás visitando un conjunto distinto de nodos y solo quieres bordes que conecten clases de nodos adyacentes.

Answer 7

Es así como actualmente interpreto su problema.

Las flechas rojas me permiten rastrear manualmente las rutas que se ajustan a la restricción de ordenamiento dada.

No se incluyen los costos, pero se supone que todos los enlaces tienen un costo, y los costos del enlace son diferentes.

Si esto describe con precisión el escenario que está tratando de resolver, dígalo para que otros puedan responder mejor a la pregunta.

Answer 8

Aquí es pseudocódigo con una solución de programación dinámica:

n - length of desired path 
m - number of vertices 
types[n] // desired type of ith node 
vertice_types[m] 
d[n][m] // our DP tab initially filled with infinities 

d[0][0..m] = 0 
for length from 1 to n 
    for b from 0 to m 
    if types[length] == vertice_types[b] 
     for a from 0 to m 
     if types[length-1] == vertice_types[a] 
      d[length][b] = min(d[length][b], d[length-1][a] + cost(a,b)) 

su trayectoria mínima costo es mínimo (d [n] [0..m])

se puede reducir el tamaño de la tabla d a 2 filas, pero ofuscaría la solución