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

111: /* Допоміжний АРІ */

2018-02-18T22:04:48Z

‎Допоміжний АРІ

111: /* Допоміжний АРІ */

2018-02-16T22:31:13Z

‎Допоміжний АРІ

111: /* Пошук з ітеративним заглибленням */

2018-02-16T22:23:22Z

‎Пошук з ітеративним заглибленням

111: /* Пошук з обмеженням глибини */

2018-02-16T22:21:08Z

‎Пошук з обмеженням глибини

111: 111 перейменував сторінку з Глибинний пошук в графах на Пошук графа вглибину

2018-02-16T22:18:42Z

111 перейменував сторінку з Глибинний пошук в графах на Пошук графа вглибину

111: /* Поняття */

2018-02-16T21:47:30Z

‎Поняття

111: /* Пошук вглибину */

2018-02-16T21:47:19Z

‎Пошук вглибину

111: /* Пошук з ітеративним заглибленням */

2018-02-16T21:46:05Z

‎Пошук з ітеративним заглибленням

111: /* Пошук з обмеженням глибини */

2018-02-16T21:33:21Z

‎Пошук з обмеженням глибини

111: /* Пошук вглибину */

2018-02-16T21:31:52Z

‎Пошук вглибину

← Попередня версія		Версія за 22:04, 18 лютого 2018
Рядок 94:		Рядок 94:
	int isFullPQueue (pqueue_t *q_p );</nowiki>		int isFullPQueue (pqueue_t *q_p );</nowiki>

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

← Попередня версія		Версія за 22:31, 16 лютого 2018
Рядок 93:		Рядок 93:
	int isEmptyPQueue (pqueue_t *q_p );		int isEmptyPQueue (pqueue_t *q_p );
	int isFullPQueue (pqueue_t *q_p );</nowiki>		int isFullPQueue (pqueue_t *q_p );</nowiki>
		+
		+	'''Виконав Романів Роман'''

@@ Рядок 61: / Рядок 61: @@
    init_graph( g_p );
    dfs( g_p, 0, 5 );
    destroyGraph( g_p );
    return 0;

@@ Рядок 64: / Рядок 64: @@
    return 0;
+}
 </nowiki>

@@ Рядок 2: / Рядок 2: @@
 [[Файл:Graph_depth_first_search_flow.png|300px|thumb|right|Порядок виконання пошуку вглибину в малому дереві]]
 === Поняття ===
-[[Алгоритм|алгоритм]] пошуку вглибину (Depth-First Search, DFS) - це метод пошуку [[Граф|графа]], який починається з кореневого вузла, і оглядає кожну гілку на найглибшому рівні, перш ніж відслідковувати попередньо нерозвідані гілки. Знайдені, але ще не перевірені вузли зберігаються в черзі LIFO (стек).
+[[Алгоритм|Алгоритм]] пошуку вглибину (Depth-First Search, DFS) - це метод пошуку [[Граф|графа]], який починається з кореневого вузла, і оглядає кожну гілку на найглибшому рівні, перш ніж відслідковувати попередньо нерозвідані гілки. Знайдені, але ще не перевірені вузли зберігаються в черзі LIFO (стек).
 Складність простору для DFS - це O (bd), де складність часу геометрична (O (b^d)). Це може бути великою проблемою для глибоких розгалужених [[Граф|графів]], оскільки [[Алгоритм|алгоритм]] буде продовжувати до максимальної глибини [[Граф|графа]]. Якщо в [[Граф|графі]] присутні цикли, DFS буде слідувати цим циклам безкінечно. З цієї причини алгоритм DFS не є повним, оскільки цикли можуть не дати алгоритму виявити ціль. Якщо на [[Граф|графі]] немає циклів, то алгоритм повний (завжди знайде цільовий вузол). Алгоритм DFS не є оптимальним, але може ним стати, за допомогою перевірки шляху (щоб забезпечити найкоротший шлях до мети).

← Попередня версія	Версія за 22:18, 16 лютого 2018
(Немає відмінностей)

@@ Рядок 145: / Рядок 145: @@
 === Поняття ===
 Пошук з ітеративним заглибленням (Iterative Deepening Search, IDS) – це похідний від DLS алгоритм, що поєднує в собі особливості пошуку вглибину з та пошуку вширину. IDS працює, виконуючи пошуки DLS із збільшеною глибиною, доки не буде знайдено ціль.
-Мінімізуючи глибину пошуку, ми змушуємо алгоритм шукати вширину [[Граф|графа]]. Якщо ціль не знайдено, збільшується глибина, яку алгоритму дозволено шукати, і він запускається знову.
+Мінімізуючи глибину пошуку, ми змушуємо [[Алгоритм|алгоритм]] шукати вширину [[Граф|графа]]. Якщо ціль не знайдено, збільшується глибина, яку [[Алгоритм|алгоритму]] дозволено шукати, і він запускається знову.
-IDS є зручним, тому що він не схильний до зациклення (характеристика DLS, на якій вона заснована). Він також знаходить ціль, найближчу до кореневого вузла, як і алгоритм BFS (який буде детально описано далі). З цієї причини це найкращий алгоритм, коли глибина рішення невідома.
+IDS є зручним, тому що він не схильний до зациклення (характеристика DLS, на якій вона заснована). Він також знаходить ціль, найближчу до кореневого вузла, як і [[Алгоритм|алгоритм]] BFS (який буде детально описано далі). З цієї причини це найкращий [[Алгоритм|алгоритм]], коли глибина рішення невідома.
 Складність часу для IDS ідентична DFS і DLS, O (b^d). Простір складності IDS - O (bd). Навідмінно від DFS та DLS, IDS завжди знайде найкраще рішення, тому він є повним і оптимальним.

