Пошук в графах - Історія редагувань

111: /* Додатково */

2018-02-18T22:05:52Z

‎Додатково

111: /* Додатково */

2018-02-16T22:29:51Z

‎Додатково

111: /* Порівняльна таблиця складності алгоритмів пошуку в графах */

2018-02-16T22:27:37Z

‎Порівняльна таблиця складності алгоритмів пошуку в графах

111: /* Додатково */

2018-02-16T21:56:13Z

‎Додатково

111: /* Оцінка складності алгоритмів пошуку */

2018-02-16T21:55:24Z

‎Оцінка складності алгоритмів пошуку

111: /* Оцінка складності алгоритмів пошуку */

2018-02-16T20:51:25Z

‎Оцінка складності алгоритмів пошуку

111: /* Переваги та недоліки */

2018-02-16T20:50:20Z

‎Переваги та недоліки

111: /* Переваги та недоліки */

2018-02-16T20:49:27Z

‎Переваги та недоліки

111: /* Порівняльна таблиця складності алгоритмів пошуку в графах */

2018-02-16T16:30:10Z

‎Порівняльна таблиця складності алгоритмів пошуку в графах

111: Створена сторінка: == Загальні парадигми == Перш ніж ми обговоримо деякі з неінформованих методів пошуку, да...

2018-02-16T16:29:12Z

Створена сторінка: == Загальні парадигми == Перш ніж ми обговоримо деякі з неінформованих методів пошуку, да...

Нова сторінка

== Загальні парадигми ==
Перш ніж ми обговоримо деякі з неінформованих методів пошуку, давайте розглянемо два простих загальних неінформованих методи пошуку.

Перший називається "Генеруй і тестуй". У цьому методі ми генеруємо потенційне рішення, а потім перевіряємо його на відповідність. Якщо ми знайшли рішення, ми закінчили, інакше ми повторимо, спробувавши ще одне потенційне рішення. Без належного рішення ми спробуємо знову. Зауважте, що ми не відстежуємо те, що ми пробували раніше; ми просто рухаємося вперед з потенційними рішеннями, що є справжнім сліпим пошуком.

Інший варіант називається "випадковий пошук", який випадковим чином вибирає новий стан з поточного (шляхом вибору оператора та його застосування). Якщо ми досягнемо цільового стану, то пошук завершено. В іншому випадку ми випадково виберемо інший оператор (що веде до нового стану) і продовжуємо.

Випадковий пошук і метод "Генеруй та тестуй" є сліпими методами пошуку. Вони можуть привести до зациклення, і не знайти рішення, навіть якщо воно існує в пошуковому просторі.

== Оцінка складності алгоритмів пошуку ==
Значення O-велике буде використане для порівняння алгоритмів. Ця позначка визначає асимптотичну верхню межу алгоритму з урахуванням глибини (d) дерева та коефіцієнта розгалуження або середнього числа гілок (b) з кожного вузла. Існує ряд загальних складностей, які існують для алгоритмів пошуку:

{|
! style="text-align:left;"| Складність
! Значення
|-
|«O»
|Порядок
|-
|О (1)
|Константа (незалежно від кількості вузлів)
|-
|O (n)
|Лінійний (відповідно до кількості вузлів)
|-
|O (log n)
|Логарифмічний
|-
|O (n^2)
|Квадратичний
|-
|O (c^n)
|Геометричний
|-
|O (n!)
|Комбінаторний
|}

