Śledzenie odwiedzonych stanów w wyszukiwaniu rozszerzonym

Próbowałem więc zaimplementować BFS na łamigłówce przesuwanej (typ liczbowy). Najważniejsze, co zauważyłem, to to, że jeśli masz 4*4tablicę, liczba stanów może być tak duża 16!, że nie mogę wcześniej wyliczyć wszystkich stanów.

Więc moje pytanie brzmi: jak mogę śledzić już odwiedzone stany? (Używam tablicy klas, każda instancja klasy zawiera unikalny wzór tablicy i jest tworzona przez wyliczenie wszystkich możliwych kroków z bieżącego kroku).

Szukałem w sieci i najwyraźniej nie wracają one do właśnie ukończonego poprzedniego kroku, ALE możemy też wrócić do poprzedniego kroku inną drogą, a następnie ponownie wymienić wszystkie kroki, które wcześniej odwiedziłem. Jak więc śledzić odwiedzone stany, kiedy wszystkie stany nie zostały jeszcze wyliczone? (porównanie już obecnych stanów z obecnym krokiem będzie kosztowne).

Możesz użyć set(w matematycznym znaczeniu tego słowa, tj. Kolekcji, która nie może zawierać duplikatów) do przechowywania stanów, które już widziałeś. Operacje, które musisz wykonać, to:

• wstawianie elementów
• testowanie, czy elementy już tam są

Prawie każdy język programowania powinien już mieć obsługę struktury danych, która może wykonywać obie te operacje w stałym ( ) czasie. Na przykład:$O(1)$

• set w Pythonie
• HashSet w Javie

Na pierwszy rzut oka może się wydawać, że dodanie wszystkich stanów, które kiedykolwiek widziałeś, do takiego zestawu, będzie kosztowne pod względem pamięci, ale nie jest tak źle w porównaniu z pamięcią, której już potrzebujesz na swojej granicy; jeśli twój współczynnik rozgałęzienia wynosi , twoja granica wzrośnie o elementy na odwiedzany węzeł (usuń węzeł z granicy, aby go „odwiedzić”, dodaj nowych następców / dzieci), podczas gdy twój zestaw wzrośnie tylko o dodatkowy węzeł na odwiedzony węzeł.$b$$b - 1$$1$$b$$1$

