Back

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




                                     

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

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

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

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

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

                                     

1. Псеудокод

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

initstart, goal fringe F = s cache C if parent!= null reverse_pathparent print node
                                     

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

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

                                     

3. Референце

  • 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.

Users also searched:

...