Претрага са скоком

У области информатика, претрага са скоком је алгоритам који је оптимизација алгоритма А* алгоритам за претрагу. Смањује симетрије у процедури претраге помоћу орезивања графа, елеминишући одређене чворове у бази на основу претпоставки које се могу донети о суседима тренутног чвора, докле год су неки услови везани за мрежу графа испуњени. Као резултат, алгоритам може да узима у обзир и „велике скокове“ преко правих (хоризонталних, вертикалних или дијагоналних) линија мреже графа, који су оптималнији од малих корака од сваке позиције мреже до следеће коју извршава класичан А* алгоритам.

Претрага са скоком чува оптималност А*, док потенцијално смањује време извршавања.

Историја

Харабор и Грастјенова оригинална објава описује алгоритме за орезивање суседних чворова и одеђивање наследника. Оригинални алгоритам за орезивање је допуштао да се секу ћошкови, што је значило да алгоритам може да се употреби само за померање агената са ширином нула; и и тиме је била ограничена употреба са правим агетнима (нпр. у роботици) или са симулацијама (многе игре).

Аутори су следеће године издали оптимизованији алгоритам који није допуштао да се секу ћошкови. Овај чланак је садржао и алгоритам којим је омогућена провера мреже да би се минимизовао број претрага.

Аутори су објавили неколико оптимизација 2014. године. Ове оптимизације укључују истраживање редова и колона чворова, уместо сваког чвора посебно и тиме се врши прерачунавање скокова по мрежи, и уводе се оштрија правила орезивања.

Будући рад

Иако је претрага са скоком ограничена на мреже без тежинских грана и агенте са сталном величином, аутори раде на истраживању примене овог алгоритма са постојећим техникама заснованим на убрзавању скокова као што су хијерархијске мреже.