Najlepsza ścieżka w siatce

Question

Mam najlepszy problem z ścieżką do rozwiązania. Biorąc pod uwagę siatkę nxn wypełnioną pieszymi kaflami i płytkami, które nie mogą się przechodzić, muszę dotrzeć do punktu B z punktu A, najkrótszą drogą. Sztuczka polega na tym, że niektóre z płytek, które można chodzić, zawierają punkty. Aby być dobrym rozwiązaniem, gdy osiągnę cel, muszę mieć określoną liczbę punktów. Płytki mają zmienną liczbę punktów na nich (lub brak) i potrzebuję najkrótszej drogi, aby osiągnąć cel, ale także zebrać co najmniej punkty M na trasie.

Próbowałem algorytmu A *, który znajduje najkrótszą ścieżkę między dwoma punktami i próbował dostosować go tak, aby stan zatrzymania był spełniony nie tylko wtedy, gdy osiągnął cel, ale również miał wymagane punkty. Nie działa tak, jak ja to zrobiłem, ponieważ blokuję ścieżki.

Jeśli masz jakieś sugestie, jak podejść do tego problemu lub inny algorytm, który byłby bardziej odpowiedni, byłbym wdzięczny za pomoc. Dzięki.

Answer 1

W Przypadek, w którym wciąż tkwi problem, ponieważ inne odpowiedzi/komentarze dają tylko częściową odpowiedź - oto pęknięcie w przestrzeni problemowej.

W rzeczywistości możesz użyć A * z kilkoma modyfikacjami do przechwycenia (w większości) nieuporządkowanej ścieżki punktu M. Jedyne, co musisz zmienić, to heurystyczne i kryteria zakończenia.

Najpierw należy zmienić heurystykę, aby uwzględnić ścieżki za pośrednictwem punktów M. Hierarchia musi być dopuszczalna i spójna, więc musi być równa wartości mniejszej lub równej prawdziwemu kosztowi ścieżki i może się zmniejszyć tylko wtedy, gdy zbliżysz się do celu (musi być monotoniczny).

Możesz myśleć o ścieżce, którą teraz bierzesz, jako ścieżkach podrzędnych M, które musisz wykonać, a każda z nich działa jak normalna ścieżka. Tak więc dla wykresu jednopunktowego (z tylko przestrzenią kończącą) można użyć standardowej heurystyki, takiej jak odległość euklidesowa. Jest to chciwa ocena, która sugeruje, że prosta droga jest optymalna i dla której nie można zrobić lepiej w idealnych warunkach (jest to dopuszczalne).

W przypadku więcej niż jednej ścieżki podejście chciwości mówi podobnie, że odblokowana prosta droga między punktami jest najszybsza, jaką można przejść. Jest to również spójna heurystyka, ponieważ nie można odejść dalej i nadal mieć lepszy wynik. Najtrudniejsze jest ustalenie, które uporządkowanie punktów M jest najszybsze bez przeszkód, aby utrzymać dopuszczalną heurystykę.Możesz znaleźć optymalny wybór punktów M na wykresie, na którym wszystkie płytki można chodzić po szerokości, najpierw przeszukując odległość euklidesową od aktualnej płytki do każdego z punktów M, do każdego z pozostałych punktów M-1, ..., do kwadrat kończący. Ta operacja jest kosztowna, ponieważ musisz ją wykonać dla każdego kwadratu, do którego się zbliżasz - ale możesz użyć programowania dynamicznego lub buforowania wyszukiwania, aby wymagane amortyzowane obliczenia spadły do ​​O (M) na krok.

Teraz, gdy już uzyskasz ścieżki punktów M, które będą najszybsze bez przeszkód, możesz użyć odległości euklidesowej między każdym punktem na tej ścieżce a bieżącą pozycją jako heurystyką. To chciwy szacunek ruchu, więc jest zawsze dopuszczalny (nie można pokonać szacunkowych kosztów) i jest spójny, ponieważ nie można odejść od następnego chciwego punktu optymalnego i zmniejszyć koszty, ponieważ wybiera inny chciwy punkt z bieżącego pola nie byłoby dopuszczalne.

Wreszcie, kryteria końcowe muszą zostać zmienione, aby osiągnąć M punktów, gdzie ostatnim punktem jest kafelka kończąca. To imituje chodzące wykresy M bez potrzeby konstruowania M! możliwe wykresy do chodzenia. Podana heurystyka pozwoli A * zrobić to magicznie bez zmiany podstawowego algorytmu i powinna być mniej więcej tak efektywna, jak to tylko możliwe, przy zachowaniu wymaganych ograniczeń heurystycznych na ogólnych siatkach.

Answer 2

Możesz dodawać warstwy do wykresu, gdy znajdujesz się w warstwie głębi X -> zebrałeś co najmniej X punktów. Dodaj odpowiednie krawędzie na wykresie od górnej warstwy do warstwy +N, gdzie N to liczba punktów w bieżącym kafelku.

Twój wykres jest nieskończony, ale możesz dynamicznie dodawać liczbę klocków do wierzchołków, podczas przechodzenia przez krawędź. A ponieważ jest nieskończona, nie można stwierdzić, czy osiągalne jest zakończenie, ale można sprawdzić, czy istnieje ścieżka na wykresie podstawowym i czy istnieje co najmniej jeden punkt.

Powinieneś zakończyć grę na poziomach >M.

Jeśli potrzebujesz wyjaśnień, poprosić =)

Edycja

Jak powiedział @Pyrce, również powinna dostarczyć consisten heurystyki, jeśli planujesz używać * http://en.wikipedia.org/wiki/Consistent_heuristic