Відмінності між версіями «Пошук в графах»!!!
111 (обговорення • внесок) (→Переваги та недоліки) |
111 (обговорення • внесок) (→Додатково) |
||
| (не показано 6 проміжних версій цього учасника) | |||
| Рядок 9: | Рядок 9: | ||
== Оцінка складності алгоритмів пошуку == | == Оцінка складності алгоритмів пошуку == | ||
| − | Значення O-велике буде використане для порівняння алгоритмів. Ця позначка визначає асимптотичну верхню межу алгоритму з урахуванням глибини (d) дерева та коефіцієнта розгалуження або середнього числа гілок (b) з кожного вузла. Існує ряд загальних складностей, які існують для алгоритмів пошуку: | + | Значення O-велике буде використане для порівняння [[Алгоритм|алгоритмів]]. Ця позначка визначає асимптотичну верхню межу [[Алгоритм|алгоритму]] з урахуванням глибини (d) [[Граф|дерева]] та коефіцієнта розгалуження або середнього числа гілок (b) з кожного вузла. Існує ряд загальних складностей, які існують для [[Алгоритм|алгоритмів]] пошуку: |
{| | {| | ||
| Рядок 37: | Рядок 37: | ||
|} | |} | ||
| − | Позначення O-велике враховує найгірший можливий показник складності алгоритму пошуку та є звичайним інструментом порівняння для алгоритмів. Ми порівняємо алгоритми пошуку з використанням простору складності (міра пам'яті, необхідної під час пошуку) та складності часу (найгірший час, необхідний для пошуку рішення). | + | Позначення O-велике враховує найгірший можливий показник складності [[Алгоритм|алгоритму]] пошуку та є звичайним інструментом порівняння для [[Алгоритм|алгоритмів]]. Ми порівняємо [[Алгоритм|алгоритми]] пошуку з використанням простору складності (міра пам'яті, необхідної під час пошуку) та складності часу (найгірший час, необхідний для пошуку рішення). |
== Порівняльна таблиця складності алгоритмів пошуку в графах == | == Порівняльна таблиця складності алгоритмів пошуку в графах == | ||
| Рядок 53: | Рядок 53: | ||
! Повнота | ! Повнота | ||
|- | |- | ||
| − | |DFS, [[ | + | |DFS, [[Пошук графа вглибину|Пошук вглибину]] |
|O(b^m) | |O(b^m) | ||
|O(bm) | |O(bm) | ||
| Рядок 59: | Рядок 59: | ||
|Ні | |Ні | ||
|- | |- | ||
| − | |DLS, [[ | + | |DLS, [[Пошук в графі з обмеженням глибини|Пошук з обмеженням глибини]] |
|O(b^1) | |O(b^1) | ||
|O(bl) | |O(bl) | ||
| Рядок 65: | Рядок 65: | ||
|Ні | |Ні | ||
|- | |- | ||
| − | |IDS, [[ | + | |IDS, [[Пошук в графі з ітеративним заглибленням|Пошук з ітеративним заглибленням]] |
|O(b^d) | |O(b^d) | ||
|O(bd) | |O(bd) | ||
| Рядок 71: | Рядок 71: | ||
|Ні | |Ні | ||
|- | |- | ||
| − | |BFS, [[Пошук | + | |BFS, [[Пошук графа вширину|Пошук вширину]] |
|O(b^d) | |O(b^d) | ||
|O(b^d) | |O(b^d) | ||
| Рядок 77: | Рядок 77: | ||
|Так | |Так | ||
|- | |- | ||
| − | |BIDI, [[Пошук | + | |BIDI, [[Пошук графа вширину|Двонаправлений пошук]] |
|O(b^(d/2)) | |O(b^(d/2)) | ||
|O(b^(d/2)) | |O(b^(d/2)) | ||
| Рядок 83: | Рядок 83: | ||
|Так | |Так | ||
|- | |- | ||
| − | |UCS, [[Пошук в | + | |UCS, [[Пошук в графі з критерієм ваги|Пошук з критерієм ваги]] |
|O(b^d) | |O(b^d) | ||
|O(b^d) | |O(b^d) | ||
| Рядок 92: | Рядок 92: | ||
== Додатково == | == Додатково == | ||
=== Вдосконалення === | === Вдосконалення === | ||
| − | Одна з основних проблем з традиційними DFS і BFS полягає в тому, що у них відсутній список відвіданих вузлів. Ця модифікація робить алгоритми повними, ігноруючи цикли та відвідуючи лише наступні шляхи, які ще не були розглянуті. Для BFS, збереження списку відвіданих може скоротити час пошуку, а DFS може бути повним. | + | Одна з основних проблем з традиційними DFS і BFS полягає в тому, що у них відсутній список відвіданих вузлів. Ця модифікація робить [[Алгоритм|алгоритми]] повними, ігноруючи цикли та відвідуючи лише наступні шляхи, які ще не були розглянуті. Для BFS, збереження списку відвіданих може скоротити час пошуку, а DFS може бути повним. |
=== Переваги та недоліки === | === Переваги та недоліки === | ||
| − | Кожен з алгоритмів має переваги та недоліки, що базуються на [[Граф|графі]] для пошуку. Наприклад, якщо коефіцієнт розгалуження графа невеликий, то BFS є найкращим вибором. Якщо дерево глибоке, але, як відомо, рішення є неглибоким на графі, то IDS є хорошим вибором. Якщо граф є зваженим, то слід використовувати UCS, оскільки він завжди знайде найкраще рішення, де DFS і BFS не зможуть. | + | Кожен з алгоритмів має переваги та недоліки, що базуються на [[Граф|графі]] для пошуку. Наприклад, якщо коефіцієнт розгалуження [[Граф|графа]] невеликий, то BFS є найкращим вибором. Якщо [[Граф|дерево]] глибоке, але, як відомо, рішення є неглибоким на графі, то IDS є хорошим вибором. Якщо [[Граф|граф]] є зваженим, то слід використовувати UCS, оскільки він завжди знайде найкраще рішення, де DFS і BFS не зможуть. |
| + | |||
| + | '''Виконав [[Романів Роман]]''' | ||
Поточна версія на 01:05, 19 лютого 2018
Зміст
Загальні парадигми
Перш ніж ми обговоримо деякі з неінформованих методів пошуку, давайте розглянемо два простих загальних неінформованих методи пошуку.
Перший називається "Генеруй і тестуй". У цьому методі ми генеруємо потенційне рішення, а потім перевіряємо його на відповідність. Якщо ми знайшли рішення, ми закінчили, інакше ми повторимо, спробувавши ще одне потенційне рішення. Без належного рішення ми спробуємо знову. Зауважте, що ми не відстежуємо те, що ми пробували раніше; ми просто рухаємося вперед з потенційними рішеннями, що є справжнім сліпим пошуком.
Інший варіант називається "випадковий пошук", який випадковим чином вибирає новий стан з поточного (шляхом вибору оператора та його застосування). Якщо ми досягнемо цільового стану, то пошук завершено. В іншому випадку ми випадково виберемо інший оператор (що веде до нового стану) і продовжуємо.
Випадковий пошук і метод "Генеруй та тестуй" є сліпими методами пошуку. Вони можуть привести до зациклення, і не знайти рішення, навіть якщо воно існує в пошуковому просторі.
Оцінка складності алгоритмів пошуку
Значення 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 Інститут Програмних Систем
