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

азбука на бројеве

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

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

1. Претрага у ширину:

• Претрага у ширину је најчешћа стратегија претраживања за обилажење дрвета или графикона. Овај алгоритам претражује у ширину у стаблу или графу, па се назива претрага у ширину.
• БФС алгоритам почиње претрагу од коренског чвора стабла и проширује све чворове наследнике на тренутном нивоу пре него што пређе на чворове следећег нивоа.
• Алгоритам претраге у ширину је пример општег алгоритма за претрагу графа.
• Претрага у ширину имплементирана коришћењем ФИФО структуре података реда.

Предности:

• БФС ће пружити решење ако постоји било какво решење.
• Ако постоји више од једног решења за дати проблем, онда ће БФС обезбедити минимално решење које захтева најмањи број корака.

Недостаци:

• Захтева много меморије пошто сваки ниво стабла мора бити сачуван у меморији да би се проширио следећи ниво.
• БФС-у је потребно много времена ако је решење далеко од коренског чвора.

Пример:

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

 S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K 

Временска сложеност: Временска сложеност БФС алгоритма се може добити бројем чворова пређених у БФС до најплићег чвора. Где је д= дубина најплићег решења и б је чвор у сваком стању.

Т (б) = 1+б²+б³+.......+ б^д= О (б^д)

Сложеност простора: Сложеност простора БФС алгоритма је дата величином границе меморије која је О(б^д).

Комплетност: БФС је потпун, што значи да ако је најплићи циљни чвор на некој коначној дубини, онда ће БФС пронаћи решење.

Оптималност: БФС је оптималан ако је цена путање неопадајућа функција дубине чвора.

2. Претрага у дубину

• Претрага у дубину је рекурзивни алгоритам за прелажење структуре података стабла или графикона.
• Зове се претрага по дубини јер почиње од коренског чвора и прати сваку путању до свог највећег дубински чвора пре него што пређе на следећу путању.
• ДФС користи структуру података стека за своју имплементацију.
• Процес ДФС алгоритма је сличан БФС алгоритму.

Напомена: Враћање уназад је алгоритамска техника за проналажење свих могућих решења помоћу рекурзије.

предност:

• ДФС захтева веома мање меморије јер треба само да ускладишти гомилу чворова на путу од основног чвора до тренутног чвора.
• Потребно је мање времена да се дође до циљног чвора него БФС алгоритам (ако се креће на правом путу).

Недостатак:

• Постоји могућност да се многе државе понављају и нема гаранције да ће се наћи решење.
• ДФС алгоритам иде за дубоко претраживање и понекад може отићи у бесконачну петљу.

Пример:

У стаблу претраге испод, приказали смо ток претраге у дубину, и он ће пратити редослед као:

Коренски чвор--->леви чвор ----> десни чвор.

Почеће да тражи од коренског чвора С, и прелази А, затим Б, затим Д и Е, након што пређе Е, вратиће се стаблом уназад јер Е нема другог наследника и још увек циљни чвор није пронађен. Након враћања уназад, он ће прећи чвор Ц, а затим Г, и овде ће се прекинути када је пронашао циљни чвор.

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

Временска сложеност: Временска сложеност ДФС-а ће бити еквивалентна чвору који прелази алгоритам. Даје га:

Т(н)= 1+ н²+ н³+.........+ н^м=О(н^м)

Где је м= максимална дубина било ког чвора и ово може бити много веће од д (најплића дубина решења)

Сложеност простора: ДФС алгоритам треба да складишти само једну путању од коренског чвора, стога је просторна сложеност ДФС-а еквивалентна величини рубног скупа, што је О томе .

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

3. Алгоритам претраге ограничен на дубину:

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

Претрага ограничена на дубину може се прекинути са два услова неуспеха:

• Стандардна вредност грешке: Указује на то да проблем нема решење.
• Вредност граничне грешке: Не дефинише решење за проблем унутар дате границе дубине.

Предности:

Претрага ограничена на дубину је ефикасна за меморију.

Недостаци:

• Претраживање ограничено на дубину такође има недостатак непотпуности.
• Можда неће бити оптимално ако проблем има више од једног решења.

Пример:

Комплетност: ДЛС алгоритам претраге је завршен ако је решење изнад границе дубине.

Временска сложеност: Временска сложеност ДЛС алгоритма је О(б^ℓ) .

Сложеност простора: Просторна сложеност ДЛС алгоритма је О (б�ℓ) .

Оптимално: Претрага ограничена на дубину може се посматрати као посебан случај ДФС-а, а такође није оптимална чак и ако је ℓ>д.

4. Алгоритам за претрагу уједначених трошкова:

