Uso de A * para resolver al Vendedor ambulante

Question

Se me ha encomendado la tarea de escribir una implementación del algoritmo A * (heurística provista) que resolverá el problema del vendedor ambulante. Entiendo el algoritmo, es bastante simple, pero simplemente no puedo ver el código que lo implementa. Quiero decir, lo entiendo Cola de prioridad para los nodos, ordenados por distancia + heurística (nodo), agregue el nodo más cercano a la ruta. La pregunta es, por ejemplo, ¿qué sucede si no se puede llegar al nodo más cercano desde el nodo más cercano anterior? ¿Cómo se puede tomar un "gráfico" como argumento de función? Simplemente no puedo ver cómo funciona realmente el algoritmo, como código.

Leí la página de Wikipedia antes de publicar la pregunta. Repetidamente. En realidad, no responde a la pregunta: la búsqueda del gráfico es muy diferente a la solución del TSP. Por ejemplo, podría construir un gráfico donde el nodo más corto en cualquier momento dado siempre da como resultado un retroceso, ya que dos rutas de la misma longitud no son iguales, mientras que si solo está tratando de pasar de A a B, entonces dos caminos de la misma longitud son iguales.

Puede obtener un gráfico por el cual nunca se alcanzan algunos nodos accediendo siempre al más cercano.

Realmente no veo cómo A * se aplica al TSP. Quiero decir, encontrar una ruta de A a B, claro, entiendo eso. Pero el TSP? No veo la conexión.

Answer 1

Para responder a una de sus preguntas ...

Para pasar un gráfico como un argumento de la función, tiene varias opciones. Puede pasar un puntero a una matriz que contiene todos los nodos. Podría pasar solo el nodo inicial y trabajar desde allí, si es un gráfico completamente conectado. Y, por último, podría escribir una clase de gráfico con cualquier estructura de datos que necesite dentro de ella, y pasarle una referencia a una instancia de esa clase.

En cuanto a su otra pregunta acerca de los nodos más cercanos, ¿no forma parte de la búsqueda A * que retrocederá según sea necesario? O podría implementar su propio tipo de retroceso para manejar ese tipo de situación.

Answer 2

Si solo se trata de un problema de comprensión del algoritmo y cómo funciona, es posible que desee considerar dibujar un gráfico en papel, asignarle pesos y dibujarlo. También es probable que pueda encontrar algunas animaciones que muestran el camino más corto de Dijkstra, Wikipedia tiene una buena. La única diferencia entre Dijkstra y A * es la adición de la heurística, y detiene la búsqueda tan pronto como llegue al nodo objetivo. En cuanto a usarlo para resolver el TSP, ¡buena suerte con eso!

Answer 3

Piense en esto un poco más abstracto. Olvídate de A * por un momento, es solo dijkstra con una heurística de todos modos. Antes, querías ir de A a B. ¿Cuál era tu objetivo? Para llegar a B. El objetivo era llegar a B con el menor costo. En cualquier punto dado, ¿cuál era su "estado" actual? Probablemente solo su ubicación en el gráfico.

Ahora, desea comenzar en A, luego vaya a B y C. ¿Cuál es su objetivo ahora? Para pasar B y C, manteniendo el menor costo. Puede generalizar esto con más nodos: D, E, F, ... o solo N nodos. Ahora, en cualquier punto dado, ¿cuál es su "estado" actual? Esto es fundamental: NO es solo su ubicación en el gráfico, sino también cuál de B o C o los nodos que ha visitado hasta el momento en la búsqueda.

Implemente su algoritmo original para que invoque alguna función que le pregunte si ha alcanzado "el estado objetivo" después de hacer que X se mueva. Antes, la función acababa de decir "sí, estás en el estado B, por lo tanto, estás en la meta". Pero ahora, deje que la función responda "sí, está en el estado de objetivo" si la ruta de búsqueda ha pasado por cada uno de los puntos de interés. Sabrá si la búsqueda ha pasado o no sobre todos los puntos de interés porque está incluida en el estado actual.

Después de eso, mejora la búsqueda con cierta heurística, y A * arriba.

Answer 4

he encontrado una solución here

Uso árbol de expansión mínima como un heurístico.

Conjunto Estado inicial: Agente en la ciudad de inicio y no ha visitado ninguna otra ciudad

Estado Objetivo: El agente le ha visitado todas las ciudades y llegaron a la ciudad de inicio de nuevo Función

Sucesor: Genera todas las ciudades que aún no ha visitado

Coste perimetral: distancia entre las ciudades representadas por los nodos, use este costo para calcular g (n).

