Пошук в графах!!!
Зміст
Загальні парадигми
Перш ніж ми обговоримо деякі з неінформованих методів пошуку, давайте розглянемо два простих загальних неінформованих методи пошуку.
Перший називається "Генеруй і тестуй". У цьому методі ми генеруємо потенційне рішення, а потім перевіряємо його на відповідність. Якщо ми знайшли рішення, ми закінчили, інакше ми повторимо, спробувавши ще одне потенційне рішення. Без належного рішення ми спробуємо знову. Зауважте, що ми не відстежуємо те, що ми пробували раніше; ми просто рухаємося вперед з потенційними рішеннями, що є справжнім сліпим пошуком.
Інший варіант називається "випадковий пошук", який випадковим чином вибирає новий стан з поточного (шляхом вибору оператора та його застосування). Якщо ми досягнемо цільового стану, то пошук завершено. В іншому випадку ми випадково виберемо інший оператор (що веде до нового стану) і продовжуємо.
Випадковий пошук і метод "Генеруй та тестуй" є сліпими методами пошуку. Вони можуть привести до зациклення, і не знайти рішення, навіть якщо воно існує в пошуковому просторі.
Оцінка складності алгоритмів пошуку
Значення O-велике буде використане для порівняння алгоритмів. Ця позначка визначає асимптотичну верхню межу алгоритму з урахуванням глибини (d) дерева та коефіцієнта розгалуження або середнього числа гілок (b) з кожного вузла. Існує ряд загальних складностей, які існують для алгоритмів пошуку:
| Складність | Значення |
|---|---|
| «O» | Порядок |
| О (1) | Константа (незалежно від кількості вузлів) |
| O (n) | Лінійний (відповідно до кількості вузлів) |
| O (log n) | Логарифмічний |
| O (n^2) | Квадратичний |
| O (c^n) | Геометричний |
| O (n!) | Комбінаторний |
Позначення O-велике враховує найгірший можливий показник складності алгоритму пошуку та є звичайним інструментом порівняння для алгоритмів. Ми порівняємо алгоритми пошуку з використанням простору складності (міра пам'яті, необхідної під час пошуку) та складності часу (найгірший час, необхідний для пошуку рішення).
Порівняльна таблиця складності алгоритмів пошуку в графах
b – коефіцієнт розгалуження, d – глибина дерева розв’язку, m – глибина дерева, l – обмеження глибини пошуку
| Алгоритм | Час | Простір | Оптимальність | Повнота |
|---|---|---|---|---|
| DFS, Пошук вглибину | O(b^m) | O(bm) | Ні | Ні |
| DLS, Пошук з обмеженням глибини | O(b^1) | O(bl) | Ні | Ні |
| IDS, Пошук з ітеративним заглибленням | O(b^d) | O(bd) | Так | Ні |
| BFS, Пошук вширину | O(b^d) | O(b^d) | Так | Так |
| BIDI, Двонаправлений пошук | O(b^(d/2)) | O(b^(d/2)) | Так | Так |
| UCS, Пошук з критерієм ваги | O(b^d) | O(b^d) | Так | Так |
Додатково
Вдосконалення
Одна з основних проблем з традиційними DFS і BFS полягає в тому, що у них відсутній список відвіданих вузлів. Ця модифікація робить алгоритми повними, ігноруючи цикли та відвідуючи лише наступні шляхи, які ще не були розглянуті. Для BFS, збереження списку відвіданих може скоротити час пошуку, а DFS може бути повним.
Переваги та недоліки
Кожен з алгоритмів має переваги та недоліки, що базуються на графі для пошуку. Наприклад, якщо коефіцієнт розгалуження графа невеликий, то BFS є найкращим вибором. Якщо дерево глибоке, але, як відомо, рішення є неглибоким на графі, то IDS є хорошим вибором. Якщо граф є зваженим, то слід використовувати UCS, оскільки він завжди знайде найкраще рішення, де DFS і BFS не зможуть.
Виконав Романів Роман
Developed by Інститут Програмних Систем