Позначення O-велике враховує найгірший можливий показник складності алгоритму пошуку та є звичайним інструментом порівняння для алгоритмів. Ми порівняємо алгоритми пошуку з використанням простору складності (міра пам'яті, необхідної під час пошуку) та складності часу (найгірший час, необхідний для пошуку рішення).

== Порівняльна таблиця складності алгоритмів пошуку в графах ==

b – коефіцієнт розгалуження
d – глибина дерева розв’язку
m – глибина дерева
l – обмеження глибини пошуку

{|
! style="text-align:left;"| Алгоритм
! Час
! Простір
! Оптимальність
! Повнота
|-
|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 не зможуть.

← Попередня версія		Версія за 22:05, 18 лютого 2018
Рядок 97:		Рядок 97:
	Кожен з алгоритмів має переваги та недоліки, що базуються на [[Граф\|графі]] для пошуку. Наприклад, якщо коефіцієнт розгалуження [[Граф\|графа]] невеликий, то BFS є найкращим вибором. Якщо [[Граф\|дерево]] глибоке, але, як відомо, рішення є неглибоким на графі, то IDS є хорошим вибором. Якщо [[Граф\|граф]] є зваженим, то слід використовувати UCS, оскільки він завжди знайде найкраще рішення, де DFS і BFS не зможуть.		Кожен з алгоритмів має переваги та недоліки, що базуються на [[Граф\|графі]] для пошуку. Наприклад, якщо коефіцієнт розгалуження [[Граф\|графа]] невеликий, то BFS є найкращим вибором. Якщо [[Граф\|дерево]] глибоке, але, як відомо, рішення є неглибоким на графі, то IDS є хорошим вибором. Якщо [[Граф\|граф]] є зваженим, то слід використовувати UCS, оскільки він завжди знайде найкраще рішення, де DFS і BFS не зможуть.

−	'''Виконав Романів Роман'''	+	'''Виконав [[Романів Роман]]'''

← Попередня версія		Версія за 22:29, 16 лютого 2018
Рядок 96:		Рядок 96:
	=== Переваги та недоліки ===		=== Переваги та недоліки ===
	Кожен з алгоритмів має переваги та недоліки, що базуються на [[Граф\|графі]] для пошуку. Наприклад, якщо коефіцієнт розгалуження [[Граф\|графа]] невеликий, то BFS є найкращим вибором. Якщо [[Граф\|дерево]] глибоке, але, як відомо, рішення є неглибоким на графі, то IDS є хорошим вибором. Якщо [[Граф\|граф]] є зваженим, то слід використовувати UCS, оскільки він завжди знайде найкраще рішення, де DFS і BFS не зможуть.		Кожен з алгоритмів має переваги та недоліки, що базуються на [[Граф\|графі]] для пошуку. Наприклад, якщо коефіцієнт розгалуження [[Граф\|графа]] невеликий, то BFS є найкращим вибором. Якщо [[Граф\|дерево]] глибоке, але, як відомо, рішення є неглибоким на графі, то IDS є хорошим вибором. Якщо [[Граф\|граф]] є зваженим, то слід використовувати UCS, оскільки він завжди знайде найкраще рішення, де DFS і BFS не зможуть.
		+
		+	'''Виконав Романів Роман'''

@@ Рядок 9: / Рядок 9: @@
 == Оцінка складності алгоритмів пошуку ==
-Значення O-велике буде використане для порівняння алгоритмів. Ця позначка визначає асимптотичну верхню межу алгоритму з урахуванням глибини (d) [[Граф|дерева]] та коефіцієнта розгалуження або середнього числа гілок (b) з кожного вузла. Існує ряд загальних складностей, які існують для алгоритмів пошуку:
+Значення O-велике буде використане для порівняння [[Алгоритм|алгоритмів]]. Ця позначка визначає асимптотичну верхню межу [[Алгоритм|алгоритму]] з урахуванням глибини (d) [[Граф|дерева]] та коефіцієнта розгалуження або середнього числа гілок (b) з кожного вузла. Існує ряд загальних складностей, які існують для [[Алгоритм|алгоритмів]] пошуку:
 {|
@@ Рядок 37: / Рядок 37: @@
 |}
-Позначення O-велике враховує найгірший можливий показник складності алгоритму пошуку та є звичайним інструментом порівняння для алгоритмів. Ми порівняємо алгоритми пошуку з використанням простору складності (міра пам'яті, необхідної під час пошуку) та складності часу (найгірший час, необхідний для пошуку рішення).
+Позначення O-велике враховує найгірший можливий показник складності [[Алгоритм|алгоритму]] пошуку та є звичайним інструментом порівняння для [[Алгоритм|алгоритмів]]. Ми порівняємо [[Алгоритм|алгоритми]] пошуку з використанням простору складності (міра пам'яті, необхідної під час пошуку) та складності часу (найгірший час, необхідний для пошуку рішення).
 == Порівняльна таблиця складності алгоритмів пошуку в графах ==

← Попередня версія		Версія за 20:50, 16 лютого 2018
Рядок 95:		Рядок 95:

	=== Переваги та недоліки ===		=== Переваги та недоліки ===
−	Кожен з алгоритмів має переваги та недоліки, що базуються на [[Граф\|графі]] для пошуку. Наприклад, якщо коефіцієнт розгалуження графа невеликий, то BFS є найкращим вибором. Якщо дерево глибоке, але, як відомо, рішення є неглибоким на графі, то IDS є хорошим вибором. Якщо граф є зваженим, то слід використовувати UCS, оскільки він завжди знайде найкраще рішення, де DFS і BFS не зможуть.	+	Кожен з алгоритмів має переваги та недоліки, що базуються на [[Граф\|графі]] для пошуку. Наприклад, якщо коефіцієнт розгалуження [[Граф\|графа]] невеликий, то BFS є найкращим вибором. Якщо [[Граф\|дерево]] глибоке, але, як відомо, рішення є неглибоким на графі, то IDS є хорошим вибором. Якщо [[Граф\|граф]] є зваженим, то слід використовувати UCS, оскільки він завжди знайде найкраще рішення, де DFS і BFS не зможуть.

← Попередня версія		Версія за 20:49, 16 лютого 2018
Рядок 95:		Рядок 95:

	=== Переваги та недоліки ===		=== Переваги та недоліки ===
−	Кожен з алгоритмів має переваги та недоліки, що базуються на графі для пошуку. Наприклад, якщо коефіцієнт розгалуження графа невеликий, то BFS є найкращим вибором. Якщо дерево глибоке, але, як відомо, рішення є неглибоким на графі, то IDS є хорошим вибором. Якщо граф є зваженим, то слід використовувати UCS, оскільки він завжди знайде найкраще рішення, де DFS і BFS не зможуть.	+	Кожен з алгоритмів має переваги та недоліки, що базуються на [[Граф\|графі]] для пошуку. Наприклад, якщо коефіцієнт розгалуження графа невеликий, то BFS є найкращим вибором. Якщо дерево глибоке, але, як відомо, рішення є неглибоким на графі, то IDS є хорошим вибором. Якщо граф є зваженим, то слід використовувати UCS, оскільки він завжди знайде найкраще рішення, де DFS і BFS не зможуть.

@@ Рядок 53: / Рядок 53: @@
 ! Повнота
 |-
-|DFS, [[Глибинний пошук в графах|Пошук вглибину]]
+|DFS, [[Пошук графа вглибину|Пошук вглибину]]
 |O(b^m)
 |O(bm)
@@ Рядок 59: / Рядок 59: @@
 |Ні
 |-
-|DLS, [[Глибинний пошук в графах|Пошук з обмеженням глибини]]
+|DLS, [[Пошук в графі з обмеженням глибини|Пошук з обмеженням глибини]]
 |O(b^1)
 |O(bl)
@@ Рядок 65: / Рядок 65: @@
 |Ні
 |-
-|IDS, [[Глибинний пошук в графах|Пошук з ітеративним заглибленням]]
+|IDS, [[Пошук в графі з ітеративним заглибленням|Пошук з ітеративним заглибленням]]
 |O(b^d)
 |O(bd)
@@ Рядок 71: / Рядок 71: @@
 |Ні
 |-
-|BFS, [[Пошук в графах вширину|Пошук вширину]]
+|BFS, [[Пошук графа вширину|Пошук вширину]]
 |O(b^d)
 |O(b^d)
@@ Рядок 77: / Рядок 77: @@
 |Так
 |-
-|BIDI, [[Пошук в графах вширину|Двонаправлений пошук]]
+|BIDI, [[Пошук графа вширину|Двонаправлений пошук]]
 |O(b^(d/2))
 |O(b^(d/2))
@@ Рядок 83: / Рядок 83: @@
 |Так
 |-
-|UCS, [[Пошук в графах вширину|Пошук з критерієм ваги]]
+|UCS, [[Пошук в графі з критерієм ваги|Пошук з критерієм ваги]]
 |O(b^d)
 |O(b^d)

@@ Рядок 92: / Рядок 92: @@
 == Додатково ==
 === Вдосконалення ===
-Одна з основних проблем з традиційними DFS і BFS полягає в тому, що у них відсутній список відвіданих вузлів. Ця модифікація робить алгоритми повними, ігноруючи цикли та відвідуючи лише наступні шляхи, які ще не були розглянуті. Для BFS, збереження списку відвіданих може скоротити час пошуку, а DFS може бути повним.
+Одна з основних проблем з традиційними DFS і BFS полягає в тому, що у них відсутній список відвіданих вузлів. Ця модифікація робить [[Алгоритм|алгоритми]] повними, ігноруючи цикли та відвідуючи лише наступні шляхи, які ще не були розглянуті. Для BFS, збереження списку відвіданих може скоротити час пошуку, а DFS може бути повним.
 === Переваги та недоліки ===
 Кожен з алгоритмів має переваги та недоліки, що базуються на [[Граф|графі]] для пошуку. Наприклад, якщо коефіцієнт розгалуження [[Граф|графа]] невеликий, то BFS є найкращим вибором. Якщо [[Граф|дерево]] глибоке, але, як відомо, рішення є неглибоким на графі, то IDS є хорошим вибором. Якщо [[Граф|граф]] є зваженим, то слід використовувати UCS, оскільки він завжди знайде найкраще рішення, де DFS і BFS не зможуть.

@@ Рядок 41: / Рядок 41: @@
 == Порівняльна таблиця складності алгоритмів пошуку в графах ==
-b – коефіцієнт розгалуження
+b – коефіцієнт розгалуження,
-d – глибина дерева розв’язку
+d – глибина дерева розв’язку,
-m – глибина дерева
+m – глибина дерева,
 l – обмеження глибини пошуку