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

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

2018-02-18T22:05:29Z

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

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

2018-02-16T22:31:56Z

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

111: /* Пошук вширину */

2018-02-16T22:17:36Z

‎Пошук вширину

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

2018-02-16T22:15:49Z

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

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

2018-02-16T22:10:28Z

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

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

2018-02-16T21:51:45Z

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

111: /* Двонаправлений пошук */

2018-02-16T21:50:29Z

‎Двонаправлений пошук

111: /* Пошук вширину */

2018-02-16T21:49:50Z

‎Пошук вширину

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

2018-02-16T21:08:06Z

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

111: /* Двонаправлений пошук */

2018-02-16T20:58:31Z

‎Двонаправлений пошук

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

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

← Попередня версія		Версія за 22:31, 16 лютого 2018
Рядок 100:		Рядок 100:
	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>
		+
		+	'''Виконав Романів Роман'''

← Попередня версія		Версія за 22:17, 16 лютого 2018
Рядок 1:		Рядок 1:
−	~~== Пошук вширину ==~~
	[[Файл:Bread_first_search_flow.png\|300px\|thumb\|right\|Порядок виконання пошуку вширину]]		[[Файл:Bread_first_search_flow.png\|300px\|thumb\|right\|Порядок виконання пошуку вширину]]
	=== Поняття ===		=== Поняття ===

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

	Двонаправлений пошук є цікавою ідеєю, але вимагає, щоб ми знали ціль, яку ми шукаємо на [[Граф\|графі]]. Простота часу та простору для двонаправленого пошуку - це O (bd / 2), оскільки нам потрібно лише оглядати половину глибини [[Граф\|дерева]]. Оскільки він базується на BFS, двонаправлений пошук є повним і оптимальним.		Двонаправлений пошук є цікавою ідеєю, але вимагає, щоб ми знали ціль, яку ми шукаємо на [[Граф\|графі]]. Простота часу та простору для двонаправленого пошуку - це O (bd / 2), оскільки нам потрібно лише оглядати половину глибини [[Граф\|дерева]]. Оскільки він базується на BFS, двонаправлений пошук є повним і оптимальним.