h (n): distancia a la ciudad no visitada más cercana de la ciudad actual + distancia estimada para viajar a todas las ciudades no visitadas (heurística MST utilizada aquí) + distancia más cercana de una ciudad no visitada a la ciudad de inicio. Tenga en cuenta que esta es una función heurística admisible. Puede considerar mantener una lista de ciudades visitadas y una lista de ciudades no visitadas para facilitar los cálculos.

Answer 5

La pregunta es, como, ¿qué ocurre si no se puede acceder al nodo más cercano desde el nodo más cercano anterior?

Este paso no es necesario. Como en, no estás calculando un camino desde el anterior más cercano al más cercano, estás tratando de llegar a tu nodo objetivo, y lo más cercano es lo único que importa (por ejemplo, al algoritmo no le importa esa última iteración) estabas a 100 km de distancia, porque esta iteración estás a solo 96 km de distancia).

Como introducción general, A * no construye directamente una ruta: explora hasta que definitivamente sabe que la ruta está contenida dentro de la región que ha explorado, y luego construye la ruta en función de la información registrada durante la exploración .

(voy a utilizar the code in the Wikipedia article como una implementación de referencia para ayudar a mi explicación.)

usted tiene una de dos conjuntos de nodos: closedset y openset

closedset sostiene nodos que han sido evaluados por completo, es decir, usted sabe exactamente qué tan lejos están de start y todos sus vecinos están en uno de los dos conjuntos. No hay más cálculos que puedas hacer con ellos y podamos (más o menos) ignorarlos. (Básicamente estos están completamente contenidos dentro del borde.)

openset tiene nodos "fronterizos", usted sabe qué tan lejos están de start, pero todavía no ha tocado a sus vecinos, por lo que están al borde de su búsqueda hasta aquí.

(Implícitamente, hay un tercer grupo:. Nodos completamente intacta, pero que en realidad no tocarlos hasta que estén en openset por lo que no importan.)

En una iteración dada, si' Si tiene nodos que explorar (es decir, nodos en openset), necesita averiguar cuál explorar.Este es el trabajo de la heurística, básicamente le da una pista sobre qué punto en el borde será el mejor para explorar a continuación, diciéndole qué nodo cree que tendrá la ruta más corta a goal.

El nodo más cercano anterior es irrelevante, simplemente expandió el borde un poco, agregando nuevos nodos a openset. Estos nuevos nodos ahora son candidatos para el nodo más cercano en esta iteración.

Al principio, sólo se openset contiene start, pero entonces iterar y en cada paso de la frontera se expande un poco (en la dirección más prometedora), hasta que finalmente llegue a goal.

Cuando A * está realmente haciendo la exploración, no se preocupa de qué nodos vinieron de dónde. No es necesario, porque conoce su distancia desde start y la función heurística y eso es todo lo que necesita.

Sin embargo, para reconstruir la ruta más adelante, necesita tener algún registro de la ruta, esto es lo que camefrom es. Para un nodo determinado, camefrom lo vincula al nodo que está más cerca de start, por lo que puede reconstruir la ruta más corta siguiendo los enlaces hacia atrás desde goal.

¿Cómo se puede tomar un "gráfico" como argumento de función?

Al pasar uno de los representations of a graph.

Realmente no veo cómo A * se aplica al TSP. Quiero decir, encontrar una ruta de A a B, claro, entiendo eso. Pero el TSP? No veo la conexión.

Necesita una heurística diferente y una condición de finalización diferente: goal ya no es un nodo único, sino el estado de tener todo conectado; y su heurística es una estimación de la longitud de la ruta más corta que conecta los nodos restantes.

Answer 6

La confusión aquí es que el gráfico en el que usted está tratando de resolver el TSP es no la gráfica va a realizar una búsqueda A * sucesivamente.

Relacionados: Sudoku solving algorithm C++

para resolver este problema es necesario:

• Define tu:
  • TSP establece
  • estado inicial TSP
  • TSP estado objetivo (s)
  • Función sucesora de estado TSP Estado
  • TSP heurística
• Aplicar un genérico A * solucionador a este diagrama de estados TSP

Un ejemplo rápido que puedo pensar en:

• TSP afirma: lista de nodos (ciudades) actualmente en el ciclo de TSP
• Estado inicial de TSP: la lista que contiene un solo nodo, la ciudad de origen del vendedor ambulante
• Estado (s) de objetivo TSP: un estado es un objetivo si contiene todos los nodos en el gráfico de ciudades
• Función sucesora TSP: puede agregar cualquier nodo (ciudad) que no esté en el ciclo actual hasta el final de la lista de nodos en el ciclo para obtener un nuevo estado
  • el costo de la transición es igual al costo de la arista que está añadiendo al ciclo
• TSP heurística estado: usted decide