Pređi na sadržaj

Marginalna pretraga

S Vikipedije, slobodne enciklopedije

Marginalna pretraga pripada klasi algoritama za pretragu grafova, koja pronalazi put najmanje težine između zadatog čvora i ciljnog.

Algoritam

[uredi | uredi izvor]

Ako g(x) je cena pretraživanja od prvog čvora do tekućeg i ako h(x) je heuristička procena cene od tekućeg čvora do ciljnog, onda važi da je h(x) = g(x) + h(x) i da je h* tekuća cena pretrage do ciljnog čvora. Razmislite IDA* koja rekurzivno ide sleva nadesno (Pretraga u dubinu) iz korena čvora, i zaustavlja se kad pronađe ciljni čvor ili čvorovi postignu maksimalnu vrednost ƒ. Ako se cilj ne nalazi u prvom pragu ƒ, prag se tada povećava i ponovo se pokreće algoritam pretrage, tj. on ponavlja pretragu.

Postoje tri glavne neefikasnosti IDA*. Prvo, IDA* će ponoviti algoritam kada ima više (ponekad nisu optimalne) putanja do ciljnog čvora (rešenja) - to je često rešavano keširanje posećenih čvorova. IDA* je izmenjena poboljšanjem memorijske složenosti IDA* (ME-IDA*), jer koristi neka skladištenja. Osim toga, IDA* radi sve prethodne radnje u potrazi koja se ponavlja, što je neophodno za rad bez skladištenja. Skladištenjem liste čvorova prethodne iteracije i koristivši ih kao polaznu poziciju, IDA* efikasnost je značajno poboljšana (inače, u poslednjoj iteraciji uvek će morati da posete svaki čvor u drvetu).

Marginalna pretraga implementira ova poboljšanja na IDA * koristeći strukturu podataka koju predstavlja otprilike dve liste, da bi se prelazilo preko granice rese pretrage drveta. Na jednoj listi, skladišti se trenutna iteracija, a druga lista kasnije skladišti odmah sledeću iteraciju. Tako da koren čvora za pretragu drveta, sada postaje koren, a kasnije će biti prazan. Tada algoritam preduzima jednu od dve akcije: Ako je ƒ (glava) veći od trenutnog praga, izvadite sada glavu i dodajte je na kraju, odnosno sačuvajte glavu za sledeću iteraciju. U suprotnom, ako je ƒ (glava) manji ili jednak pragu, uvećaj glavu i odbaci je, uzevši u obzir prethodne radnje, dodajete je na početak sada. Na kraju jedne iteracije, prag se povećava, glava postaje sledeći čvor u listi, a stara glava se prazni.

Važna razlika između margina i A* je u tome što sadržaj listi u ne mora nužno da bude sortiran - značajan dobitak u odnosu na A*, koji zahteva često skupa održavanja poretka u njegovim otvorenim listama. Međutim, resa će morati više puta da poseti iste čvorove, ali je cena za svaku takvu posetu konstantna što je sigurno bolje u odnosu na najgori mogući slučaj sortiranja liste u A* koji zahteva logaritamsko vreme za izvršavanje.

Pseudokod

[uredi | uredi izvor]

Implementacija obe liste u jednu dvostruko povezanu listu, gde čvorovi koji prate trenutni čvor su kasniji deo a svi drugi sada prate listu. Koristeći niz prethodno dodeljenih čvorova u listi za svaki čvor u mreži, pristup svakom čvoru u listi se izvršava za konstantno vreme. Slično tome, marker niz omogućava pronalaženje nekog čvora u listi za konstantno vreme. g se čuva kao heš-tabela. 

init(start, goal)
    fringe F = s
    cache C[start] = (0, null)
    flimit = h(start)
    found = false

    while (found == false) AND (F not empty)
        fmin = ∞
        for node in F, from left to right
            (g, parent) = C[node]
            f = g + h(node)
            if f > flimit
                fmin = min(f, fmin)
                continue
            if node == goal
                found = true
                break
            for child in children(node), from right to left
                g_child = g + cost(node, child)
                if C[child] != null
                    (g_cached, parent) = C[child]
                    if g_child >= g_cached
                        continue
                if child in F
                    remove child from F
                insert child in F past node
                C[child] = (g_child, node)
            remove node from F
        flimit = fmin

    if reachedgoal == true
        reverse_path(goal)

Reverse pseudokod. 

reverse_path(node)
    (g, parent) = C[node]
    if parent != null
        reverse_path(parent)
    print node

Eksperimenti

[uredi | uredi izvor]

Pri testiranju okruženja, koja su bazirana na mrežama, tipičnih kompjuterskih igara uključujući neprohodne prepreke, rese su dale u odnosu na A* za 10 do 40 procenata bolje rezultate. Moguća poboljšanja zasnivaju se na korišćenju specijalnih struktura podataka koje se jednostavnije keširaju.

Literatura

[uredi | uredi izvor]
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Маргинална_претрага&oldid=28435023”