Претрага по униформним трошковима је алгоритам претраживања који се користи за прелазак пондерисаног стабла или графикона. Овај алгоритам долази у игру када је за сваку ивицу доступна различита цена. Примарни циљ претраге униформних трошкова је проналажење пута до чвора циља који има најнижу кумулативну цену. Претрага по униформним трошковима проширује чворове у складу са њиховим трошковима путање од основног чвора. Може се користити за решавање било ког графикона/дрвета где је тражена оптимална цена. Алгоритам претраге уједначених трошкова имплементиран је редом приоритета. Максимални приоритет даје најнижим кумулативним трошковима. Униформна претрага трошкова је еквивалентна БФС алгоритму ако је цена путање свих ивица иста.

Предности:

• Униформна претрага трошкова је оптимална јер се у сваком стању бира пут са најмањим трошковима.

Недостаци:

• Није га брига за број корака који укључује претрагу и брине само о цени путање. Због чега овај алгоритам може бити заглављен у бесконачној петљи.

Пример:

Комплетност:

Претрага по униформним трошковима је завршена, на пример, ако постоји решење, УЦС ће га пронаћи.

Временска сложеност:

Нека Ц* је Цена оптималног решења , и е је сваки корак да се приближите циљном чвору. Тада је број корака = Ц*/ε+1. Овде смо узели +1, јер почињемо од стања 0 и завршавамо на Ц*/ε.

Дакле, у најгорем случају временска сложеност претраге униформних трошкова је О(б^{1 + [Ц*/е]})/ .

Сложеност простора:

кали линук команде

Иста логика је и за комплексност простора, тако да је најгори случај комплексности простора за претрагу по униформним трошковима О(б^{1 + [Ц*/е]}) .

Оптимално:

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

5. Итеративно продубљивање претраге у дубину:

Алгоритам итеративног продубљивања је комбинација ДФС и БФС алгоритама. Овај алгоритам претраживања проналази најбољу границу дубине и то чини тако што постепено повећава ограничење док се не пронађе циљ.

Овај алгоритам врши претрагу по дубини до одређене 'граничне дубине' и наставља да повећава границу дубине након сваке итерације док се не пронађе циљни чвор.

Овај алгоритам претраге комбинује предности брзе претраге у ширину и ефикасности меморије претраге прве дубине.

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

Предности:

• Комбинује предности БФС и ДФС алгоритма претраге у смислу брзе претраге и ефикасности меморије.

Недостаци:

• Главни недостатак ИДДФС-а је у томе што понавља сав рад претходне фазе.

Пример:

Следећа структура стабла приказује итеративно продубљивање претраге у дубину. ИДДФС алгоритам изводи различите итерације све док не пронађе циљни чвор. Итерација коју изводи алгоритам је дата као:

1. итерација-----> А
2. итерација----> А, Б, Ц
Трећа итерација------>А, Б, Д, Е, Ц, Ф, Г
4. итерација------>А, Б, Д, Х, И, Е, Ц, Ф, К, Г
У четвртој итерацији, алгоритам ће пронаћи циљни чвор.

Комплетност:

Овај алгоритам је потпун ако је фактор гранања коначан.

Временска сложеност:

Претпоставимо да је б фактор гранања, а дубина д, тада је временска сложеност у најгорем случају О(б^д) .

Сложеност простора:

Просторна сложеност ИДДФС ће бити О(бд) .

Оптимално:

ИДДФС алгоритам је оптималан ако је цена путање неопадајућа функција дубине чвора.

6. Алгоритам двосмерне претраге:

Алгоритам двосмерне претраге покреће две истовремене претраге, једно од почетног стања које се зове унапред-претрага, а друго из чвора циља који се назива претрага уназад, да пронађе циљни чвор. Двосмерна претрага замењује један граф претраге са два мала подграфа у којима један почиње претрагу од почетног врха, а други од циљног врха. Претрага се зауставља када се ова два графикона пресеку.

Двосмерна претрага може да користи технике претраге као што су БФС, ДФС, ДЛС итд.

Предности:

• Двосмерна претрага је брза.
• Двосмерна претрага захтева мање меморије

Недостаци:

• Имплементација двосмерног стабла претраге је тешка.
Код двосмерне претраге треба унапред знати циљно стање.

Пример:

У доњем стаблу претраге примењен је двосмерни алгоритам претраге. Овај алгоритам дели један граф/стабло на два подграфа. Почиње да се креће од чвора 1 у правцу напред и почиње од циљног чвора 16 у правцу уназад.

Алгоритам се завршава на чвору 9 где се сусрећу две претраге.

Комплетност: Двосмерна претрага је потпуна ако користимо БФС у обе претраге.

Временска сложеност: Временска сложеност двосмерног претраживања коришћењем БФС је О(б^д) .

Сложеност простора: Просторна сложеност двосмерног претраживања је О(б^д) .

Оптимално: Двосмерна претрага је оптимална.