@@ Рядок 69: / Рядок 69: @@
 [[Файл:Depth_limited_search_flow.png|300px|thumb|right|Порядок виконання пошуку з обмеженням глибини 2]]
 === Поняття ===
-Пошук з обмеженням глибини (Depth-Limited Search, DLS) – це модифікація пошуку вглибину, яка мінімізує глибину, на яку може йти алгоритм пошуку. Крім того, що починається з кореневого та цільового вузлів, передбачається, що алгоритм не спускається нижче певного рівня.
+Пошук з обмеженням глибини (Depth-Limited Search, DLS) – це модифікація пошуку вглибину, яка мінімізує глибину, на яку може йти [[Алгоритм|алгоритм]] пошуку. Крім того, що починається з кореневого та цільового вузлів, передбачається, що алгоритм не спускається нижче певного рівня.
-Ця модифікація зберігає алгоритм від безкінечних циклів, зупиняючи пошук після попередньо встановленої глибини.
+Ця модифікація зберігає [[Алгоритм|алгоритм]] від безкінечних циклів, зупиняючи пошук після попередньо встановленої глибини.
-Хоча алгоритм усуває можливість нескінченного циклу у [[Граф|графі]], він також зменшує область пошуку. Якщо цільовий вузол був одним з вузлів із позначкою "X", його не було б знайдено, зробивши алгоритм пошуку неповним. Алгоритм може бути повним, якщо глибина пошуку залежить від самого дерева (у цьому випадку d дорівнює трьом). Техніка також не є оптимальною, оскільки може бути знайдений перший шлях замість найкоротшого.
+Хоча [[Алгоритм|алгоритм]] усуває можливість нескінченного циклу у [[Граф|графі]], він також зменшує область пошуку. Якщо цільовий вузол був одним з вузлів із позначкою "X", його не було б знайдено, зробивши [[Алгоритм|алгоритм]] пошуку неповним. [[Алгоритм|алгоритм]] може бути повним, якщо глибина пошуку залежить від самого дерева (у цьому випадку d дорівнює трьом). Техніка також не є оптимальною, оскільки може бути знайдений перший шлях замість найкоротшого.
-Час і простір обмеженого по глибині пошуку аналогічні DFS, з якого виводиться цей алгоритм. Складність простору - це O (bd), а складність часу - O (b^d), але в цьому випадку d є глибиною пошуку, а не [[Граф|графа]].
+Час і простір обмеженого по глибині пошуку аналогічні DFS, з якого виводиться цей [[Алгоритм|алгоритм]]. Складність простору - це O (bd), а складність часу - O (b^d), але в цьому випадку d є глибиною пошуку, а не [[Граф|графа]].
 === Реалізація ===

@@ Рядок 4: / Рядок 4: @@
 Алгоритм пошуку вглибину (Depth-First Search, DFS) - це метод пошуку [[Граф|графа]], який починається з кореневого вузла, і оглядає кожну гілку на найглибшому рівні, перш ніж відслідковувати попередньо нерозвідані гілки. Знайдені, але ще не перевірені вузли зберігаються в черзі LIFO (стек).
-Складність простору для DFS - це O (bd), де складність часу геометрична (O (b^d)). Це може бути великою проблемою для глибоких розгалужених [[Граф|графів]], оскільки алгоритм буде продовжувати до максимальної глибини [[Граф|графа]]. Якщо в [[Граф|графі]] присутні цикли, DFS буде слідувати цим циклам безкінечно. З цієї причини алгоритм DFS не є повним, оскільки цикли можуть не дати алгоритму виявити ціль. Якщо на [[Граф|графі]] немає циклів, то алгоритм повний (завжди знайде цільовий вузол). Алгоритм DFS не є оптимальним, але може ним стати, за допомогою перевірки шляху (щоб забезпечити найкоротший шлях до мети).
+Складність простору для DFS - це O (bd), де складність часу геометрична (O (b^d)). Це може бути великою проблемою для глибоких розгалужених [[Граф|графів]], оскільки [[Алгоритм|алгоритм]] буде продовжувати до максимальної глибини [[Граф|графа]]. Якщо в [[Граф|графі]] присутні цикли, DFS буде слідувати цим циклам безкінечно. З цієї причини алгоритм DFS не є повним, оскільки цикли можуть не дати алгоритму виявити ціль. Якщо на [[Граф|графі]] немає циклів, то алгоритм повний (завжди знайде цільовий вузол). Алгоритм DFS не є оптимальним, але може ним стати, за допомогою перевірки шляху (щоб забезпечити найкоротший шлях до мети).
 === Реалізація ===