algorithm - Usando A*para resolver vendedor ambulante
a-star traveling-salesman (6)
La pregunta es, por ejemplo, ¿qué sucede si no se puede acceder al nodo más cercano desde el nodo más cercano anterior?
Este paso no es necesario. Al igual que en, no está calculando una ruta desde la anterior más cercana a la actual más cercana, está tratando de llegar a su nodo objetivo, y la actual más cercana es lo único que importa (por ejemplo, al algoritmo no le importa la última iteración) estaba a 100 km de distancia, porque esta iteración está a solo 96 km de distancia).
Como introducción general, A * no construye directamente una ruta: explora hasta que sabe definitivamente 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 usar el código del artículo de Wikipedia como implementación de referencia para ayudar a mi explicación).
Tienes dos conjuntos de nodos: closedset y openset
closedset contiene nodos que se han evaluado completamente, es decir, usted sabe exactamente qué tan lejos están del 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 así podemos (más o menos) ignorarlos. (Básicamente estos están completamente contenidos dentro de la frontera.)
openset tiene nodos de "borde", usted sabe qué tan lejos están de su start , pero aún no ha tocado a sus vecinos, por lo que están al borde de su búsqueda hasta el momento.
(Implícitamente, hay un tercer conjunto: nodos completamente intactos. Pero realmente no los tocas hasta que están en openset por lo que no importan).
En una iteración determinada, si tiene nodos para explorar (es decir, nodos en openset ), necesita averiguar cuál explorar. Este es el trabajo de la heurística, básicamente te da una pista sobre qué punto en el borde será el mejor para explorar a continuación y te dirá qué nodo cree que tendrá el camino más corto hacia la goal .
El nodo más cercano anterior es irrelevante, simplemente expandió el borde un poco, agregando nuevos nodos al conjunto openset . Estos nuevos nodos ahora son candidatos para el nodo más cercano en esta iteración.
Al principio, openset solo contiene start , pero luego se repite y en cada paso el borde se expande un poco (en la dirección más prometedora), hasta que finalmente se alcanza la goal .
Cuando A * está realizando la exploración, no se preocupa por qué nodos vinieron de dónde. No es necesario, porque conoce su distancia desde el 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 de lo que camefrom . Para un nodo determinado, camefrom enlaces al nodo que está más cerca de start , para que pueda reconstruir la ruta más corta siguiendo los enlaces hacia atrás desde la goal .
¿Cómo se toma realmente una "gráfica" como argumento de función?
Al pasar una de las representaciones de una gráfica .
Realmente no veo cómo se aplica A * al TSP. Quiero decir, encontrar una ruta de A a B, claro, lo entiendo. Pero el TSP? No veo la conexión.
Necesita una heurística diferente y una condición final diferente: el goal ya no es un solo nodo, sino el estado de tener todo conectado; y su heurística es una estimación de la longitud del camino más corto que conecta los nodos restantes.
Se me ha asignado la tarea de escribir una implementación del algoritmo A * (heurística proporcionada) 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, ordenada 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 acceder al nodo más cercano desde el nodo más cercano anterior? ¿Cómo se toma realmente una "gráfica" 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. Realmente no responde a la pregunta, buscar en la gráfica es muy diferente a resolver el TSP. Por ejemplo, podría construir un gráfico en el que el nodo más corto en un momento dado siempre resulte en un retroceso, ya que dos caminos de la misma longitud no son iguales, mientras que si solo intenta ir de A a B, entonces dos caminos de la misma longitud son iguales.
Podría derivar una gráfica por la cual nunca se llega a algunos nodos si siempre se aproxima más al primero.
Realmente no veo cómo se aplica A * al TSP. Quiero decir, encontrar una ruta de A a B, claro, lo entiendo. Pero el TSP? No veo la conexión.
Encontré una solución here
Utilice el árbol de expansión mínima como heurística.
Establezca el estado inicial: Agente en la ciudad de inicio y no ha visitado ninguna otra ciudad
Estado objetivo: el agente ha visitado todas las ciudades y ha vuelto a la ciudad de inicio
Función sucesora: Genera todas las ciudades que aún no han visitado.
Costo de borde: 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 desde la ciudad actual + distancia estimada para recorrer todas las ciudades no visitadas (heurística MST utilizada aquí) + la distancia más cercana desde 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.
La confusión aquí es que el gráfico en el que intenta resolver el TSP no es el gráfico en el que está realizando una búsqueda A *.
Ver relacionados: algoritmo de resolución de Sudoku C ++.
Para resolver este problema necesitas:
- Define tu
- Estados TSP
- Estado inicial de TSP
- Estado (s) objetivo (s) TSP
- Función sucesor del estado TSP
- TSP estado heurístico
- Aplique un solver A * genérico a este gráfico de estado TSP
Un ejemplo rápido que puedo pensar:
- Estados TSP: lista de nodos (ciudades) actualmente en el ciclo TSP
- Estado inicial de TSP: la lista que contiene un solo nodo, la ciudad natal del vendedor ambulante
- Estado (s) de objetivo de TSP: un estado es un objetivo si contiene todos los nodos en el gráfico de ciudades
- Función sucesora de TSP: puede agregar cualquier nodo (ciudad) que no esté en el ciclo actual al 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 ventaja que está agregando al ciclo
- TSP estado heurístico: tu decides
Para responder a una de tus preguntas ...
Para pasar una gráfica como un argumento de función, tiene varias opciones. Podría pasar un puntero a una matriz que contiene todos los nodos. Podría pasar solo un nodo de inicio y trabajar desde allí, si se trata de un gráfico totalmente conectado. Y finalmente, puede escribir una clase de gráfico con las estructuras de datos que necesite dentro y pasar una referencia a una instancia de esa clase.
En cuanto a su otra pregunta acerca de los nodos más cercanos, ¿no es parte de la búsqueda A * que retrocederá cuando sea necesario? O podría implementar su propio tipo de retroceso para manejar ese tipo de situación.
Piensa en esto un poco más abstracto. Olvídate de A * por un momento, es solo de 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 un momento dado, ¿cuál era su "estado" actual? Probablemente solo tu ubicación en el gráfico.
Ahora, quieres comenzar en A, luego ve a B y C. ¿Cuál es tu objetivo ahora? Pasar por encima de B y C, manteniendo el menor costo. Puede generalizar esto con más nodos: D, E, F, ... o solo Nodos. Ahora, en un punto dado, ¿cuál es su "estado" actual? Esto es crítico: NO ES solo su ubicación en el gráfico, también es cuál de B o C o los nodos que haya visitado hasta ahora en la búsqueda.
Implemente su algoritmo original para que llame a alguna función preguntando si ha alcanzado "el estado objetivo" después de hacer que X se mueva. Antes, la función simplemente habría dicho "sí, estás en el estado B, por lo tanto, estás en la meta". Pero ahora, deje que la función devuelva "sí, está en el estado 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 por todos los puntos de interés porque está incluido en el estado actual.
Después de obtener eso, mejora la búsqueda con un poco de heurística y A * it up.
Si es solo un problema de entender el algoritmo y cómo funciona, es posible que desee considerar dibujar un gráfico en un papel, asignarle un peso y dibujarlo. También es probable que encuentres algunas animaciones que muestren 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 usted detiene la búsqueda tan pronto como llega al nodo objetivo. En cuanto a usarlo para resolver el TSP, ¡buena suerte con eso!