Rozwiązywanie labiryntu z numerami

Mój 8-latek znudził się tworzeniem konwencjonalnych labiryntów i zaczął tworzyć warianty, które wyglądają tak:

Próbka lejka numerowego

Chodzi o to, aby zacząć od x i osiągnąć normalne zasady. Dodatkowo możesz „przeskoczyć” z dowolnej liczby całkowitej $a$ na inną liczbę całkowitą $b$ , ale musisz zapłacić $|a-b|$ dolarów za przywilej. Celem jest rozwiązanie labiryntu przy jak najniższych kosztach. W powyższym przykładzie możemy przejść od x do o przez x-14-18-27-28-o po koszcie 5, ale taniej jest przejść x-13-11-9-8-29-28-o tylko 4

Oto moje pytanie: jakie jest najlepsze rozwiązanie (jeśli chodzi o asymptotyczny czas działania), które możesz wymyślić w celu rozwiązania tego problemu? Możesz przyjąć wszelkie uzasadnione założenia dotyczące formatu wejściowego.

Uwaga: używam tutaj tagu „puzzle”, ponieważ mam na myśli odpowiedź $O(n^2)$ , ale nie jestem pewien, czy jest optymalna i chciałbym sprawdzić, czy ktoś inny może poprawić moje rozwiązanie. (Tutaj $n$ to liczba całkowita w labiryncie.)

ds.algorithms optimization puzzles

— Fixee
źródło

Rekwizyty dla dziecka za tworzenie takich kreatywnych i matematycznych łamigłówek!

— bbejot

@bbejot Powinieneś zobaczyć niektóre rzeczy, o które mnie pyta ... czasami nie mogę odpowiedzieć na jego pytania. Np. Math.stackexchange.com/questions/33094/…

— Fixee

Nie jestem pewien, czy obliczenia kosztów są prawidłowe. x-14-18-27-28-o powinien kosztować

a x-13-11-9-8-29-28-o powinien kosztować

4 + 9 + 1 = 14

$4 + 9 + 1 = 14$

2 + 2 + 1 + 21 + 1 = 27

$2 + 2 + 1 + 21 + 1 = 27$

— Dave Clarke

@Dave nie wszystkie przejścia są skokami. Moglibyśmy napisać „ab” dla skoków (które mają koszt

) i „a-> b” dla przejścia po wykresie od a do b (który ma koszt

), co jest dozwolone tylko wtedy, gdy są osiągalne bez zburzenia ściany w labiryncie. W tym zapisie mamy x-> 14-18-> 27-28-> o, a koszt 5 i x-> 13-11-> 9-8-> 29-28-> o. Rozmyślam, że Fixee nie wprowadził tego zapisu, ponieważ jest zbędny: nie ma powodu, aby skakać dwa razy, a zatem przeskakiwanie i spacery w labiryncie będą się zmieniać.

| a - b |

$|a - b|$

0

$0$

— Artem Kaznatcheev

To doskonały problem z pracą domową!

— Jeffε

Odpowiedzi:

Możesz to rozwiązać w czasie przy użyciu odmiany algorytmu Dijkstry. Nie możemy wykonać wszystkich aktualizacji odległości, gdy odwiedzimy nowy węzeł. Jeśli odwiedzimy węzeł , musimy jedynie zaktualizować odległości od wszystkiego, na co można przejść $O(n\log n)$ $y$ do 0, i zaktualizować odległości do dwóch węzłów i z najbliższymi wartościami mniejszymi i większymi niż które nie został jeszcze wybrany. $y$ $y_-$ $y_+$ $y$ $y$

Te aktualizacje są wystarczające, aby sterty zwracały minimalny element, ponieważ najbliższy węzeł, do którego przeskakujesz, musi znajdować się liczbowo tuż nad lub tuż pod wcześniej odwiedzonym węzłem.