−
−	~~== Пошук вширину з критерієм ваги ==~~
−	~~[[Файл:Ucs_selection_flow.png\|300px\|thumb\|right\|Приклад графа де вибір найнижчої вартості для першого~~
−	~~вузла не дає найкращого результату]]~~
−	~~=== Поняття ===~~
−	Пошук з критерієм ваги (вартості) (UCS) можна застосувати, щоб знайти найнижчу вартість через [[Граф\|граф]], зберігаючи упорядкований список вузлів у порядку зниження ваги. Це дозволяє нам оцінити найменший рівень витрат з самого початку.
−
−	[[Алгоритм\|Алгоритм]] UCS використовує накопичену вартість шляху для визначення шляху для оцінки. Черга пріоритетів (відсортована від найменшої вартості до найбільшої) містить вузли для оцінювання. Оскільки діти вузлів оцінюються, ми додаємо їхню вартість до вузла з сукупною сумою поточного шляху. Цей вузол потім додається до черги, а коли всі діти оцінюються, то черга сортується в порядку зростання вартості. Коли першим елементом у черзі на пріоритет є цільовий вузол, то знайдено найкраще рішення.
−
−	UCS є оптимальним і може бути повним, але тільки в тому випадку, якщо вартість дуг невід'ємна (сумарна вартість маршруту завжди зростає). Складність часу та простору є такою ж, як BFS, O (b^d) для кожного.
−
−	~~=== Перебіг пошуку ===~~
−	~~[[Файл:Ucs_priorities.png\|300px\|thumb\|left\|Оцінка вузлів і стан черги пріоритетів]]~~
−	~~[[Файл:Ucs_price.png\|300px\|thumb\|right\|Ілюстрація вартості шляху в графі]]~~
−	На першому кроці початковий вузол був доданий до черги для пріоритетів, з вартістю нуль. На другому кроці кожний із трьох пов'язаних вузлів оцінюється та додається в чергу пріоритету. Коли жоден дочірній вузол не доступний для оцінки, черга пріоритетів сортується, щоб розмістити їх у порядку зростання вартості.
−
−	На третьому етапі оцінюються дочірні вузли С. У цьому випадку ми знаходимо бажану ціль (E), але оскільки накопичена ціна шляху становить вісім, вона закінчується в кінці черги. Для четвертого етапу ми оцінюємо вузол D та знову шукаємо цільовий вузол. Ціна шляху дорівнює семи, що все ще перевершує наш вузол B у черзі. Нарешті, на п’ятому етапі, оцінюється вузол В. Цільовий вузол знайдено знову, при цьому вартість маршруту становить шість. Черга пріоритету тепер містить цільовий вузол у верхній частині, що означає, що на наступній ітерації циклу [[Алгоритм\|алгоритм]] вийде з шляху A-> B-> E (працює назад від цільового вузла до початкового вузла).
−
−	Щоб обмежити розмір черги для пріоритетів, можна стерти записи, які є надлишковими. Наприклад, на кроці 4, запис про E (8) можна було б безпечно видалити, оскільки існує інший шлях, який має нижчу вартість (E (7)).
−
−	~~=== Реалізація ===~~
−	~~<nowiki>~~
−	~~#include <stdio.h>~~
−	~~#include “graph.h”~~
−	~~#include “pqueue.h”~~
−	~~#deﬁne A 0~~
−	~~#deﬁne B 1~~
−	~~#deﬁne C 2~~
−	~~#deﬁne D 3~~
−	~~#deﬁne E 4~~
−	~~int init_graph( graph_t *g_p )~~
−	{
−	~~addEdge( g_p, A, B, 5 );~~
−	~~addEdge( g_p, A, C, 1 );~~
−	~~addEdge( g_p, A, D, 2 );~~
−	~~addEdge( g_p, B, E, 1 );~~
−	~~addEdge( g_p, C, E, 7 );~~
−	~~addEdge( g_p, D, E, 5 );~~
−	~~return 0;~~
−	}
−	~~void ucs( graph_t *g_p, int root, int goal )~~
−	{
−	~~int node, cost, child_cost;~~
−	~~int to; pqueue_t *q_p;~~
−	~~q_p = createPQueue( 7 );~~
−	~~enPQueue( q_p, root, 0 );~~
−	~~while ( !isEmptyPQueue(q_p) )~~
−	{
−	~~dePQueue( q_p, &node, &cost );~~
−	~~if (node == goal)~~
−	{
−	~~printf(“cost %d\n”, cost);~~
−	~~return;~~
−	}
−	~~for (to = g_p->nodes-1 ; to > 0 ; to--)~~
−	{
−	~~child_cost = getEdge( g_p, node, to );~~
−	~~if (child_cost)~~
−	{
−	~~enPQueue( q_p, to, (child_cost+cost) );~~
−	}
−	}
−	}
−	~~destroyPQueue( q_p );~~
−	~~return;~~
−	}
−	~~int main()~~
−	{
−	~~graph_t *g_p;~~
−	~~g_p = createGraph( 6 );~~
−	~~init_graph( g_p );~~
−	~~ucs( g_p, A, E );~~
−	~~destroyGraph( g_p );~~
−	~~return 0;~~
−	}
−	~~</nowiki>~~

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

@@ Рядок 80: / Рядок 80: @@
 Пошук з критерієм ваги (вартості) (UCS) можна застосувати, щоб знайти найнижчу вартість через [[Граф|граф]], зберігаючи упорядкований список вузлів у порядку зниження ваги. Це дозволяє нам оцінити найменший рівень витрат з самого початку.
