Implementacja algorytmu A Star (A *) w Javie

Question

Nota prawna: Mam małe doświadczenie w Javie, ponieważ jestem głównie programistą C#.

Chciałbym wdrożyć java algorytmu A *.
Tak, widziałem wiele wersji tego samego internetu i nie jestem w stanie wybrać między nimi.

Szukam implementacji algorytmu A *, który wykorzystuje wszystkie nowe funkcje java, co sprawia, że ​​algorytm jest szybszy (nawet jeśli odrobinę). Powodem jest to, że implementujemy to do wyszukiwania ścieżek na MMO, a więc wydajność jest najwyższym priorytetem.

Jakieś wskazówki (co najmniej gdzie szukać)?

Answer 1

Wypróbuj kilka, zmierz, wybierz najszybszy, dostosuj się do swoich potrzeb. Wydajność jest określana głównie przez wybór funkcji heurystycznej, która jest niezależna od A * właściwego.

Jeśli heurystyka zostanie naprawiona, implementacja kolejki priorytetowej prawdopodobnie stanie się wąskim gardłem, więc spróbuj pairing heaps. Są to jedne z najszybszych struktur danych stert w praktyce i mają przewagę nad stertami binarnymi, które pozwalają na czas wstawienia O (1) + amortyzowany pop (O) (log n). Jest to ważne w oczekiwanym przypadku wielu pętli A *, w których kolejka jest wypełniona, ale nigdy całkowicie pusta, tj. Liczba wstawień jest znacznie większa niż liczba popów.

Jeśli pamięć staje się problemem, przejdź do iteracyjnego pogłębiania A * (IDA *) lub rekursywnego najlepszego wyszukiwania (RBFS).

Jeśli nic nie działa, należy rozważyć zastosowanie algorytmu aproksymacji (chciwe wyszukiwanie). Po prostu optymalizacja przyzwoicie napisanej pętli A * nie przyniesie Ci ogromnych przyspieszeń.

Zapoznaj się z Russell and Norvig dla algorytmów i dobrej dyskusji na temat problemów.

Answer 2

Jeśli wydajność ma najwyższy priorytet, A * prawdopodobnie nie jest najlepszym wyborem. A * zapewnia dokładne rozwiązanie, w wyniku czego przetwarzanie jest kontynuowane, dopóki nie znajdzie poprawnej odpowiedzi. Istnieją inne lekkie rozwiązania, które zapewniają wystarczająco dobre rozwiązania w znacznie szybszym czasie: na przykład wymuszone wspinanie się po zboczach lub najlepiej najpierw, a nawet prosta głębokość.