Рецоммендед, 2020

Избор Уредника

Разлика између информисаног и неинформисаног претраживања

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

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

Цомпарисон Цхарт

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Кључне разлике између информисаног и неинформисаног претраживања

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

Закључак

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

Top