Wyszukiwanie punktu przeskoku

W informatyce wyszukiwanie punktów przeskoku ( JPS ) jest optymalizacją algorytmu wyszukiwania A* dla siatek o jednolitym koszcie. Zmniejsza symetrie w procedurze wyszukiwania poprzez przycinanie grafów, eliminując pewne węzły w siatce w oparciu o założenia, które można przyjąć na temat sąsiadów bieżącego węzła, o ile spełnione są pewne warunki dotyczące siatki. W rezultacie algorytm może uwzględniać długie „skoki” wzdłuż linii prostych (poziomych, pionowych i ukośnych) w siatce, zamiast małych kroków z jednej pozycji siatki do drugiej, które bierze pod uwagę zwykły A*.

Wyszukiwanie punktu przeskoku zachowuje optymalność A*, potencjalnie skracając czas jego działania o rząd wielkości.

Historia

Oryginalna publikacja Harabor i Grastien zawiera algorytmy przycinania sąsiadów i identyfikowania następców. Oryginalny algorytm przycinania sąsiadów pozwalał na wycinanie narożników, co oznaczało, że algorytm mógł być używany tylko do przenoszenia agentów o zerowej szerokości, ograniczając jego zastosowanie do rzeczywistych agentów (np. robotyka) lub symulacji (np. wiele gier).

Autorzy przedstawili zmodyfikowane zasady przycinania dla zastosowań, w których podcinanie narożników jest niedozwolone w następnym roku. W artykule przedstawiono również algorytm wstępnego przetwarzania siatki w celu zminimalizowania wyszukiwania online .

W 2014 roku autorzy opublikowali szereg dalszych optymalizacji. Optymalizacje te obejmują eksplorację kolumn lub rzędów węzłów zamiast pojedynczych węzłów, wstępne obliczenia „skoków” w siatce i silniejsze reguły przycinania.

Przyszła praca

Chociaż wyszukiwanie punktów przeskoku jest ograniczone do jednorodnych siatek kosztów i agentów o jednorodnej wielkości, autorzy planują przyszłe badania nad zastosowaniem JPS z istniejącymi technikami przyspieszania opartymi na siatkach, takimi jak siatki hierarchiczne.