TechCodeview

Алгоритми за претрагу су једна од најважнијих области вештачке интелигенције. Ова тема ће објаснити све о алгоритмима претраживања у АИ.

Агенти за решавање проблема:

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

Терминологије алгоритма претраге:

Претрага:Претраживање је поступак корак по корак за решавање проблема претраге у датом простору претраге. Проблем претраге може имати три главна фактора:
Простор за претрагу:Простор за претрагу представља скуп могућих решења која систем може имати.Почетно стање:То је стање одакле агент почиње Претрага .Тест гола:То је функција која посматра тренутно стање и враћа да ли је циљно стање постигнуто или не.
дрво претраге:Стабло представљања проблема претраге назива се дрво претраге. Корен стабла претраге је коренски чвор који одговара почетном стању.Радње:Агенту даје опис свих доступних радњи.Прелазни модел:Опис онога што свака акција ради, може се представити као прелазни модел.Цена пута:То је функција која свакој путањи додељује нумеричку цену.Решење:То је секвенца акција која води од почетног чвора до циљног чвора.Оптимално решење:Ако решење има најнижу цену међу свим решењима.

Својства алгоритама претраге:

Следе четири битна својства алгоритама претраге за упоређивање ефикасности ових алгоритама:

Комплетност: За алгоритам претраге се каже да је потпун ако гарантује да ће вратити решење ако постоји бар било које решење за било који случајни унос.

Оптималност: Ако је решење пронађено за алгоритам гарантовано најбоље решење (најнижа цена путање) међу свим осталим решењима, онда се за такво решење за каже да је оптимално решење.

Временска сложеност: Временска сложеност је мера времена за алгоритам да заврши свој задатак.

Сложеност простора: То је максимални простор за складиштење потребан у било ком тренутку током претраге, с обзиром на сложеност проблема.

Врсте алгоритама претраживања

На основу проблема претраге можемо класификовати алгоритме претраживања на неинформисано (слепо претраживање) претрагу и информисано претраживање (хеуристичко претраживање) алгоритме.

Необавештени/слепи трагови:

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

Може се поделити у пет главних типова:

• Претрага у ширину
• Једнообразна претрага трошкова
• Претрага у дубину
• Итеративно продубљивање претраге у дубину
• Двосмерна претрага

Информед Сеарцх

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

Хеуристика је начин за који можда није увек загарантована најбоља решења, али је загарантовано да се нађе добро решење у разумном времену.

Информисана претрага може да реши много сложених проблема који се не могу решити на други начин.

Пример информисаних алгоритама претраге је проблем трговачког путника.

1. Грееди Сеарцх
2. Потрага