Пређи на садржај

Маргинална претрага

С Википедије, слободне енциклопедије

Маргинална претрага припада класи алгоритама за претрагу графова, која проналази пут најмање тежине између задатог чвора и циљног.

Алгоритам

[уреди | уреди извор]

Ако g(x) је цена претраживања од првог чвора до текућег и ако х(x) је хеуристичка процена цене од текућег чвора до циљног, онда важи да је h(x) = g(x) + х(x) и да је х* текућа цена претраге до циљног чвора. Размислите IDA* која рекурзивно иде слева надесно (Претрага у дубину) из корена чвора, и зауставља се кад пронађе циљни чвор или чворови постигну максималну вредност ƒ. Ако се циљ не налази у првом прагу ƒ, праг се тада повећава и поново се покреће алгоритам претраге, тј. он понавља претрагу.

Постоје три главне неефикасности IDA*. Прво, IDA* ће поновити алгоритам када има више (понекад нису оптималне) путања до циљног чвора (решења) - то је често решавано кеширање посећених чворова. IDA* је измењена побољшањем меморијске сложености IDA* (МЕ-IDA*), јер користи нека складиштења. Осим тога, IDA* ради све претходне радње у потрази која се понавља, што је неопходно за рад без складиштења. Складиштењем листе чворова претходне итерације и користивши их као полазну позицију, IDA* ефикасност је значајно побољшана (иначе, у последњој итерацији увек ће морати да посете сваки чвор у дрвету).

Маргинална претрага имплементира ова побољшања на ИДА * користећи структуру података коју представља отприлике две листе, да би се прелазило преко границе ресе претраге дрвета. На једној листи, складишти се тренутна итерација, а друга листа касније складишти одмах следећу итерацију. Тако да корен чвора за претрагу дрвета, сада постаје корен, а касније ће бити празан. Тада алгоритам предузима једну од две акције: Ако је ƒ (глава) већи од тренутног прага, извадите сада главу и додајте је на крају, односно сачувајте главу за следећу итерацију. У супротном, ако је ƒ (глава) мањи или једнак прагу, увећај главу и одбаци је, узевши у обзир претходне радње, додајете је на почетак сада. На крају једне итерације, праг се повећава, глава постаје следећи чвор у листи, а стара глава се празни.

Важна разлика између маргина и А* је у томе што садржај листи у не мора нужно да буде сортиран - значајан добитак у односу на А*, који захтева често скупа одржавања поретка у његовим отвореним листама. Међутим, реса ће морати више пута да посети исте чворове, али је цена за сваку такву посету константна што је сигурно боље у односу на најгори могући случај сортирања листе у А* који захтева логаритамско време за извршавање.

Псеудокод

[уреди | уреди извор]

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

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 псеудокод. 

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

Експерименти

[уреди | уреди извор]

При тестирању окружења, која су базирана на мрежама, типичних компјутерских игара укључујући непроходне препреке, ресе су дале у односу на А* за 10 до 40 процената боље резултате. Могућа побољшања заснивају се на коришћењу специјалних структура података које се једноставније кеширају.

Литература

[уреди | уреди извор]
Преузето из „https://sr.wikipedia.org/w/index.php?title=Маргинална_претрага&oldid=28435023”