Jaka jest oczekiwana długość najkrótszej ścieżki hamiltonowskiej w losowo wybranych punktach z siatki planarnej?

$k$ różnych punktów wybiera się losowo z siatki . (Oczywiście i jest daną stałą liczbą.) Na podstawie tych punktów budowany jest kompletny wykres ważony, tak że ciężar krawędzi między wierzchołkiem a wierzchołkiem jest równy odległości Manhattanu dwóch wierzchołków na pierwotnej siatce . $p\times q$ $k\leq p\times q$ $k$ $i$ $j$

Szukam skuteczny sposób obliczyć oczekiwaną długość najkrótszego (minimalnej masie całkowitej) Hamiltonian ścieżki przechodzącej przez te węzłów. Mówiąc dokładniej, następujące naiwne podejścia nie są pożądane: $k$

$\bullet$ Obliczenie dokładnej długości ścieżki dla wszystkich kombinacji k węzłów i wyprowadzenie oczekiwanej długości.

$\bullet$ Obliczanie przybliżonej długości ścieżki dla wszystkich kombinacji węzłów k przy użyciu podstawowej heurystyki użycia minimalnego drzewa opinającego, co daje błąd do 50%. (Pomocna może być lepsza heurystyka z mniejszym błędem)

— Javad
źródło

Obecnie nie ma nadziei na efektywny algorytm, ponieważ nieważony problem ścieżki hamiltonowskiej na siatce planarnej jest NP-kompletny.

— Mohammad Al-Turkistany

Kiedy mówisz o ścieżce hamiltonowskiej, czy myślisz o ścieżce hamiltonowskiej o najmniejszej wadze (czyli problem sprzedawcy podróżującego)?

— a3nm

@ MohammadAl-Turkistany twardość ŚCIEŻKI HAM niekoniecznie stanowi przeszkodę, ponieważ PO jest jedynie oszacowaniem losowych punktów.

— Suresh Venkat

@ a3nm tak i naprawiłem to.

— Suresh Venkat

Co jest złego w obliczeniu dokładnej długości trasy dla wielu losowych próbek punktów i znalezieniu oczekiwań i odchylenia standardowego? Jak duże potrzebujesz ?

k

$k$

k, p, q

$k, p, q$

— Peter Shor,

Zakładając, że i są dość duże, można oczekiwać, że oczekiwana długość będzie zależeć głównie od gęstości, a pewien składnik korekcyjny będzie zależał od obwodu. Tak więc, w pierwszej kolejności, będzie funkcją następującej formy. $p$ $q$

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

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

Teraz można korzystać z doświadczeń na temat problemów mniejszych rozmiarach, aby dowiedzieć się, co i są. Po pierwsze, aby oszacować , chcesz przeprowadzić eksperymenty na próbce bez granicy: najłatwiejszym sposobem na to jest użycie siatki z lewą stroną podłączoną po prawej stronie i od góry do dołu, tworząc torus. Aby oszacować , możesz użyć eksperymentów na siatce . $f$ $g$ $f$ $p\times p$ $g$ $p \times q$

Do oszacowania musisz rozwiązać (dokładnie lub w przybliżeniu) stosunkowo duże TSP, ponieważ im większe stosujesz do oszacowania, tym lepsze będą twoje wyniki. Możesz użyć heurystyki w zakresie kilku procent lub dokładnego kodu TSP. Zobacz tutaj kilka dobrych heurystyk. Solver Concorde TSP Billa Cooka znajdzie dokładne optymalne rozwiązanie dla stosunkowo dużych instancji (jest to najlepszy dostępny kod TSP) i może być używany bezpłatnie do badań akademickich.

— Peter Shor
źródło

Używając terminologii z TSPLIB , szukałem SOP, a nie TSP. Mnożenie

E [L]

$E[L]$ obliczone dla TSP przez daje górną granicę dla SOP. Niestety, solver Concorde TSP nie obsługuje SOP i nie mogłem znaleźć żadnego solvera SOP online.

(k - 1) / k

$(k-1)/k$

— Javad

Myślę, że do obliczenia przypadki, które mają większe i mniejsze są równomiernie rozmieszczone wokół , więc można wymyślić konstruktywne podejście do znalezienia układu punktów na siatce co (może w przybliżeniu) daje . Znalezienie takiego układu znacznie zmniejszyłoby koszty obliczeń.

E [L]

$E[L]$

L

$L$

L

$L$

E [L]

$E[L]$

k

$k$

E [L]

$E[L]$

— Javad,

Nie do końca też zrozumiałem przyczynę współczynnika . Dlaczego nie powinien to być ? Jak zmienia się ta formuła aproksymacji dla mniejszych wartości i ?

k^{2}

$k^2$

k^{2} / (p q)

$k^2/(pq)$

p

$p$

q

$q$

— Javad

@Javad: Dobre pytanie. Myliłem się, bo jakoś myślałem

k^{2}

$k^2$ wskazuje, kiedy napisałem swoją odpowiedź. Współczynnik pochodzi z mojego założenia, że

p \times q

$p\times q$ Siatka ma krawędzie długości jednostki, więc cały region ma rozmiar

p \times q

$p \times q$ . Średnia krawędź powinna mieć długość

θ (\sqrt{p q / k})

$\theta(\sqrt{pq/k})$ , i jest krawędzi, więc jeśli chcesz, aby pozostało mniej więcej stałe, pierwszym terminem powinno być .

k

$k$

f

$f$

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

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

— Peter Shor

Dla

k \approx 10^{6}

$k \approx 10^6$ , różnica między długością TSP a długością SOP powinna być prawie nieistotna.

— Peter Shor