W pseudokodzie taki zestaw (nazwijmy go closed_set, aby był spójny z pseudokodem na wikipedii, może być użyty w wyszukiwaniu szerokości w następujący sposób:

frontier = First-In-First-Out Queue
frontier.add(initial_state)

closed_set = set()

while frontier not empty:
    current = frontier.remove_next()

    if current == goal_state:
        return something

    for each child in current.generate_children()
        if child not in closed_set:    // This operation should be supported in O(1) time regardless of closed_set's current size
            frontier.add(child)

    closed_set.add(current)    // this should also run in O(1) time

(niektóre odmiany tego pseudokodu mogą również działać i być mniej lub bardziej wydajne w zależności od sytuacji; na przykład możesz również wziąć closed_setdo wszystkich węzłów, których już dodałeś dzieci na granicy, a następnie całkowicie uniknąć generate_children()połączenia jeśli currentjest już w closed_set.)

To, co opisałem powyżej, byłoby standardowym sposobem radzenia sobie z tym problemem. Podejrzewam, że intuicyjnie innym „rozwiązaniem” może być zawsze losowa kolejność nowej listy stanów następczych przed dodaniem ich do granicy. W ten sposób nie unikniesz problemu od czasu do czasu dodawania stanów, które już wcześniej rozszerzyłeś na granicę, ale myślę, że powinno to znacznie zmniejszyć ryzyko utknięcia w nieskończonych cyklach.

Uwaga : nie znam żadnej formalnej analizy tego rozwiązania, która dowodzi, że zawsze unika się nieskończonych cykli. Jeśli spróbuję to „przelecieć” przez głowę, intuicyjnie, podejrzewam, że powinien to być rodzaj pracy i nie wymaga dodatkowej pamięci. Mogą być jednak przypadki krawędziowe, o których teraz nie myślę, więc może to po prostu nie działać, standardowe rozwiązanie opisane powyżej będzie bezpieczniejszym zakładem (kosztem większej ilości pamięci).

Odpowiedź Dennisa Soemersa jest poprawna: należy użyć HashSet lub podobnej struktury, aby śledzić odwiedzone stany w BFS Graph Search.

Jednak nie do końca odpowiada na twoje pytanie. Masz rację, że w najgorszym przypadku BFS będzie wymagać przechowywania 16! węzły Chociaż czasy wstawiania i sprawdzania w zestawie będą wynosić O (1), nadal potrzebujesz absurdalnej ilości pamięci.

Aby to naprawić, nie używaj BFS . Jest trudny do rozwiązania dla wszystkich problemów z wyjątkiem najprostszych, ponieważ wymaga zarówno czasu, jak i pamięci, które są wykładnicze w odległości do najbliższego stanu docelowego.

Znacznie bardziej wydajnym algorytmem pamięci jest iteracyjne pogłębianie . Ma wszystkie pożądane właściwości BFS, ale wykorzystuje tylko pamięć O (n), gdzie n jest liczbą ruchów do osiągnięcia najbliższego rozwiązania. Może to jeszcze trochę potrwać, ale limity pamięci osiągniesz na długo przed limitami związanymi z procesorem.

Jeszcze lepiej, opracuj heurystykę specyficzną dla domeny i użyj wyszukiwania A * . Powinno to wymagać sprawdzenia tylko bardzo małej liczby węzłów i umożliwienia zakończenia wyszukiwania w czymś znacznie bliższym czasowi liniowemu.

Chociaż udzielone odpowiedzi są na ogół prawdziwe, BFS w 15-łamigłówce jest nie tylko całkiem wykonalne, ale zrobiono to w 2005 roku! Artykuł opisujący to podejście można znaleźć tutaj:

http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

Kilka kluczowych punktów:

• W tym celu potrzebna była pamięć zewnętrzna - czyli BFS użył dysku twardego do przechowywania zamiast pamięci RAM.
• W rzeczywistości istnieje tylko 15! / 2 stanów, ponieważ przestrzeń stanów ma dwa wzajemnie nieosiągalne składniki.
• Działa to w przesuwanej układance płytek, ponieważ przestrzenie stanu rosną naprawdę powoli z poziomu na poziom. Oznacza to, że całkowita pamięć wymagana dla dowolnego poziomu jest znacznie mniejsza niż pełny rozmiar przestrzeni stanu. (Kontrastuje to z przestrzenią stanu, taką jak Kostka Rubika, gdzie przestrzeń stanu rośnie znacznie szybciej.)
• Ponieważ układanka z przesuwanymi kafelkami nie jest przekierowywana, musisz martwić się tylko o duplikaty w bieżącej lub poprzedniej warstwie. W ukierunkowanej przestrzeni możesz generować duplikaty na dowolnej poprzedniej warstwie wyszukiwania, co znacznie komplikuje sprawę.
• W oryginalnej pracy Korfa (link powyżej) tak naprawdę nie zachowali wyniku wyszukiwania - wyszukiwanie tylko obliczyło, ile stanów było na każdym poziomie. Jeśli chcesz zapisać pierwsze wyniki, potrzebujesz czegoś takiego jak WMBFS ( http://www.cs.du.edu/~sturtevant/papers/bfs_min_write.pdf )
• Istnieją trzy podstawowe podejścia do porównywania stanów z poprzednich warstw, gdy stany są przechowywane na dysku.
  • Pierwszy opiera się na sortowaniu. Jeśli posortujesz dwa pliki następców, możesz zeskanować je w kolejności liniowej, aby znaleźć duplikaty.
  • Drugi jest oparty na haszowaniu. Jeśli używasz funkcji skrótu do grupowania następców w pliki, możesz załadować pliki mniejsze niż pełna przestrzeń stanu, aby sprawdzić duplikaty. (Zauważ, że są tutaj dwie funkcje skrótu - jedna do wysyłania stanu do pliku, a druga do rozróżniania stanów w tym pliku).
  • Trzeci to strukturalne wykrywanie duplikatów. Jest to forma wykrywania opartego na haszowaniu, ale odbywa się to w taki sposób, że duplikaty można sprawdzić natychmiast po ich wygenerowaniu, a nie po ich wygenerowaniu.

Jest tu o wiele więcej do powiedzenia, ale powyższe dokumenty zawierają o wiele więcej szczegółów.

Jak na ironię odpowiedź brzmi „użyj dowolnego systemu”. HashSet to dobry pomysł. Okazuje się jednak, że Twoje obawy dotyczące wykorzystania pamięci są bezpodstawne. BFS jest tak zły w tego rodzaju problemach, że rozwiązuje ten problem za Ciebie.

Weź pod uwagę, że twój BFS wymaga zachowania stosu nieprzetworzonych stanów. W miarę postępów w układance stany, z którymi masz do czynienia, stają się coraz bardziej różne, więc prawdopodobnie zauważysz, że każda warstwa twojego BFS zwielokrotnia liczbę stanów do oglądania przez około 3.

Oznacza to, że podczas przetwarzania ostatniej warstwy BFS musisz mieć w pamięci co najmniej 16! / 3 stanów. Niezależnie od tego, jakie podejście zastosowałeś, aby upewnić się, że dopasowanie do pamięci będzie wystarczające, aby Twoja poprzednio odwiedzona lista również mieściła się w pamięci.

Jak zauważyli inni, nie jest to najlepszy algorytm do użycia. Użyj algorytmu, który lepiej pasuje do problemu.

Problem 15 puzzli rozgrywa się na planszy 4x4. Implementacja tego w kodzie źródłowym odbywa się krok po kroku. Najpierw należy zaprogramować sam silnik gry. Pozwala to na grę przez człowieka. 15-łamigłówka ma tylko jeden wolny element i na tym elemencie wykonywane są akcje. Silnik gry akceptuje cztery możliwe polecenia: w lewo, w prawo, w górę i w dół. Inne działania są niedozwolone i można kontrolować grę tylko za pomocą tych instrukcji.

Kolejną warstwą do gry jest GUI. Jest to bardzo ważne, ponieważ pozwala przetestować silnik gry i spróbować rozwiązać grę ręcznie. Również GUI jest ważny, ponieważ musimy znaleźć potencjalną heurystykę. A teraz możemy porozmawiać o samej AI. AI musi wysyłać polecenia do silnika gry (w lewo, w prawo, w górę i w dół). Naiwnym podejściem do solvera byłby algorytm poszukiwania siły, co oznacza, że ​​AI wysyła losowe polecenia, aż do osiągnięcia celu. Bardziej zaawansowanym pomysłem jest zaimplementowanie pewnego rodzaju bazy danych wzorców, która zmniejsza przestrzeń stanu. Pierwsze wyszukiwanie nie jest bezpośrednio heurystyką, ale jest początkiem. Równo jest stworzyć wykres do testowania możliwych ruchów w sposób chronologiczny.

Śledzenie istniejących stanów można wykonać za pomocą wykresu. Każdy stan jest węzłem, ma identyfikator i identyfikator nadrzędny. AI może dodawać i usuwać węzły na wykresie, a planista może rozwiązać wykres w celu znalezienia ścieżki do celu. Z perspektywy programistycznej silnik gry z 15 puzzli jest obiektem, a lista wielu obiektów jest arraylistą. Są one przechowywane w klasie graficznej. Uświadomienie sobie tego w kodzie źródłowym jest nieco trudne, zwykle pierwsza próba kończy się niepowodzeniem, a projekt spowoduje wiele błędów. Aby poradzić sobie ze złożonością, taki projekt jest zwykle wykonywany w projekcie akademickim, co oznacza, że ​​jest to temat pisania artykułu na ten temat, który może mieć 100 stron i więcej.

Podejścia do gry

Prawdą jest, że tablica ma $16!$możliwe stany. Prawdą jest również to, że uczenie się na kursach algorytmicznych pierwszego roku polega na korzystaniu z zestawu skrótów, aby uniknąć nadmiarowości i niekończących się zapętleń podczas wyszukiwania wykresu, który może zawierać cykle wykresu.

Te trywialne fakty nie są jednak istotne, jeśli celem jest ukończenie układanki w jak najmniejszej liczbie cykli obliczeniowych. Pierwsze wyszukiwanie szerokości nie jest praktycznym sposobem na ukończenie układanki z ortogonalnym ruchem. Bardzo wysoki koszt pierwszego wyszukiwania byłby konieczny tylko wtedy, gdy liczba ruchów ma z jakiegoś powodu ogromne znaczenie.

Zejście podsekwencyjne

Większość wierzchołków reprezentujących stany nigdy nie będzie odwiedzana, a każdy odwiedzany stan może mieć od dwóch do czterech krawędzi wychodzących. Każdy blok ma pozycję początkową i końcową, a plansza jest symetryczna. Największa swoboda wyboru istnieje, gdy otwarta przestrzeń jest jedną z czterech pozycji środkowych. Najmniej jest, gdy otwarta przestrzeń jest jedną z czterech pozycji narożnych.

Rozsądna funkcja rozbieżności (błędu) to po prostu suma wszystkich x dysproporcji plus suma wszystkich y dysproporcji i liczby heurystycznie reprezentującej, który z trzech poziomów swobody przemieszczania się istnieje z powodu wynikającego z tego położenia otwartej przestrzeni (środek, krawędź , kąt).

Chociaż bloki mogą tymczasowo oddalić się od swoich miejsc docelowych, aby wesprzeć strategię ukończenia wymagającą sekwencji ruchów, rzadko zdarza się, że taka strategia przekracza osiem ruchów, generując średnio 5184 permutacji, dla których można porównać stany końcowe za pomocą powyższej funkcji rozbieżności.

Jeśli pusta przestrzeń i pozycje bloków od 1 do 15 są kodowane jako tablica skubków, potrzebne są tylko operacje dodawania, odejmowania i bitowe, dzięki czemu algorytm jest szybki. Powtarzanie ośmiu strategii brutalnej siły można powtarzać, aż różnica spadnie do zera.

Podsumowanie

Algorytm ten nie może się zmieniać, ponieważ zawsze istnieje co najmniej jedna z permutacji ośmiu ruchów, która zmniejsza dysparytet, niezależnie od stanu początkowego, z wyjątkiem stanu początkowego, który jest już ukończony.