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. [1]
Pretraga sa skokom čuva optimalnost A*, dok potencijalno smanjuje vreme izvršavanja.
Istorija
urediHarabor 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
urediIako 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.
Reference
uredi- ^ Witmer, Nathan (5. 05. 2013). „Jump Point Search Explained”. zerowidth positive lookahead. Arhivirano iz originala 10. 03. 2014. g. Pristupljeno 9. 03. 2014.