-Алгоритм UCS використовує накопичену вартість шляху для визначення шляху для оцінки. Черга пріоритетів (відсортована від найменшої вартості до найбільшої) містить вузли для оцінювання. Оскільки діти вузлів оцінюються, ми додаємо їхню вартість до вузла з сукупною сумою поточного шляху. Цей вузол потім додається до черги, а коли всі діти оцінюються, то черга сортується в порядку зростання вартості. Коли першим елементом у черзі на пріоритет є цільовий вузол, то знайдено найкраще рішення.
+[[Алгоритм|Алгоритм]] UCS використовує накопичену вартість шляху для визначення шляху для оцінки. Черга пріоритетів (відсортована від найменшої вартості до найбільшої) містить вузли для оцінювання. Оскільки діти вузлів оцінюються, ми додаємо їхню вартість до вузла з сукупною сумою поточного шляху. Цей вузол потім додається до черги, а коли всі діти оцінюються, то черга сортується в порядку зростання вартості. Коли першим елементом у черзі на пріоритет є цільовий вузол, то знайдено найкраще рішення.
 UCS є оптимальним і може бути повним, але тільки в тому випадку, якщо вартість дуг невід'ємна (сумарна вартість маршруту завжди зростає). Складність часу та простору є такою ж, як BFS, O (b^d) для кожного.
@@ Рядок 89: / Рядок 89: @@
 На першому кроці початковий вузол був доданий до черги для пріоритетів, з вартістю нуль. На другому кроці кожний із трьох пов'язаних вузлів оцінюється та додається в чергу пріоритету. Коли жоден дочірній вузол не доступний для оцінки, черга пріоритетів сортується, щоб розмістити їх у порядку зростання вартості.
-На третьому етапі оцінюються дочірні вузли С. У цьому випадку ми знаходимо бажану ціль (E), але оскільки накопичена ціна шляху становить вісім, вона закінчується в кінці черги. Для четвертого етапу ми оцінюємо вузол D та знову шукаємо цільовий вузол. Ціна шляху дорівнює семи, що все ще перевершує наш вузол B у черзі. Нарешті, на п’ятому етапі, оцінюється вузол В. Цільовий вузол знайдено знову, при цьому вартість маршруту становить шість. Черга пріоритету тепер містить цільовий вузол у верхній частині, що означає, що на наступній ітерації циклу алгоритм вийде з шляху A-> B-> E (працює назад від цільового вузла до початкового вузла).
+На третьому етапі оцінюються дочірні вузли С. У цьому випадку ми знаходимо бажану ціль (E), але оскільки накопичена ціна шляху становить вісім, вона закінчується в кінці черги. Для четвертого етапу ми оцінюємо вузол D та знову шукаємо цільовий вузол. Ціна шляху дорівнює семи, що все ще перевершує наш вузол B у черзі. Нарешті, на п’ятому етапі, оцінюється вузол В. Цільовий вузол знайдено знову, при цьому вартість маршруту становить шість. Черга пріоритету тепер містить цільовий вузол у верхній частині, що означає, що на наступній ітерації циклу [[Алгоритм|алгоритм]] вийде з шляху A-> B-> E (працює назад від цільового вузла до початкового вузла).
 Щоб обмежити розмір черги для пріоритетів, можна стерти записи, які є надлишковими. Наприклад, на кроці 4, запис про E (8) можна було б безпечно видалити, оскільки існує інший шлях, який має нижчу вартість (E (7)).

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

@@ Рядок 70: / Рядок 70: @@
 == Двонаправлений пошук ==
 [[Файл:Tssearch_flow.png|200px|thumb|right|Порядок виконання двонаправленого пошуку, що зустрівся на вузлі Н]]
-Алгоритм двонаправленого пошуку є похідним від BFS, що оперує, виконуючи два пошуки вширину, один починаючи від кореневого вузла, а інший - від цільового вузла. Коли два пошукові запити зустрічаються посередині, шлях може бути відновлений від кореня до цілі. Зустріч пошуків визначається, коли знайдено спільний вузол. Це здійснюється шляхом збереження закритого списку відвіданих вузлів.
+[[Алгоритм|Алгоритм]] двонаправленого пошуку є похідним від BFS, що оперує, виконуючи два пошуки вширину, один починаючи від кореневого вузла, а інший - від цільового вузла. Коли два пошукові запити зустрічаються посередині, шлях може бути відновлений від кореня до цілі. Зустріч пошуків визначається, коли знайдено спільний вузол. Це здійснюється шляхом збереження закритого списку відвіданих вузлів.
 Двонаправлений пошук є цікавою ідеєю, але вимагає, щоб ми знали ціль, яку ми шукаємо на [[Граф|графі]]. Простота часу та простору для двонаправленого пошуку - це O (bd / 2), оскільки нам потрібно лише оглядати половину глибини [[Граф|дерева]]. Оскільки він базується на BFS, двонаправлений пошук є повним і оптимальним.

