Se necesita un algoritmo eficiente para visitar todos los nodos de un grafo, se permite volver a visitar aristas y nodos

Question

Actualización:

Esta es mi solución con el Algoritmo de Kruskal, aunque no tiene en cuenta el "camino" real. La fuerza bruta puede ser la única solución.

http://www.youtube.com/watch?v=VbSwwos4R2E

Hola, quiero saber si existe un algoritmo que me permita visitar todos los nodos de un grafo, revisitando permitido, cada nodo puede tener hasta 4 nodos enlazados.

He subido el dibujo del gráfico como ejemplo. En ese ejemplo, una buena ruta sería:

A - B - C - D - E - F - G - H - I - J - K - L - H - I - M

Suma de pesos:

11 + 3 + 1 + 7 + 10 + 7 + 3 + 2 + 2 + 4 + 4 + 4 + 2 + 1 = 61

Pero otra vía, con menos peso, sería:

A - B - C - D - E - F - G - H - I - M - I - H - L - K - J

Pesos:

11 + 3 + 1 + 7 + 10 + 7 + 3 + 2 + 1 + 1 + 2 + 4 + 4 + 4 = 60

Por supuesto, quiero conseguir el camino con menos peso. Se permite la revisión porque de lo contrario no puedo visitar todos los nodos.

Yo mismo no soy un matemático, así que se agradecería una charla fácil. Estoy familiarizado con algoritmos como A* y Dijkstra, que son útiles cuando tengo un objetivo que buscar, pero en este caso no estoy buscando un objetivo en particular.

Gracias.

Answer 1

Un problema muy similar es el Problema de inspección de rutas (también conocido como el "problema del cartero chino"). Ese problema es exactamente igual que el suyo, salvo que hay que visitar cada borde en lugar de cada nodo según sus necesidades.

Sospecho que su variante es NP-Dura.

Estrictamente hablando, sólo has preguntado si "hay un algoritmo" para tu problema; sin duda lo hay: probar todas las soluciones y tomar la mejor. Como hay un número finito de candidatos, esto es un algoritmo.

Si quiere un eficiente algoritmo, voy a suponer que no encontrará ninguno. Sin embargo, me encantaría que se demostrara que estoy equivocado.

Answer 2

Parece que quieres generar un árbol de expansión del grafo, lo que se suele hacer con una búsqueda de profundidad o de amplitud. Wikipedia tiene una breve discusión de las posibilidades si quieres paralelizar las cosas.

Añadiendo la consideración de los pesos, lo que se quiere es un mínimo spanning tree, para los algoritmos, véase, de nuevo, wikipedia .

Editar: Como un buen comentario señala, el problema no es, dado por la búsqueda de un árbol de extensión mínima. Sin embargo, podría ser una forma razonable de obtener una solución pasable.

Answer 3

Me parece que es una variante del Problema del Vendedor Viajero. No deberías tener problemas para encontrar literatura sobre este problema. Se sabe que la versión estándar es NP-dura, lo que implica que nadie conoce un buen algoritmo para resolverlo en general (aunque hay muy buenos algoritmos para instancias pequeñas, y muy buenos algoritmos para encontrar soluciones aproximadas). Su restricción de que cada nodo tenga un grado máximo de 4 puede facilitar el problema (pero lo dudo).

Answer 4

Tal vez le interese el debate aquí: https://stackoverflow.com/questions/5280594/travelling-salesman-with-repeat-nodes-dynamic-weights Quizás también haya ideas de interés para usted en el libro: The Vehicle Routing Problem, ed. Toth y Vigo, SIAM, 2002.