Każdy węzeł jest aktualizowany co najwyżej do 0 (jeśli usuniemy wszystkie węzły o zerowej odległości z kolejki, aby uniknąć zachowania kwadratowego), i za każdym razem, gdy dodamy węzeł, wykonujemy tylko inne aktualizacje O (1). Znalezienie wartości i można wykonać w czasie liniowym, jeśli będziemy również przechowywać uporządkowaną podwójnie połączoną listę wszystkich węzłów, posortowaną według ich wartości całkowitych. Zbudowanie tej podwójnie połączonej listy zajmuje , a na koniec $y_-$ $y_+$ $O(n \log n)$ aktualizacje i wyskakujące ze stosu zajmują czas , co daje całkowity czas działania $O(n)$ $O(n \log n)$ $O(n \log n)$

— Dave
źródło

Prawdopodobnie można to nieco poprawić, używając kolejek sortowania i priorytetów, które są wyspecjalizowane dla liczb całkowitych, ale nie można zrobić nic lepszego niż sortowanie liczb całkowitych, co widać po poniższym zmniejszeniu: jeśli mamy listę wartości liczb całkowitych

, ustaw

na dwukrotność minimum, a

na dwukrotność maksimum. Utwórz region o wartościach

dla siebie

. Najlepszym rozwiązaniem przechodzi każdego regionu posortowanych według

, a więc wytwarza sortowanie

x_{1}, \dots, x_{n}

$x_1,\ldots,x_n$

x

$x$

o

$o$

2 x_{i}

$2x_i$

2 x_{i} + 1

$2x_i+1$

x_{i}

$x_i$

x_{i}

$x_i$

wartości

x_{i}

$x_i$

— Dave

Dave ma rację, można to zredukować do

, aktualizując tylko

. Ponadto zamiast łączyć każdy węzeł w regionie z każdym innym węzłem w regionie, muszą one być połączone tylko z 1 lub 2 innymi węzłami w regionie (tworząc ścieżkę). Zatem każdy węzeł ma tylko do 4 krawędzi. Następnie algorytm Dijkstry (z kolejką o minimalnym priorytecie) może być zastosowany, zapewniając czas

O (n l g n)

$O(n lg n)$

y_{+}

$y_+$

y_{-}

$y_-$

O (n l g n)

$O(n lg n)$

— bbejot

@bbejot: Ale jeśli tak, to czy integralna kolejka priorytetowa Thorup nie skraca czasu działania do

, a nawet do

O (n \log \log n)

$O(n \log\log n)$

O (n)

$O(n)$ z jakąś dodatkową techniką segmentowania w sytuacji nieukierunkowanej?

— Hsien-Chih Chang 張顯之

Czuję, że może być najlepszym, co możesz dostać. $O(n^2)$

Naturalne wydaje się przekształcenie tego problemu w najkrótszą ścieżkę za pomocą specjalnego węzła początkowego (x) i węzła końcowego (0). Byłby również jeden inny węzeł dla każdej liczby. Zarówno x, jak i 0 mają krawędzie o wadze 0 do wszystkich węzłów liczbowych, które są osiągalne w labiryncie. Wszystkie węzły liczbowe są połączone albo z wagą 0 (jeśli liczby są osiągalne w labiryncie), albo z różnicą między liczbami (jeśli nie można osiągnąć labiryntu).

Najkrótszej ścieżki na tym wykresie nie można rozwiązać w zakresie mniejszym niż ponieważ wykres ma z grubsza krawędzi, aw najgorszym przypadku każdy przypadek musiałby zostać wyświetlony raz. Jako taki, algorytm Dijkstra'a dla najkrótszej ścieżki zajmuje czas i jest optymalny w najgorszym przypadku. $O(n^2)$ $n^2$ $O(n^2)$

— bbejot
źródło

O (n^{2})

$O(n^2)$

O (n^{2} \lg n)

$O(n^2 \lg n)$

r

$r$

O (r^{2})

$O(r^2)$

Potrzebujesz również czasu

aby utworzyć wykres, więc całkowity czas działania powinien wynosić

O (n \log n)

$O(n\log n)$

O (r^{2} + n \log n)

$O(r^2 + n\log n)$

Ω (n \log n)

$\Omega(n\log n)$

Ω (n^{2})

$\Omega(n^2)$