Садржај

• Упоредни графикон
• Дефиниција информисане претраге
• Прва претрага хеуристичке дубине
• Дефиниција неинформисане претраге
• Дубина прва претрага
• Закључак

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

Међутим, између информисане и неинформисане технике претраживања, обавештена претрага је ефикаснија и економичнија.

1. 1. Упоредни графикон
   2. Дефиниција
   3. Кључне разлике
   4. Закључак

Упоредни графикон

Основе за поређење	Информед Сеарцх	Неинформисана претрага
Основни	Користи знање за проналажење корака до решења.	Нема користи од знања
Ефикасност	Високо ефикасан јер троши мање времена и трошкова.	Ефикасност је посредничка
Трошак	Ниска	Релативно висок
Перформансе	Брже проналази решење	Брзина је спорија од претраживане информисане
Алгоритми	Хеуристичка дубина прво и најпре ширина и А * претрага	Прва дубина, прва претраживања и најнижа цена прве претраге

Дефиниција информисане претраге

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

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

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

Прва претрага хеуристичке дубине

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

Други алгоритам информисаног претраживања је А * претрага који спаја концепт најнижих цена прве и најбоље прве претраге. Ова метода узима у обзир и трошкове пута и хеуристичке информације у процесу претраге и избора пута који треба проширити. Процијењени укупни трошак путање који се користи за сваку стазу која се налази на граници од почетка до циљаног чвора. Стога истовремено користи двије функције - трошак (п) је трошак откривене путање и х (п) је процијењена вриједност трошкова путање од почетног чвора до циљаног чвора.

Дефиниција неинформисане претраге

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

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

Дубина прва претрага

Приликом дубинске претраге, сноп Ласт ин фирст оут користи се за додавање и уклањање чворова. Само један чвор додаје се или уклања истовремено, а први елемент уклоњен са границе стака би био последњи елемент који је додан у низ. Употребом снопа на граници резултат је прво тражење дубине. Када се претражује најкраћи и оптимални пут употребом прве претраге дубине, пут који креирају сусједни чворови прво се довршава чак и ако није жељени. Тада се тражи алтернативни пут повратним траком.

Другим речима, алгоритам бира прву алтернативу на сваком чвору, а затим враћа другу алтернативу док не пређе све стазе из прве селекције. Ово такође ствара проблем где претрага може престати да престаје због бесконачних петљи (циклуса) присутних на графикону.

1. Бивша информисана техника претраживања користи знање како би пронашла рјешење. Са друге стране, последња неинформисана техника претраживања не користи знање. Једноставније речено, не постоје додатне информације о рјешењу.
2. Ефикасност информисане претраге је боља од неинформисане претраге.
3. Неинформисана претрага троши више времена и трошкова јер нема појма о решењу у односу на информисану претрагу.
4. Претрага по дубини, прва потрага и најнижа цена прве претраге су алгоритми који се налазе у категорији неинформисане претраге. Насупрот томе, информисана претрага обухвата алгоритме као што су хеуристичка дубина прво, хеуристичка ширина-прва претрага и А * претрага.

Закључак

Информисана претрага даје смер у вези са решењем, док код неинформисане претраге није дат предлог за решење. То чини неинформисану претрагу дужим када се алгоритам имплементира.