Неінформований пошук — це клас алгоритмів пошуку загального призначення, які працюють методом грубої сили. Неінформовані алгоритми пошуку не мають додаткової інформації про стан або простір пошуку, окрім того, як обійти дерево, тому їх також називають сліпим пошуком.
Нижче наведено різні типи неінформованих алгоритмів пошуку:
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 є вузлом у кожному стані.
T (b) = 1+b2+б3+......+ бd= O (bd)
Космічна складність: Просторова складність алгоритму BFS визначається розміром межі пам’яті, який дорівнює O(bd).
Повнота: BFS завершено, що означає, що якщо найдрібніший цільовий вузол знаходиться на деякій кінцевій глибині, BFS знайде рішення.
Оптимальність: BFS є оптимальним, якщо вартість шляху є неспадною функцією глибини вузла.
2. Пошук у глибину
- Пошук у глибину — це рекурсивний алгоритм для обходу структури даних дерева або графа.
- Його називають пошуком у глибину, тому що він починається з кореневого вузла та йде по кожному шляху до його найбільшого вузла глибини перед переходом до наступного шляху.
- DFS використовує стекову структуру даних для своєї реалізації.
- Процес алгоритму DFS подібний до алгоритму BFS.
Примітка. Зворотне відстеження — це метод алгоритму для пошуку всіх можливих рішень за допомогою рекурсії.
Перевага:
- DFS потребує набагато менше пам’яті, оскільки їй потрібно лише зберігати стек вузлів на шляху від кореневого вузла до поточного вузла.
- Для досягнення цільового вузла потрібно менше часу, ніж для алгоритму BFS (якщо він проходить по правильному шляху).
Недолік:
- Існує ймовірність того, що багато станів продовжують виникати знову, і немає гарантії знайти рішення.
- Алгоритм DFS виконує глибокий пошук і іноді може переходити до нескінченного циклу.
приклад:
У наведеному нижче дереві пошуку ми показали потік пошуку в глибину, і він буде відповідати такому порядку:
Кореневий вузол--->Лівий вузол ----> правий вузол.
Він розпочне пошук із кореневого вузла S і обійде A, потім B, потім D і E, після обходу E, він повернеться до дерева, оскільки E не має іншого наступника, а цільовий вузол все ще не знайдено. Після зворотного відстеження він пройде вузол C, а потім G, і тут він завершиться, коли знайде цільовий вузол.
оператор java
Повнота: Алгоритм пошуку DFS є завершеним у скінченному просторі станів, оскільки він розширює кожен вузол у межах обмеженого дерева пошуку.
Часова складність: Часова складність DFS буде еквівалентна вузлу, пройденому алгоритмом. Він надається:
T(n)= 1+ n2+ п3+.........+ пм=O(nм)
Де m = максимальна глибина будь-якого вузла, і вона може бути набагато більшою за d (найменша глибина рішення)
діаграма моделі e-r
Космічна складність: Алгоритм DFS повинен зберігати лише один шлях від кореневого вузла, тому складність простору DFS еквівалентна розміру набору країв, який є O(bm) .
Оптимальний: Алгоритм пошуку DFS є неоптимальним, оскільки він може генерувати велику кількість кроків або високу вартість для досягнення цільового вузла.
3. Алгоритм пошуку з обмеженою глибиною:
Алгоритм пошуку з обмеженою глибиною подібний до пошуку в глибину із заздалегідь визначеним обмеженням. Пошук з обмеженою глибиною може вирішити недолік нескінченного шляху в пошуку з першою глибиною. У цьому алгоритмі вузол на межі глибини розглядатиметься як не має наступних вузлів.
Пошук з обмеженою глибиною може бути припинено за наявності двох умов невдачі:
- Стандартне значення помилки: вказує на те, що проблема не має вирішення.
- Граничне значення невдачі: не визначає вирішення проблеми в межах заданої межі глибини.
Переваги:
Пошук з обмеженою глибиною ефективний для пам’яті.
Недоліки:
- Пошук з обмеженою глибиною також має недолік неповноти.
- Це може бути не оптимальним, якщо проблема має більше ніж одне рішення.
приклад:
Повнота: Алгоритм пошуку DLS завершується, якщо рішення перевищує межу глибини.
Часова складність: Часова складність алгоритму DLS становить O(bℓ) .
Космічна складність: Просторова складність алгоритму DLS становить O (b�ℓ) .
Оптимальний: Пошук з обмеженою глибиною можна розглядати як окремий випадок DFS, і він також не є оптимальним, навіть якщо ℓ>d.
4. Алгоритм пошуку за рівномірною вартістю:
Пошук за рівномірною вартістю — це алгоритм пошуку, який використовується для обходу зваженого дерева або графа. Цей алгоритм вступає в дію, коли для кожного краю доступна різна вартість. Основною метою пошуку з рівномірною вартістю є пошук шляху до цільового вузла, який має найменшу сукупну вартість. Пошук за рівномірною вартістю розширює вузли відповідно до вартості їх шляху від кореневого вузла. Його можна використовувати для вирішення будь-якого графа/дерева, де потрібна оптимальна вартість. Алгоритм пошуку з рівномірною вартістю реалізований пріоритетною чергою. Він надає максимальний пріоритет найнижчим сукупним витратам. Рівномірний пошук за вартістю еквівалентний алгоритму BFS, якщо вартість шляху всіх ребер однакова.
Переваги:
- Рівномірний пошук за вартістю є оптимальним, оскільки в кожному стані вибирається шлях з найменшими витратами.
Недоліки:
- Він не дбає про кількість кроків, пов’язаних з пошуком, а лише про вартість шляху. Через що цей алгоритм може застрягти в нескінченному циклі.
приклад:
Повнота:
Пошук за рівномірною вартістю завершено, наприклад, якщо є рішення, UCS знайде його.
Часова складність:
Нехай C* Вартість оптимального рішення , і д це кожен крок, щоб наблизитися до цільового вузла. Тоді кількість кроків = C*/ε+1. Тут ми взяли +1, оскільки ми починаємо від стану 0 і закінчуємо до C*/ε.
Отже, найгірша часова складність пошуку за рівномірною вартістю O(b1 + [C*/e])/ .
Космічна складність:
Така сама логіка стосується просторової складності, тому найгірший випадок просторової складності пошуку за рівномірною вартістю O(b1 + [C*/e]) .
Оптимальний:
Пошук за рівномірною вартістю завжди є оптимальним, оскільки він вибирає лише шлях із найнижчою вартістю шляху.
масив c рядок
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, тоді часова складність у найгіршому випадку дорівнює O(bd) .
Космічна складність:
Космічна складність IDDFS буде O(bd) .
Оптимальний:
Алгоритм IDDFS є оптимальним, якщо вартість шляху є неспадною функцією глибини вузла.
панда тане
6. Алгоритм двонаправленого пошуку:
Алгоритм двонаправленого пошуку виконує два одночасні пошуки, один у початковому стані, який називається пошуком уперед, а інший від цільового вузла, який називається зворотним пошуком, щоб знайти цільовий вузол. Двонаправлений пошук замінює один граф пошуку двома невеликими підграфами, в яких один починає пошук із початкової вершини, а інший – із цільової вершини. Пошук припиняється, коли ці два графіки перетинаються.
Двонаправлений пошук може використовувати такі методи пошуку, як BFS, DFS, DLS тощо.
Переваги:
- Швидкий двонаправлений пошук.
- Двонаправлений пошук вимагає менше пам'яті
Недоліки:
- Реалізація двонаправленого дерева пошуку складна.
приклад:
У наведеному нижче дереві пошуку застосовано двонаправлений алгоритм пошуку. Цей алгоритм ділить один граф/дерево на два підграфи. Він починає рух від вузла 1 у прямому напрямку та починається від цільового вузла 16 у зворотному напрямку.
Алгоритм завершується на вузлі 9, де зустрічаються два пошуки.
Повнота: Двонаправлений пошук завершується, якщо ми використовуємо BFS в обох пошуках.
Часова складність: Часова складність двонаправленого пошуку за допомогою BFS становить O(bd) .
Космічна складність: Просторова складність двонаправленого пошуку O(bd) .
Оптимальний: Двонаправлений пошук є оптимальним.