Неинформираното търсене е клас алгоритми за търсене с общо предназначение, които работят по метода на груба сила. Алгоритмите за неинформирано търсене нямат допълнителна информация за състоянието или пространството за търсене, освен как да преминат през дървото, така че се нарича още сляпо търсене.

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

Търсене в ширина Търсене в дълбочина Търсене с ограничена дълбочина Итеративно задълбочаващо се търсене в дълбочина Единно търсене на разходите Двупосочно търсене

1. Търсене в ширина:

• Търсенето в ширина е най-честата стратегия за търсене за преминаване през дърво или графика. Този алгоритъм търси в ширина в дърво или графика, така че се нарича търсене в ширина.
• BFS алгоритъмът започва търсене от коренния възел на дървото и разширява всички последващи възли на текущото ниво, преди да премине към възли на следващото ниво.
• Алгоритъмът за търсене в ширина е пример за алгоритъм за търсене с обща графика.
• Търсене в ширина, реализирано с помощта на FIFO структура от данни на опашка.

Предимства:

• BFS ще предостави решение, ако съществува такова.
• Ако има повече от едно решения за даден проблем, тогава BFS ще предостави минималното решение, което изисква най-малко стъпки.

Недостатъци:

• Изисква много памет, тъй като всяко ниво на дървото трябва да бъде запазено в паметта, за да се разшири следващото ниво.
• BFS се нуждае от много време, ако решението е далеч от основния възел.

Пример:

В структурата на дървото по-долу сме показали преминаването на дървото с помощта на BFS алгоритъм от основния възел S до целевия възел K. Алгоритъмът за търсене на BFS преминава на слоеве, така че ще следва пътя, който е показан от пунктираната стрелка, и изминатият път ще бъде:

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

Времева сложност: Времевата сложност на алгоритъма BFS може да се получи чрез броя на възлите, преминати в BFS до най-плитката възлова точка. Където d = дълбочина на най-плиткото решение и b е възел във всяко състояние.

лента с инструменти за бърз достъп до word

T (b) = 1+b²+б³+.......+ б^д= O (b^д)

Космическа сложност: Пространствената сложност на BFS алгоритъма се дава от размера на паметта на границата, който е O(b^д).

Пълнота: BFS е завършен, което означава, че ако най-плитката целева точка е на някаква крайна дълбочина, тогава BFS ще намери решение.

Оптималност: BFS е оптимален, ако цената на пътя е ненамаляваща функция на дълбочината на възела.

2. Търсене в дълбочина

• Търсенето първо в дълбочина е рекурсивен алгоритъм за преминаване през дървовидна или графична структура от данни.
• Нарича се търсене първо в дълбочина, защото започва от основния възел и следва всеки път до възела с най-голяма дълбочина, преди да премине към следващия път.
• DFS използва стекова структура от данни за своята реализация.
• Процесът на алгоритъма DFS е подобен на алгоритъма BFS.

Забележка: Backtracking е алгоритъмна техника за намиране на всички възможни решения с помощта на рекурсия.

Предимство:

• DFS изисква много по-малко памет, тъй като трябва да съхранява само стек от възли по пътя от основния възел до текущия възел.
• Отнема по-малко време за достигане до целевия възел от BFS алгоритъма (ако преминава по правилния път).

Недостатък:

• Има възможност много състояния да се появяват отново и няма гаранция за намиране на решението.
• DFS алгоритъмът отива за дълбоко търсене и понякога може да премине към безкраен цикъл.

Пример:

В дървото за търсене по-долу сме показали потока на търсене в дълбочина и той ще следва реда като:

Основен възел--->Ляв възел ----> десен възел.

Той ще започне да търси от коренния възел S и ще пресече A, след това B, след това D и E, след като обходи E, ще върне дървото назад, тъй като E няма друг наследник и все още целевият възел не е намерен. След връщане назад той ще пресече възел C и след това G и тук ще приключи, когато намери целевия възел.

Пълнота: Алгоритъмът за търсене на DFS е завършен в ограниченото пространство на състоянието, тъй като ще разшири всеки възел в рамките на ограничено дърво за търсене.

Времева сложност: Времевата сложност на DFS ще бъде еквивалентна на възела, преминат от алгоритъма. Дава се от:

T(n)= 1+ n²+ н³+.........+ п^м=O(n^м)

Където m = максимална дълбочина на всеки възел и това може да бъде много по-голямо от d (най-плитка дълбочина на решение)

Космическа сложност: DFS алгоритъмът трябва да съхранява само един път от основния възел, следователно пространствената сложност на DFS е еквивалентна на размера на набора от ръбове, който е относно .

Оптимално: Алгоритъмът за търсене на DFS не е оптимален, тъй като може да генерира голям брой стъпки или висока цена за достигане до целевия възел.

3. Алгоритъм за търсене с ограничена дълбочина:

Алгоритъмът за търсене с ограничена дълбочина е подобен на търсенето първо в дълбочина с предварително зададено ограничение. Търсенето с ограничена дълбочина може да разреши недостатъка на безкрайния път при търсенето с първа дълбочина. В този алгоритъм възелът на границата на дълбочината ще се третира като няма последващи възли по-нататък.

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

• Стандартна стойност на грешка: Показва, че проблемът няма решение.
• Стойност на грешка при прекъсване: не определя решение за проблема в рамките на дадена граница на дълбочината.

Предимства:

Търсенето с ограничена дълбочина е ефективно за паметта.

Недостатъци:

• Търсенето с ограничена дълбочина също има недостатък на непълнотата.
• Може да не е оптимално, ако проблемът има повече от едно решение.

Пример:

Пълнота: Алгоритъмът за търсене на DLS е завършен, ако решението е над границата на дълбочината.

