Pytanie Jak rozwiązać 15-zagadkę z A-Star lub algorytmem Dijkstry?


W jednej z moich książek o AI przeczytałem, że popularne algorytmy (A-Star, Dijkstra) do odnajdywania ścieżek w symulacji lub gier są również używane do rozwiązania dobrze znanej "15-łamigłówki".

Czy ktoś może mi podać wskazówki na temat tego, jak zredukować układankę 15 do wykresu węzłów i krawędzi, aby móc zastosować jeden z tych algorytmów?

Gdybym traktował każdy węzeł na wykresie jako stan gry, czy to drzewo nie stałoby się dość duże? A może to po prostu sposób na zrobienie tego?


14
2017-09-18 17:56


pochodzenie


to pachnie jak praca domowa compsci! - Rick Minerich
Jest to dość powszechny problem z pracą domową CompSci - monksy


Odpowiedzi:


Dobra heurystyka dla A-Star z 15 układami to liczba kwadratów znajdujących się w niewłaściwym miejscu. Ponieważ potrzebujesz co najmniej jednego ruchu na kwadrat, który jest nie na miejscu, liczba kwadratów poza miejscem jest mniejsza lub równa liczbie ruchów wymaganych do rozwiązania zagadki, co czyni ją odpowiednią heurystyką dla A-Star .


8
2018-04-12 18:20



Nie sądzę, że proponowane dane są dobrze dopasowane do problemu. Intuicyjnie byłoby to bardzo podatne na sytuacje z kilkoma elementami po niewłaściwej stronie planszy. Prawdopodobnie lepiej byłoby z sumą odległości od ich ostatecznej pozycji. - wowest
Masz rację, to lepiej, ale moje też będą działać. - RossFabricant


Szybkie wyszukiwanie w wyszukiwarce Google pokazuje kilka dokumentów, które opisują to szczegółowo: jeden na jeden Równoległe wyszukiwanie kombinatorycznei jeden na Wyszukiwanie wykresu pamięci zewnętrznej

Ogólna zasada, jeśli chodzi o problemy algorytmiczne: ktoś prawdopodobnie zrobił to przed tobą i opublikował ich wyniki.


6
2017-09-22 20:13



Połowa twoich linków nie działa. - Jonny
Oto pierwszy link: cse.psu.edu/~pxr3/optslides.pdf - Zobayer Hasan


Jest to zadanie dla 8-zagadkowego problemu, w którym omówiono użycie algorytmu A *, ale także dość proste:

http://www.cs.princeton.edu/courses/archive/spring09/cos226/assignments/8puzzle.html


3
2018-06-20 19:01





Graficzny sposób rozwiązania problemu polega na wyobrażeniu sobie każdej konfiguracji planszy jako wierzchołka wykresu, a następnie skorzystaniu z pierwszego wyszukiwania z przycinaniem opartego na czymś takim, jak odległość Manhattena planszy, aby wyprowadzić najkrótszą ścieżkę od początku konfiguracja do rozwiązania.

Jednym z problemów z tym podejściem jest to, że dla każdego n x n deska gdzie n > 3 przestrzeń gry staje się tak duża, że ​​nie jest jasne, w jaki sposób można efektywnie oznaczyć odwiedzone wierzchołki. Innymi słowy, nie ma oczywistego sposobu oceny, czy aktualna konfiguracja planszy jest identyczna z tą, która została wcześniej odkryta poprzez przechodzenie przez inną ścieżkę. Innym problemem jest to, że rozmiar wykresu rośnie tak szybko n (to około (n^2)!), że po prostu nie nadaje się do ataku sił brue'a, ponieważ liczba ścieżek staje się niewykonalna w obliczeniach.

Artykuł autorstwa Iana Parberry Algorytm czasu rzeczywistego dla (n^2 − 1) - Puzzle opisuje prosty chciwy algorytm, który iteracyjnie dociera do rozwiązania, wypełniając pierwszy wiersz, następnie pierwszą kolumnę, a następnie drugi wiersz ... Dostaje rozwiązanie niemal natychmiast, jednak rozwiązanie jest dalekie od optymalnego; w gruncie rzeczy rozwiązuje problem w sposób, w jaki człowiek byłby pozbawiony dźwigania jakiegokolwiek obliczeniowego mięśnia.

Ten problem jest ściśle związany z rozwiązaniem sześcianu Rubika. Wykres wszystkich gier stwierdza, że ​​jest zbyt duży, aby go rozwiązać za pomocą siły Brue'a, ale istnieje dość prosta 7-stopniowa metoda, która może być użyta do rozwiązania dowolnego sześcianu w ciągu około 1-2 minut przez sprawnego człowieka. Ta ścieżka jest oczywiście nieoptymalna. Ucząc się rozpoznawać wzorce definiujące sekwencje ruchów, prędkość może zostać zmniejszona do 17 sekund. Jednak ten wyczyn Jiri jest nieco nadludzki!

Metoda Parberry opisuje przesuwanie tylko jednej płytki na raz; ktoś wyobraża sobie, że algorytm można ulepszyć, wykorzystując zręczność Jiri i przesuwając wiele płytek jednocześnie. Nie byłoby to, jak dowodzi Parberry, skrócenia długości ścieżki n^3, ale zmniejszyłoby to współczynnik wiodącego terminu.


3
2018-04-03 09:34





Pamiętaj, że A * przeszuka obszar problemowy, idąc w dół najbardziej prawdopodobną ścieżką do celu zdefiniowanego przez twojego heurestycznego.

Tylko w najgorszym przypadku, gdy skończy się konieczność zalania, wypełnia całą przestrzeń problemową, zdarza się to zazwyczaj, gdy nie ma faktycznego rozwiązania problemu.


2
2017-10-29 10:05





Po prostu użyj drzewa gry. Pamiętaj, że drzewo to specjalna forma wykresu.

W twoim przypadku liście każdego węzła będą pozycją gry po wykonaniu jednego z ruchów, który jest dostępny w bieżącym węźle.


1
2017-09-18 18:08





Proszę bardzo http://www.heyes-jones.com/astar.html


1
2018-06-20 18:37



Dzięki, to moja strona! Jest kod do rozwiązania 8puzzle i jest oparty na leczeniu w Prolog Programming Ivana Bratko - justinhj