Претрага о јединственом трошку
 | Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
У информатици, појам претрага о јединственом трошку представља претраживачки алгоритам који се користи за посећивање и претраживање стабла, структуре у облику стабла или графа. Претрага почиње од корена. Претрага се наставља посећивањем следећег најближег чвора са најнижим укупним трошком у односу на корен. Чворови се један за другим посећују на овај начин све док се не достигне задато стање.
Алгоритам за претраживање обично подразумева проширивање чворова додавањем свих непроширених суседних чворова који су директним путањама повезани са приоритетним низом. У овом низу, сваком чвору се додељује његов укупни трошак путање од корена, а путање са најнижим трошком имају приоритет. Чвор са врха низа се тако проширује, додавањем наредног сета повезаних чворова укупном трошку путање од корена до одговорајућег чвора. Претрага о јединственом трошку је комплетна и оптимална само ако трошак сваког од корака превазилази неку позитивну границу ε.[1]Најгори вид комплексности времена и простора је О(б1 + C*/ε), где C* представља трошак оптималног решења, а б фактор гранања. Када су трошкови свих корака једнаки, ово постаје О(бд + 1).[2]
Псеудокод[уреди | уреди извор]
procedure UniformCostSearch(Graph, root, goal)
node := root, cost = 0
frontier := priority queue containing node only
explored := empty set
do
if frontier is empty
return failure
node := frontier.pop()
if node is goal
return solution
explored.add(node)
for each of node's neighbors n
if n is not in explored
if n is not in frontier
frontier.add(n)
else if n is in frontier with higher cost
replace existing node with n
Приказ истражених сетова и границе (приоритетни низ):
Почетни чвор: А
Крајњи чвор (циљ): Г
| Корак | Граница: сет (чвор, његов трошак) објеката | Проширити [*] | Проширен: сет чворова |
|---|---|---|---|
| 1 | {(А,0)} | А | ∅ |
| 2 | {(D,3),(Б,5)} | D | {А} |
| 3 | {(Б,5),(Е,5),(Ф,5)} | Б | {А,D} |
| 4 | {(Е,5),(Ф,5),(C,6)} | Е | {А,D,Б} |
| 5 | {(Ф,5),(C,6)}[**] | Ф | {А,D,Б,Е} |
| 6 | {(C,6),(Г,8)} | C | {А,D,Б,Е,Ф} |
| 7 | {(Г,8)} | Г | {А,D,Б,Е,Ф,C} |
| 8 | ∅ |
^ * Чвор изабран за проширење у наредном кораку.
^ ** Б није додат граници зато што се налази у истраженом сету.
Пронађена путања: А до D до Ф до Г.
Повезаност са другим алгоритмима[уреди | уреди извор]
Дијкстрин алгоритам, који је вероватно познатији, може се посматрати као варијанта претраге о јединственом трошку, која нема циљано стање и где се процес наставља све док се сви чворови не уклоне из приоритетног низа, то јест, док се не установи најкраћа путања до свих чворова (а не само до крајњег (циљног) чвора). Као и Дијкстрин алгоритам, претрага о јединственом трошку такође гарантује (под условом да тежине ивица нису негативне) проналажење најкраће путање до одређеног чвора након што се чвор издвоји из приоритетног низа.
Претрага о јединственом трошку је посебан случај |А* алгоритма чија је хеуристика константна функција. Уколико се А* користи са монотоном хеуристиком, онда га можемо претворити у претрагу о јединственом трошку одузимањем са сваке ивице трошка умањења хеуристичке вредности на тој ивици. Претрага у ширину (БФС) је посебан пример претраге о јединственом трошку где су трошкови свих ивица позитивни и идентични. Где се применом БФС технике прво посећује чвор са најкраћом путањом (бројем чворова) од корена, претрага о јединственом трошку техника прво посећује чвор са најкраћим трошком путање (збир тежина ивица) од корена. Претрага о јединственом трошку представља једну од варијаната претраге за првим најбољим решењем.
Референце[уреди | уреди извор]
- ^ Русселл, Стуарт; Петер Норвиг (2003). Артифициал Интеллигенце: А Модерн Аппроацх (2нд изд.). Уппер Саддле Ривер, Неw Јерсеy: Прентице Халл. ИСБН 978-0-13-790395-5.
- ^ Русселл, Стуарт; Петер Норвиг (2010). Артифициал Интеллигенце: А Модерн Аппроацх (3рд изд.). Прентице Халл. ИСБН 978-0-13-604259-4.
Литература[уреди | уреди извор]
- Русселл, Стуарт; Петер Норвиг (2010). Артифициал Интеллигенце: А Модерн Аппроацх (3рд изд.). Прентице Халл. ИСБН 978-0-13-604259-4.
- Русселл, Стуарт; Петер Норвиг (2003). Артифициал Интеллигенце: А Модерн Аппроацх (2нд изд.). Уппер Саддле Ривер, Неw Јерсеy: Прентице Халл. ИСБН 978-0-13-790395-5.