10 от 60

Времева сложност: Времевата сложност на DLS алгоритъма е О(б^ℓ) .

Космическа сложност: Пространствената сложност на DLS алгоритъма е O (b�ℓ) .

Оптимално: Търсенето с ограничена дълбочина може да се разглежда като специален случай на DFS и също така не е оптимално дори ако ℓ>d.

4. Алгоритъм за търсене с еднаква цена:

Търсенето с еднаква цена е алгоритъм за търсене, използван за обхождане на претеглено дърво или графика. Този алгоритъм влиза в действие, когато има различна цена за всеки край. Основната цел на търсенето с еднакви разходи е да се намери път до целевия възел, който има най-ниската кумулативна цена. Търсенето с унифицирани разходи разширява възлите според техните разходи за път от основния възел. Може да се използва за решаване на всяка графика/дърво, където се търси оптимална цена. Алгоритъм за търсене с еднаква цена се изпълнява от опашката с приоритет. Той дава максимален приоритет на най-ниските кумулативни разходи. Еднообразното търсене на разходи е еквивалентно на BFS алгоритъм, ако цената на пътя на всички ръбове е една и съща.

Предимства:

• Еднообразното търсене на разходи е оптимално, тъй като при всяко състояние се избира пътят с най-малко разходи.

Недостатъци:

• Не се интересува от броя на стъпките, включени в търсенето, а се интересува само от цената на пътя. Поради което този алгоритъм може да остане в безкраен цикъл.

Пример:

Пълнота:

Търсенето с еднакви разходи е завършено, например ако има решение, UCS ще го намери.

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

Нека C* е цената на оптималното решение , и д е всяка стъпка за приближаване до възела на целта. Тогава броят на стъпките е = C*/ε+1. Тук сме взели +1, тъй като започваме от състояние 0 и завършваме до C*/ε.

Следователно най-лошият случай на времева сложност на търсенето с равни разходи е О(б^{1 + [C*/e]})/ .

Космическа сложност:

Същата логика е и за сложността на пространството, така че най-лошият случай на пространствена сложност на търсенето с еднаква цена е О(б^{1 + [C*/e]}) .

Оптимално:

css непрозрачност на прехода

Търсенето с еднаква цена винаги е оптимално, тъй като избира само път с най-ниска цена на пътя.

5. Итеративно задълбочаване първо търсене в дълбочина:

Алгоритъмът за итеративно задълбочаване е комбинация от DFS и BFS алгоритми. Този алгоритъм за търсене открива най-доброто ограничение на дълбочината и го прави чрез постепенно увеличаване на ограничението, докато се намери цел.

Този алгоритъм извършва първо търсене в дълбочина до определена „лимит на дълбочина“ и продължава да увеличава лимита на дълбочина след всяка итерация, докато не бъде намерен целевият възел.

Този алгоритъм за търсене съчетава предимствата на бързото търсене при търсене в ширина и ефективността на паметта при търсене в дълбочина.

Алгоритъмът за итеративно търсене е полезен при неинформирано търсене, когато пространството за търсене е голямо и дълбочината на целевия възел е неизвестна.

Предимства:

• Комбинира предимствата на алгоритъма за търсене на BFS и DFS по отношение на бързо търсене и ефективност на паметта.

Недостатъци:

• Основният недостатък на IDDFS е, че повтаря цялата работа от предишната фаза.

Пример:

Следващата дървовидна структура показва итеративното задълбочаване на първо търсене в дълбочина. IDDFS алгоритъмът изпълнява различни итерации, докато не намери целевия възел. Итерацията, извършена от алгоритъма, е дадена като:

1-ва итерация-----> A
2-ра итерация----> A, B, C
3-та итерация------>A, B, D, E, C, F, G
4-та итерация------>A, B, D, H, I, E, C, F, K, G
В четвъртата итерация алгоритъмът ще намери целевия възел.

Пълнота:

Този алгоритъм е завършен, ако факторът на разклоняване е краен.

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

Да предположим, че b е факторът на разклоняване и дълбочината е d, тогава най-лошият случай на времева сложност е О(б^д) .

Космическа сложност:

Космическата сложност на IDDFS ще бъде O(bd) .

Оптимално:

нишка.унищожавам

IDDFS алгоритъмът е оптимален, ако цената на пътя е ненамаляваща функция на дълбочината на възела.

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

Алгоритъмът за двупосочно търсене изпълнява две едновременни търсения, едно от началното състояние, наречено търсене напред, и друго от целеви възел, наречено търсене назад, за да намери целевия възел. Двупосочното търсене заменя един единствен график за търсене с два малки подграфа, в които единият започва търсенето от начален връх, а другият започва от целевия връх. Търсенето спира, когато тези две графики се пресичат.

Двупосочното търсене може да използва техники за търсене като BFS, DFS, DLS и др.

Предимства:

• Двупосочното търсене е бързо.
• Двупосочното търсене изисква по-малко памет

Недостатъци:

• Внедряването на дървото за двупосочно търсене е трудно.
При двупосочно търсене човек трябва предварително да знае състоянието на целта.

Пример:

В дървото за търсене по-долу се прилага двупосочен алгоритъм за търсене. Този алгоритъм разделя един график/дърво на два подграфа. Започва преминаване от възел 1 в посока напред и започва от целеви възел 16 в посока назад.

Алгоритъмът завършва на възел 9, където се срещат две търсения.

Пълнота: Двупосочното търсене е пълно, ако използваме BFS и в двете търсения.

Времева сложност: Времевата сложност на двупосочното търсене с помощта на BFS е О(б^д) .

Космическа сложност: Пространствената сложност на двупосочното търсене е О(б^д) .

Оптимално: Двупосочното търсене е оптимално.