Rozstrzygalność labiryntu fraktalnego

Fraktalny labirynt to labirynt, który zawiera swoje kopie. Np. Następujący Mark Mark Wolf z tego artykułu :

Zacznij od MINUS i przejdź do PLUS. Po wprowadzeniu mniejszej kopii labiryntu zapisz jej nazwę literową, ponieważ będziesz musiał pozostawić tę kopię przy wyjściu. Musisz wyjść z każdej zagnieżdżonej kopii labiryntu, w którą wszedłeś, pozostawiając w odwrotnej kolejności, w jakiej je wprowadziłeś (na przykład: wpisz A, wpisz B, wpisz C, wyjdź C, wyjdź B, wyjdź A). Pomyśl o tym jak o serii zagnieżdżonych pudełek. Jeśli nie ma ścieżki wyjścia wychodzącej z zagnieżdżonej kopii, osiągnąłeś ślepy zaułek. Kolor został dodany, aby ścieżki były wyraźniejsze, ale jest tylko dekoracyjny.

Jeśli istnieje rozwiązanie, pierwsze wyszukiwanie powinno znaleźć rozwiązanie. Załóżmy jednak, że nie ma rozwiązania dla labiryntu - wtedy nasz program wyszukiwania będzie działał wiecznie coraz głębiej.

Moje pytanie brzmi: biorąc pod uwagę labirynt fraktalny, jak możemy ustalić, czy ma rozwiązanie, czy nie?

Lub alternatywnie, czy dla fraktalnego labiryntu o danym rozmiarze (liczba wejść / wyjść na kopię) istnieje ograniczenie długości najkrótszego rozwiązania? (gdyby istniała taka granica, moglibyśmy exaustycznie szukać tylko tak głęboko)

Szybki nieformalny algorytm mający udowodnić, że problem jest rozstrzygalny:

• załóżmy, że istnieją Wejścia / Wyjścia I 1 , . . . I n ;$n$$I_1,...I_n$
• zbudowania wykresu , gdzie każdy I I The M I N U S i P L U S są węzłami i zastąpić każdą zagnieżdżonej labirynt M j o K n podgrafu (pełne wykres); dodaj krawędzie między I i , M I N U S , P L U S , M j I k zgodnie z labiryntem; zachowaj „zewnętrzny” M j I i → M $G$$I_i$$MINUS$$PLUS$$Mj$$K_n$$I_i, MINUS, PLUS, Mj_{I_k}$ krawędzie różnią się od odpowiednich krawędzi „wewnętrznych”II→IkoM-jjako kompletny podgrafu;$Mj_{I_i} \rightarrow Mj_{I_k}$$I_i \rightarrow I_k$$Mj$
• wylicz wszystkie ścieżki od MINUS do PLUS w (unikanie cykli);$G$
• jeśli znajdziesz ścieżkę, która nie przechodzi przez zagnieżdżoną kopię, jest to rozwiązanie; mogłyby rozwijać każdy „wewnętrzne” przechodzenia między zagnieżdżonej labirynty każdej ścieżce:$Mj$

Załóżmy, że ścieżka w pierwszym wyliczeniu to , wówczas ścieżka jest prawidłowym rozwiązaniem, jeśli istnieje ścieżka od I i → I j oraz od I k → I h w oryginalnym labiryncie (wykres G ).$MINUS \rightarrow A_{I_i} \rightarrow A_{I_j} \rightarrow B_{I_k} \rightarrow B_{I_h} \rightarrow PLUS$$I_i \rightarrow I_j$$I_k \rightarrow I_h$$G$

Więc musimy rozwijać się i B I k → B I h przechodzenia przez wyliczając wszystkie ścieżki z I i aby ja k iz ja k do I h w G .$A_{I_i} \rightarrow A_{I_j}$$B_{I_k} \rightarrow B_{I_h}$$I_i$$I_k$$I_k$$I_h$$G$

Nieskończone pętle są wykrywane, gdy jesteśmy wyliczając wszystkie ścieżki od do I k w ekspansji ścieżki, która w poprzednim etapie już zawarte . . . → M I i → M I k → . . . dla niektórych submaze M (istnieje tylko n 2 możliwych rozszerzeń).$I_i$$I_k$$... \rightarrow M_{I_i} \rightarrow M_{I_k} \rightarrow ...$$M$$n^2$

Rozwiązanie zostanie znalezione, jeśli znajdziemy rozszerzenie ścieżki, które zawiera tylko wejścia / wyjścia ; labirynt nie ma rozwiązania, jeśli nie możemy dalej rozwijać ścieżek bez pętli.$I_i$

To nie jest „odpowiedź” na moje pytanie, ale raczej obszerny komentarz, który ludzie tutaj mogą uznać za interesujący.

Twierdzę, że istnieje naturalna definicja „labiryntu typu analizy” i rozwiązania, i różni się ona od stosowanej tutaj definicji informatycznej / teoretycznej. W szczególności możesz mieć labirynt fraktalny, który ma „rozwiązanie” pod definicją analizy, ale zostałby uznany za nierozwiązywalny przez algorytm Marizio De Biasi i technikę automatów pushdown Petera Shora.

Definicja: labirynt jest zwarty podzbiór płaszczyzny M ⊂ R 2 , zawierającej punkt początkowy i punkt końcowy s , e ∈ M , odpowiednio. Rozwiązanie jest funkcją ciągłą F : [ 0 , T ] → M tak, że f ( 0 ) = e i f ( t ) = E .$M$$M \subset \mathbb{R}^2$$s,e \in M$$f:[0,T] \rightarrow M$$f(0)=s$$f(T)=e$

Rozważmy teraz krzywą Hilberta :

Krzywą tę można interpretować jako „labirynt fraktalny” za pomocą następującego diagramu:

$P$

$P = APA^{-1}BPB^{-1}CPC^{-1}DPD^{-1}$

Teraz możesz argumentować, że nie jest to w duchu fraktalnych labiryntów, ponieważ krzywa Hilberta wypełnia cały kwadrat, a zatem możesz po prostu narysować odcinek linii prostej od początku do końca. Sprzeciw ten można jednak łatwo obejść - wystarczy bezpośrednio osadzić diagram krzywej Hilberta, jak pokazano tutaj:

To także zawiera sekwencję jednakowo zbieżnych ciągłych ścieżek od początku do końca, za pomocą tego samego argumentu użytego do pokazania jednolitej zbieżności krzywej Hilberta. Jest to jednak prawdziwy „fraktalny labirynt” w tym sensie, że nie wypełnia całej przestrzeni.

Mamy więc labirynt fraktalny, który można rozwiązać za pomocą analitycznej definicji, ale nie można rozwiązać za pomocą teoretycznej definicji grafu!!?

W każdym razie jestem pewien, że moja logika jest poprawna, ale wydaje się, że jest to sprzeczne z intuicją, więc jeśli ktokolwiek mógłby rzucić na to trochę światła, byłbym wdzięczny.