¿Cuál es la longitud esperada del camino hamiltoniano más corto en puntos seleccionados al azar de una cuadrícula plana?

puntos distintos se seleccionan aleatoriamente de unacuadrícula . (Obviamente, y es un número constante dado.) Se construye un gráfico ponderado completo a partir de estos puntos de modo que el peso del borde entre el vértice y el vértice igual a la distancia de Manhattan de dos vértices en la cuadrícula original. $k$ $p\times q$ $k\leq p\times q$ $k$ $i$ $j$

Estoy buscando una forma eficiente de calcular la longitud esperada de la ruta hamiltoniana más corta (peso total mínimo) que pasa por estos nodos. Más precisamente, no se desean los siguientes enfoques ingenuos: $k$

Calcular la longitud de ruta exacta para todas las combinaciones de k nodos y derivar la longitud esperada. $\bullet$

Calcular la longitud aproximada de la ruta para todas las combinaciones de k nodos usando la heurística básica de usar un árbol de expansión mínimo que da hasta un 50% de error. (Una mejor heurística con menos error puede ser útil) $\bullet$

graph-theory co.combinatorics planar-graphs hamiltonian-paths Javad
fuente

Actualmente, no hay esperanza para un algoritmo eficiente ya que el problema de la ruta Hamiltoniana no ponderada en la cuadrícula plana es NP-completo.

Mohammad Al-Turkistany

Cuando habla del camino hamiltoniano, ¿está pensando en el camino hamiltoniano con el menor peso (también conocido como el problema del vendedor ambulante)?

a3nm

@ MohammadAl-Turkistany la dureza de HAM PATH no es necesariamente un obstáculo, ya que el OP simplemente es una estimación de puntos aleatorios.

Suresh Venkat

@ a3nm sí, y lo arreglé.

Suresh Venkat

¿Qué tiene de malo calcular la duración exacta del recorrido para muchas muestras aleatorias de

puntos y encontrar la expectativa y la desviación estándar? ¿Qué tan grande necesitas

para ser?

k

$k$

k, p, q

$k, p, q$

Peter Shor

Respuestas:

Suponiendo que y son bastante grandes, uno esperaría que la longitud esperada sobre todo dependería de la densidad, con algún término de corrección en función del perímetro. Por lo tanto, en primer orden, sería una función de la siguiente forma. $p$ $q$

L \approx (p q k)^{1 / 2} f (k / p q) + (p + q) g (k / p q) .

$L \approx (pqk)^{1/2} f(k/pq) + (p+q) g(k/pq).$

Ahora, podría usar experimentos en problemas de menor tamaño para descubrir qué son y . Primero, para estimar , desea hacer experimentos en una muestra sin límite: la forma más fácil de hacerlo es usar una cuadrícula con el lado izquierdo conectado a la derecha y la parte superior a la inferior, formando un toro . Para estimar , puede usar experimentos en una cuadrícula . $f$ $g$ $f$ $p\times p$ $g$ $p \times q$

Para la estimación, debe resolver (exactamente o aproximadamente) TSP relativamente grandes, ya que cuanto más grandes sean los que usa para la estimación, mejores serán sus resultados. Puede usar heurísticas que se encuentran dentro de un pequeño porcentaje o el código TSP exacto. Vea aquí algunas buenas heurísticas. El solucionador de TSP Concorde de Bill Cook encontrará el óptimo exacto para instancias razonablemente grandes (es el mejor código TSP disponible), y puede usarse sin cargo para la investigación académica.

Peter Shor
fuente

E [L]

$E[L]$

(k - 1) / k

$(k-1)/k$

E [L]

$E[L]$

L

$L$

L

$L$

E [L]

$E[L]$

k

$k$

E [L]

$E[L]$

k^{2}

$k^2$

k^{2} / (p q)

$k^2/(pq)$

p

$p$

q

$q$

k^{2}

$k^2$

p \times q

$p\times q$

p \times q

$p \times q$

θ (\sqrt{p q / k})

$\theta(\sqrt{pq/k})$

k

$k$

f

$f$

\sqrt{p q k} f (k / p q)

$\sqrt{pqk} f(k/pq)$

k \approx 10^{6}

$k \approx 10^6$