Претрага ресицама

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

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

Алгоритам[уреди]

Ако 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 процената боље резултате. Могућа побољшања заснивају се на коришћењу специјалних структура података које се једноставније кеширају.

Референце[уреди]

  • Björnsson, Yngvi; Enzenberger, Markus; Holte, Robert C.; Schaeffer, Johnathan. Fringe Search: Beating A* at Pathfinding on Game Maps. Proceedings of the 2005 IEEE Symposium on Computational Intelligence and Games (CIG05). Essex University, Colchester, Essex, UK, 4–6 April, 2005. IEEE 2005. http://www.cs.ualberta.ca/~games/pathfind/publications/cig2005.pdf

Спољашње везе[уреди]