@@ Рядок 7: / Рядок 7: @@
 Недоліком BFS є те, що кожен вузол, в якому відбувається пошук, потрібно зберігати (складність простору - O (b^d)). Всю глибину [[Граф|дерева]] не треба оглядати, тому d в цьому контексті є глибиною рішення, а не максимальна глибина дерева. Складність часу також O (b^d).
-У практичних реалізаціях BFS та інших алгоритмів пошуку підтримується закритий список, який містить відвідані вузли на [[Граф|графі]]. Це дозволяє алгоритму ефективно оглядати [[Граф|граф]] без повторного відвідування вузлів. У реалізаціях, де [[Граф|граф]] має вагу, зберігання закритого списку неможливе.
+У практичних реалізаціях BFS та інших [[Алгоритм|алгоритмів]] пошуку підтримується закритий список, який містить відвідані вузли на [[Граф|графі]]. Це дозволяє [[Алгоритм|алгоритму]] ефективно оглядати [[Граф|граф]] без повторного відвідування вузлів. У реалізаціях, де [[Граф|граф]] має вагу, зберігання закритого списку неможливе.
 === Реалізація ===

@@ Рядок 78: / Рядок 78: @@
 вузла не дає найкращого результату]]
 === Поняття ===
-Пошук з критерієм ваги (вартості) (UCS) можна застосувати, щоб знайти найнижчу вартість через граф, зберігаючи упорядкований список вузлів у порядку зниження ваги. Це дозволяє нам оцінити найменший рівень витрат з самого початку.
+Пошук з критерієм ваги (вартості) (UCS) можна застосувати, щоб знайти найнижчу вартість через [[Граф|граф]], зберігаючи упорядкований список вузлів у порядку зниження ваги. Це дозволяє нам оцінити найменший рівень витрат з самого початку.
 Алгоритм UCS використовує накопичену вартість шляху для визначення шляху для оцінки. Черга пріоритетів (відсортована від найменшої вартості до найбільшої) містить вузли для оцінювання. Оскільки діти вузлів оцінюються, ми додаємо їхню вартість до вузла з сукупною сумою поточного шляху. Цей вузол потім додається до черги, а коли всі діти оцінюються, то черга сортується в порядку зростання вартості. Коли першим елементом у черзі на пріоритет є цільовий вузол, то знайдено найкраще рішення.

@@ Рядок 72: / Рядок 72: @@
 Алгоритм двонаправленого пошуку є похідним від BFS, що оперує, виконуючи два пошуки вширину, один починаючи від кореневого вузла, а інший - від цільового вузла. Коли два пошукові запити зустрічаються посередині, шлях може бути відновлений від кореня до цілі. Зустріч пошуків визначається, коли знайдено спільний вузол. Це здійснюється шляхом збереження закритого списку відвіданих вузлів.
-Двонаправлений пошук є цікавою ідеєю, але вимагає, щоб ми знали ціль, яку ми шукаємо на графі. Простота часу та простору для двонаправленого пошуку - це O (bd / 2), оскільки нам потрібно лише оглядати половину глибини дерева. Оскільки він базується на BFS, двонаправлений пошук є повним і оптимальним.
+Двонаправлений пошук є цікавою ідеєю, але вимагає, щоб ми знали ціль, яку ми шукаємо на [[Граф|графі]]. Простота часу та простору для двонаправленого пошуку - це O (bd / 2), оскільки нам потрібно лише оглядати половину глибини [[Граф|дерева]]. Оскільки він базується на BFS, двонаправлений пошук є повним і оптимальним.
 == Пошук вширину з критерієм ваги ==