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

Алгоритам 

Ако 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. https://web.archive.org/web/20090219220415/http://www.cs.ualberta.ca/~games/pathfind/publications/cig2005.pdf

Спољашње везе 
 Xiaoxun Sun & Sven Koenig's publication on fringe search https://web.archive.org/web/20160303231907/http://www-scf.usc.edu/~xiaoxuns/IJCAI07-385.pdf

Графовски алгоритми
У информатици , претрага ресицама припада класи алгоритама за претрагу графова , он проналази пут најмање тежине између задатог чвора и циљног . Алгоритам Ако 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 ] = 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 Експерименти При тестирању окружења , која су базирана на мрежама , типичних компјутерских игара укључујући непроходне препреке , ресе су дале у односу на А * задопроцената боље резултате . Могућа побољшања заснивају се на коришћењу специјалних структура података које се једноставније кеширају . Референце Björnsson , Yngvi ; Enzenberger , Markus ; Holte , Robert C . ; Schaeffer , Johnathan . Fringe Search : Beating A * at Pathfinding on Game Maps . Proceedings of theIEEE Symposium on Computational Intelligence and Games ( CIG05 ) . Essex University , Colchester , Essex , UK ,6 April , IEEE https://web.archive.org/web/20090219220415/http://www.cs.ualberta.ca/ ~games / pathfind / publications / cig2005.pdf Спољашње везе Xiaoxun Sun & Sven Koenig's publication on fringe search https://web.archive.org/web/20160303231907/http://www-scf.usc.edu/ ~xiaoxuns / IJCAI07-385.pdf Графовски алгоритми