Ruta más corta de una vía a través de múltiples nodos

Question

Tengo una serie de coordenadas de gráfico y necesito encontrar la ruta de acceso unilateral más corta a través de todas ellas. No tengo un inicio/final predeterminados, pero cada punto solo debe tocarse una vez y NO es necesario regresar al origen óptimo.

He intentado un par de enfoques de TSP, pero todos parecen estar basados ​​en volver al origen al final, lo que da resultados terriblemente ineficientes en este caso.

Ejemplo

1, 13
3, 0
3, 7
2, 21
2, 11
3, 12
1, 19
3, 6

se resolvería a

3, 0
3, 6
3, 7
3, 12
2, 11
1, 13
1, 19
2, 21

Notas:

Sí Probé la búsqueda función, hay una pregunta básicamente idéntica Algorithm: shortest path between all points sin embargo, la única respuesta real es un TSP, que una vez más, el circuito cerrado es ineficaz para esto.

No tiene por qué ser fiable al 100%, ya tengo un método permutaciones pero su demasiado lento, lo que necesito para manejar por lo menos ~ 25-30 puntos, estableciéndose con una buena aproximación funciona para mí

Gracias por adelantado.

Editar para aclarar, TSP tiende a resolver como en img # 1, el resultado deseado es img # 2
img 3 es la muestra anterior resuelto a través de un TSP y img # 4 es la deseada (x coords cambió de nuevo - 0,5 para la visibilidad)

par más para una buena medida # 1 = TSP, # 2 = deseado

Básicamente quiero el más corto cadena que conecta n puntos, usando el punto inicial y final más eficiente

Answer 1

Esta es una instancia del all-pairs shortest path problem con todos los bordes teniendo peso = 1. Encontrará soluciones comunes como el algoritmo Dijkstra o A-star en la página vinculada.
Un enfoque ingenuo es iterar sobre los nodos y encontrar la ruta más corta a cada otro nodo.

$paths = array(); 
foreach ($nodes as $start) { 
    foreach ($nodes as $end) { 
     if ($start !== $end) { 
      $path[$start][$end] = findShortestPath($graph, $start, $end); 
     } 
    } 
} 

En un enfoque más sofisticado findShortestPath recordaría subtrazados de ejecuciones anteriores (o utilizar $paths para ese propósito) para obtener un mejor rendimiento.

Answer 2

Como no le interesa encontrar un circuito cerrado, todo lo que necesita es una única ruta, puede hacer una pequeña modificación en los puntos para evitar el costo de un ciclo cerrado. Para hacer esto, agregue un nuevo punto, llámelo v, que defina para estar a la distancia 0 de todos los otros puntos. Ahora, encuentre una solución TSP para este gráfico. En algún momento, ingresará y luego saldrá de v. Si toma el ciclo y luego elimina los bordes dentro y fuera de v de él, entonces tendrá una ruta que visita cada nodo exactamente una vez sin ningún ciclo.

Esto todavía requiere que resuelva o aproxime TSP, pero elimina la enorme sobrecarga de volver a su punto de inicio.

Answer 3

hay muchos algoritmos que buscan la ruta cerrada más corta en un gráfico. Creo que no es demasiado difícil adaptar uno de los algoritmos que resuelven ese problema (a.k.a como travelling salesman problem) a sus necesidades (la ruta debe ser una vía hamiltoniana, no un ciclo hamiltoniano). Algunas de las soluciones conocidas para el problema del vendedor son el algoritmo de Dijkstra y el algoritmo de Prim.