Pregunta acerca de la trayectoria de indagación

Question

Es posible encontrar la ruta más corta gracias a los algoritmos como Un*, pan de búsqueda en primer lugar, la profundidad de la primera búsqueda, etc..

¿Hay algún algoritmo conocido para averiguar cuántas rutas están disponibles si hay más de 1 solución óptima (por ejemplo las rutas con el mismo costo) o ninguna solución en absoluto.

Estoy trabajando en algunos algoritmos de gráfico, pero creo que no estoy en la dirección correcta. Cualquier consejos?

Answer 1

Una manera de representar un uniforme costo gráfica es con una matriz de adyacencia $A$ donde $A_{i,j}$ es 1 si existe una arista del vértice $i$ $j$y 0 si no la hay. ($A$ es simétrica para un grafo no dirigido)

El entero de la matriz de potencia $A^n$ tiene una casa en propiedad. $(A^n)_{i,j}$ cuenta el número de longitud-$n$ rutas desde el vértice $i$ hasta el vértice $j$. Para $n=1$, puede ver que esta es la definición de la matriz de adyacencia.

Si el borde de los costos son todos los enteros pesos (o racional), a continuación, puede asignar que la gráfica de un sistema de costo gráfico y preservar las rutas óptimas. A continuación, puede aumentar $n$ hasta $(A^n)_{i,j}$ es distinto de cero para los vértices de interés. Que voy a contar el número de rutas óptimas.

No sé el análisis de la complejidad de este, pero no suena muy prometedor.

Answer 2

Supongo que determinar el número de rutas es indecidible, porque puede haber un número infinito de soluciones óptimas (o puede haber al menos una solución óptima que es infinitamente profundo en el árbol de búsqueda).

Con eso dicho, hay maneras simples para enumerar todas las soluciones óptimas.

Si Un* se utiliza con un trámite y la heurística consistente, entonces A* se garantiza expanda los nodos no-orden decreciente de ruta de costo + heurística costo (es decir, Un*'s "$f$" de la función). Tenga en cuenta que todas las soluciones óptimas tendrá el mismo $f$-costo. Por lo tanto, para enumerar todas las soluciones óptimas, basta con ejecutar A* hasta que un objetivo de estado se encuentra (como de costumbre). A continuación, continuar ejecutando Un*, grabación o cualquier objetivo adicional-estados que encuentre, hasta que ésta se expande un nodo con un mayor $f$-costo (punto en el que sabemos que todas las soluciones óptimas se han encontrado).