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

2018-02-18T22:03:14Z

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

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

2018-02-16T22:32:07Z

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

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

2018-02-16T22:16:56Z

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

111: Створена сторінка: == Пошук вширину з критерієм ваги == Файл:Ucs_selection_flow.png|300px|thumb|right|Приклад графа де вибір н...

2018-02-16T22:16:15Z

Створена сторінка: == Пошук вширину з критерієм ваги == Файл:Ucs_selection_flow.png|300px|thumb|right|Приклад графа де вибір н...

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

== Пошук вширину з критерієм ваги ==
[[Файл: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>

== Допоміжний АРІ ==
Для демонстрації алгоритмів пошуку необхідний допоміжний АРІ, що включає перелічені функції:
<nowiki>
/* Graph API */
graph_t *createGraph (int nodes );
void destroyGraph (graph_t *g_p );
void addEdge (graph_t *g_p, int from, int to, int value );
int getEdge (graph_t *g_p, int from, int to );
/* Stack API */
stack_t *createStack (int depth );
void destroyStack (stack_t *s_p );
void pushStack (stack_t *s_p, int value );
int popStack (stack_t *s_p );
int isEmptyStack (stack_t *s_p );
/* Queue API */
queue_t *createQueue (int depth );
void destroyQueue (queue_t *q_p );
void enQueue (queue_t *q_p, int value );
int deQueue (queue_t *q_p );
int isEmptyQueue (queue_t *q_p );
/* Priority Queue API */
pqueue_t *createPQueue (int depth );
void destroyPQueue (pqueue_t *q_p );
void enPQueue (pqueue_t *q_p, int value, int cost );
void dePQueue (pqueue_t *q_p, int *value, int *cost );
int isEmptyPQueue (pqueue_t *q_p );
int isFullPQueue (pqueue_t *q_p );</nowiki>

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

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

← Попередня версія		Версія за 22:32, 16 лютого 2018
Рядок 101:		Рядок 101:
	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:16, 16 лютого 2018
Рядок 1:		Рядок 1:
−	~~== Пошук вширину з критерієм ваги ==~~
	[[Файл:Ucs_selection_flow.png\|300px\|thumb\|right\|Приклад графа де вибір найнижчої вартості для першого		[[Файл:Ucs_selection_flow.png\|300px\|thumb\|right\|Приклад графа де вибір найнижчої вартості для першого
	вузла не дає найкращого результату]]		вузла не дає найкращого результату]]

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

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

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

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

111: Створена сторінка: == Пошук вширину з критерієм ваги == Файл:Ucs_selection_flow.png|300px|thumb|right|Приклад графа де вибір н...