Pretraga sa skokom

U oblasti informatika, pretraga sa skokom je algoritam koji je optimizacija algoritma A* algoritam za pretragu. Smanjuje simetrije u proceduri pretrage pomoću orezivanja grafa, eleminišući određene čvorove u bazi na osnovu pretpostavki koje se mogu doneti o susedima trenutnog čvora, dokle god su neki uslovi vezani za mrežu grafa ispunjeni. Kao rezultat, algoritam može da uzima u obzir i „velike skokove“ preko pravih (horizontalnih, vertikalnih ili dijagonalnih) linija mreže grafa, koji su optimalniji od malih koraka od svake pozicije mreže do sledeće koju izvršava klasičan A* algoritam.

Pretraga sa skokom čuva optimalnost A*, dok potencijalno smanjuje vreme izvršavanja.

Istorija

Harabor i Grastjenova originalna objava opisuje algoritme za orezivanje susednih čvorova i odeđivanje naslednika. Originalni algoritam za orezivanje je dopuštao da se seku ćoškovi, što je značilo da algoritam može da se upotrebi samo za pomeranje agenata sa širinom nula; i i time je bila ograničena upotreba sa pravim agetnima (npr. u robotici) ili sa simulacijama (mnoge igre).

Autori su sledeće godine izdali optimizovaniji algoritam koji nije dopuštao da se seku ćoškovi. Ovaj članak je sadržao i algoritam kojim je omogućena provera mreže da bi se minimizovao broj pretraga.

Autori su objavili nekoliko optimizacija 2014. godine. Ove optimizacije uključuju istraživanje redova i kolona čvorova, umesto svakog čvora posebno i time se vrši preračunavanje skokova po mreži, i uvode se oštrija pravila orezivanja.

Budući rad

Iako je pretraga sa skokom ograničena na mreže bez težinskih grana i agente sa stalnom veličinom, autori rade na istraživanju primene ovog algoritma sa postojećim tehnikama zasnovanim na ubrzavanju skokova kao što su hijerarhijske mreže.