ПОШУК «НАЙКРАЩИЙ-ПЕРШИЙ» (BEST-FS) - Історія редагувань

111 в 10:50, 20 лютого 2018

2018-02-20T10:50:14Z

111 в 10:48, 20 лютого 2018

2018-02-20T10:48:54Z

111 в 10:44, 20 лютого 2018

2018-02-20T10:44:01Z

111 в 10:43, 20 лютого 2018

2018-02-20T10:43:01Z

111 в 10:39, 20 лютого 2018

2018-02-20T10:39:25Z

111 в 10:33, 20 лютого 2018

2018-02-20T10:33:59Z

111 в 10:31, 20 лютого 2018

2018-02-20T10:31:26Z

111 в 10:30, 20 лютого 2018

2018-02-20T10:30:24Z

111 в 10:24, 20 лютого 2018

2018-02-20T10:24:11Z

111 в 10:23, 20 лютого 2018

2018-02-20T10:23:37Z

@@ Рядок 1: / Рядок 1: @@
-У результатах пошуку «найкращий-перший» пошуковий простір оцінюється за евристичною функцією. Вузли, які ще підлягають оцінці, зберігаються у списку OPEN, а ті, які вже були оцінені, зберігаються у списку CLOSED. Список OPEN представлений як пріоритетна черга, така, що невідповідні вузли можна видалити у порядку їхньої функції оцінки (нагадаємо чергу пріорітетів з розділу 2 для пошуку рівних витрат).
+У результатах пошуку «найкращий-перший» пошуковий простір оцінюється за евристичною функцією. Вузли, які ще підлягають оцінці, зберігаються у списку OPEN, а ті, які вже були оцінені, зберігаються у списку CLOSED. Список OPEN представлений як пріоритетна черга, така, що невідповідні вузли можна видалити у порядку їхньої функції оцінки.
 Функція оцінки f (n) складається з двох частин. Це евристична функція (h (n)) та орієнтовна вартість (g (n)), де (див. Формулу 3.1):
   f (n) = g (n) + h (n)      (Формула 3.1)

@@ Рядок 11: / Рядок 11: @@
 ==  «НАЙКРАЩИЙ-ПЕРШИЙ» ПОШУК.РЕАЛІЗАЦІЯ ==
-Давайте тепер розглянемо просту реалізацію "найкращого-першого" пошуку на мові C. Ми представимо дві основні функції, які складають цей алгоритм пошуку; перша - best_fs, яка є основним циклом алгоритму. Друга функція, generateChildNodes, створює можливі стани (конфігурації дошки) з урахуванням поточного стану.
+Давайте тепер розглянемо просту реалізацію "найкращого-першого" пошуку на мові [[C| C]]. Ми представимо дві основні функції, які складають цей алгоритм пошуку; перша - best_fs, яка є основним циклом [[алгоритм |алгоритму]]. Друга функція, generateChildNodes, створює можливі стани (конфігурації дошки) з урахуванням поточного стану.
 Наша головна функція (best_fs) - це перелік і тестування рішень списку OPEN. Перед викликом цієї функції створено наш список OPEN (пріоритетна черга) та CLOSED. Корневий вузол, наша початкова конфігурація дошки, була поміщена в список OPEN. Функція best_fs (див. Лістинг 3.1) видаляє наступний вузол з відкритого списку (найкращий f (n)). Якщо цей вузол має g (n) (кількість конфліктів) нуля, то рішення знайдено і ми виходимо.
@@ Рядок 89: / Рядок 89: @@
 == ВАРІАНТИ «НАЙКРАЩОГО-ПЕРШОГО» ПОШУКУ ==
-Один цікавий варіант найкращого першого пошуку називається жадібним «найкращим-першим» пошуком. У цьому варіанті f (n) = h (n), а список OPEN упорядковано у f порядку. Оскільки h є єдиним фактором, який використовується для визначення того, який вузол вибрати далі (ідентифікується як близькість до цілі), він визначається як жадібний. Через це жадібний «найкращий – перший» не є повним, оскільки евристика неприйнятна (оскільки вона може переоцінити шлях до мети). Ми розглянемо допустимість більш докладно в обговоренні пошуку A*.
+Один цікавий варіант найкращого першого пошуку називається жадібним «найкращим-першим» пошуком. У цьому варіанті f (n) = h (n), а список OPEN упорядковано у f порядку. Оскільки h є єдиним фактором, який використовується для визначення того, який вузол вибрати далі (ідентифікується як близькість до цілі), він визначається як жадібний. Через це жадібний «найкращий – перший» не є повним, оскільки [[Евристика|евристика]] неприйнятна (оскільки вона може переоцінити шлях до мети). Ми розглянемо допустимість більш докладно в обговоренні [[Пошук А*| пошуку A*]].
 Інший варіант «найкращого-першого» пошуку - пошук пробілу, як і жадібний «найкращий-перший» пошук, він використовує евристичну функцію f (n) = h (n). Різниця з промінь-пошуком полягає в тому, що він зберігає лише набір кращих вузлів кандидатів для розширення і просто кидає інший спосіб. Це робить промінь-пошук набагато ефективнішим з більшим обсягом пам’яті, ніж жадібний «найкращий-перший» пошук, але неефективний тим, що вузли можуть бути відкинуті, і це може призвести до оптимального шляху. З цієї причини промінь-пошук не є оптимальним або повним.
 '''Виконала [[User:Назаренко Валерія|Назаренко Валерія]]'''

← Попередня версія		Версія за 10:44, 20 лютого 2018
Рядок 92:		Рядок 92:
	Інший варіант «найкращого-першого» пошуку - пошук пробілу, як і жадібний «найкращий-перший» пошук, він використовує евристичну функцію f (n) = h (n). Різниця з промінь-пошуком полягає в тому, що він зберігає лише набір кращих вузлів кандидатів для розширення і просто кидає інший спосіб. Це робить промінь-пошук набагато ефективнішим з більшим обсягом пам’яті, ніж жадібний «найкращий-перший» пошук, але неефективний тим, що вузли можуть бути відкинуті, і це може призвести до оптимального шляху. З цієї причини промінь-пошук не є оптимальним або повним.		Інший варіант «найкращого-першого» пошуку - пошук пробілу, як і жадібний «найкращий-перший» пошук, він використовує евристичну функцію f (n) = h (n). Різниця з промінь-пошуком полягає в тому, що він зберігає лише набір кращих вузлів кандидатів для розширення і просто кидає інший спосіб. Це робить промінь-пошук набагато ефективнішим з більшим обсягом пам’яті, ніж жадібний «найкращий-перший» пошук, але неефективний тим, що вузли можуть бути відкинуті, і це може призвести до оптимального шляху. З цієї причини промінь-пошук не є оптимальним або повним.

−	Виконала [[User:Назаренко Валерія\|Назаренко Валерія]].	+	'''Виконала [[User:Назаренко Валерія\|Назаренко Валерія]]'''

← Попередня версія		Версія за 10:43, 20 лютого 2018
Рядок 92:		Рядок 92:
	Інший варіант «найкращого-першого» пошуку - пошук пробілу, як і жадібний «найкращий-перший» пошук, він використовує евристичну функцію f (n) = h (n). Різниця з промінь-пошуком полягає в тому, що він зберігає лише набір кращих вузлів кандидатів для розширення і просто кидає інший спосіб. Це робить промінь-пошук набагато ефективнішим з більшим обсягом пам’яті, ніж жадібний «найкращий-перший» пошук, але неефективний тим, що вузли можуть бути відкинуті, і це може призвести до оптимального шляху. З цієї причини промінь-пошук не є оптимальним або повним.		Інший варіант «найкращого-першого» пошуку - пошук пробілу, як і жадібний «найкращий-перший» пошук, він використовує евристичну функцію f (n) = h (n). Різниця з промінь-пошуком полягає в тому, що він зберігає лише набір кращих вузлів кандидатів для розширення і просто кидає інший спосіб. Це робить промінь-пошук набагато ефективнішим з більшим обсягом пам’яті, ніж жадібний «найкращий-перший» пошук, але неефективний тим, що вузли можуть бути відкинуті, і це може призвести до оптимального шляху. З цієї причини промінь-пошук не є оптимальним або повним.

−	[[User:Назаренко Валерія\|Назаренко Валерія]]	+	Виконала [[User:Назаренко Валерія\|Назаренко Валерія]].

← Попередня версія		Версія за 10:39, 20 лютого 2018
Рядок 91:		Рядок 91:
	Один цікавий варіант найкращого першого пошуку називається жадібним «найкращим-першим» пошуком. У цьому варіанті f (n) = h (n), а список OPEN упорядковано у f порядку. Оскільки h є єдиним фактором, який використовується для визначення того, який вузол вибрати далі (ідентифікується як близькість до цілі), він визначається як жадібний. Через це жадібний «найкращий – перший» не є повним, оскільки евристика неприйнятна (оскільки вона може переоцінити шлях до мети). Ми розглянемо допустимість більш докладно в обговоренні пошуку A*.		Один цікавий варіант найкращого першого пошуку називається жадібним «найкращим-першим» пошуком. У цьому варіанті f (n) = h (n), а список OPEN упорядковано у f порядку. Оскільки h є єдиним фактором, який використовується для визначення того, який вузол вибрати далі (ідентифікується як близькість до цілі), він визначається як жадібний. Через це жадібний «найкращий – перший» не є повним, оскільки евристика неприйнятна (оскільки вона може переоцінити шлях до мети). Ми розглянемо допустимість більш докладно в обговоренні пошуку A*.
	Інший варіант «найкращого-першого» пошуку - пошук пробілу, як і жадібний «найкращий-перший» пошук, він використовує евристичну функцію f (n) = h (n). Різниця з промінь-пошуком полягає в тому, що він зберігає лише набір кращих вузлів кандидатів для розширення і просто кидає інший спосіб. Це робить промінь-пошук набагато ефективнішим з більшим обсягом пам’яті, ніж жадібний «найкращий-перший» пошук, але неефективний тим, що вузли можуть бути відкинуті, і це може призвести до оптимального шляху. З цієї причини промінь-пошук не є оптимальним або повним.		Інший варіант «найкращого-першого» пошуку - пошук пробілу, як і жадібний «найкращий-перший» пошук, він використовує евристичну функцію f (n) = h (n). Різниця з промінь-пошуком полягає в тому, що він зберігає лише набір кращих вузлів кандидатів для розширення і просто кидає інший спосіб. Це робить промінь-пошук набагато ефективнішим з більшим обсягом пам’яті, ніж жадібний «найкращий-перший» пошук, але неефективний тим, що вузли можуть бути відкинуті, і це може призвести до оптимального шляху. З цієї причини промінь-пошук не є оптимальним або повним.
		+
		+	[[User:Назаренко Валерія\|Назаренко Валерія]]

@@ Рядок 1: / Рядок 1: @@
 У результатах пошуку «найкращий-перший» пошуковий простір оцінюється за евристичною функцією. Вузли, які ще підлягають оцінці, зберігаються у списку OPEN, а ті, які вже були оцінені, зберігаються у списку CLOSED. Список OPEN представлений як пріоритетна черга, така, що невідповідні вузли можна видалити у порядку їхньої функції оцінки (нагадаємо чергу пріорітетів з розділу 2 для пошуку рівних витрат).
 Функція оцінки f (n) складається з двох частин. Це евристична функція (h (n)) та орієнтовна вартість (g (n)), де (див. Формулу 3.1):
-f (n) = g (n) + h (n)      (Формула 3.1)
+ f (n) = g (n) + h (n)      (Формула 3.1)
 Ми можемо думати від оціночної вартості як вартості, що вимірюється в нашому просторі пошуку, та евристичну функцію як освічену здогадку. Список OPEN потім будується в порядку f (n). Це робить «найкращий-перший» пошук принципово ''жадібним'', тому що він завжди обирає найкращу місцеву можливість на пошуковій ''межі''.
 *''Примітка.''
@@ Рядок 40: / Рядок 40: @@
 Зауважте, що ми перевіряємо список CLOSED тут, щоб уникнути створення конфігурації дошки, яку ми бачили раніше. Після перевірки всіх позицій на поточній дошці та створення нових дочірніх вузлів, функція повертається до best_fs.
 Коли знайдено нову конфігурацію дошки, функція createNode викликається для виділення нової структури вузлів і розміщує цей новий вузол у списку OPEN (і у списку CLOSED). Зверніть увагу, що плюс глибина (h (n)) передається, щоб визначити рівень рішення в дереві.
 '''Нотатка: Функція generalChildNodes для нумерації дочірніх вузлів'''
   void generateChildNodes( pqueue_t *pq_p,
@@ Рядок 85: / Рядок 86: @@
   return;
+  }
-''ВАРІАНТИ «НАЙКРАЩОГО-ПЕРШОГО» ПОШУКУ''
- Один цікавий варіант найкращого першого пошуку називається жадібним «найкращим-першим» пошуком. У цьому варіанті f (n) = h (n), а список OPEN упорядковано у f порядку. Оскільки h є єдиним фактором, який використовується для визначення того, який вузол вибрати далі (ідентифікується як близькість до цілі), він визначається як жадібний. Через це жадібний «найкращий – перший» не є повним, оскільки евристика неприйнятна (оскільки вона може переоцінити шлях до мети). Ми розглянемо допустимість більш докладно в обговоренні пошуку A*.
+== ВАРІАНТИ «НАЙКРАЩОГО-ПЕРШОГО» ПОШУКУ ==
- Інший варіант «найкращого-першого» пошуку - пошук пробілу, як і жадібний «найкращий-перший» пошук, він використовує евристичну функцію f (n) = h (n). Різниця з промінь-пошуком полягає в тому, що він зберігає лише набір кращих вузлів кандидатів для розширення і просто кидає інший спосіб. Це робить промінь-пошук набагато ефективнішим з більшим обсягом пам’яті, ніж жадібний «найкращий-перший» пошук, але неефективний тим, що вузли можуть бути відкинуті, і це може призвести до оптимального шляху. З цієї причини промінь-пошук не є оптимальним або повним.

@@ Рядок 14: / Рядок 14: @@
 Наша головна функція (best_fs) - це перелік і тестування рішень списку OPEN. Перед викликом цієї функції створено наш список OPEN (пріоритетна черга) та CLOSED. Корневий вузол, наша початкова конфігурація дошки, була поміщена в список OPEN. Функція best_fs (див. Лістинг 3.1) видаляє наступний вузол з відкритого списку (найкращий f (n)). Якщо цей вузол має g (n) (кількість конфліктів) нуля, то рішення знайдено і ми виходимо.
-'''Нотатка: Головна функция «найкращого» пошуку.'''
+'''Нотатка: Головна функция «найкращого» пошуку'''
   void best_fs ( pqueue_t *open_pq_p, queue_t *closed_q_p )
+  {
@@ Рядок 36: / Рядок 36: @@
 ''В нотатці, в той час як вартість є f (n), ми перевіряємо g (n), щоб визначити, чи знайдено рішення. Це тому, що f (n) може бути ненульовим, оскільки
 ''він включає глибину рішення (h (n)).''
 Наступна функція, generateChildNodes, приймає поточну конфігурацію дошки та перераховує всі можливі дочірні конфігурації, потенційно переміщуючи кожну королеву на одну позицію. Масив рухів визначає можливі рухи для кожного положення на дошці (-1 означає лише правий, 2 означає як ліворуч, так і праворуч, а 1 означає лише лівий). Потім дошку перераховують, і коли королева виявляється, масив ходів перевіряється на легальні ходи, а нові дочірні вузли створюються та завантажуються в список OPEN.
 Зауважте, що ми перевіряємо список CLOSED тут, щоб уникнути створення конфігурації дошки, яку ми бачили раніше. Після перевірки всіх позицій на поточній дошці та створення нових дочірніх вузлів, функція повертається до best_fs.
 Коли знайдено нову конфігурацію дошки, функція createNode викликається для виділення нової структури вузлів і розміщує цей новий вузол у списку OPEN (і у списку CLOSED). Зверніть увагу, що плюс глибина (h (n)) передається, щоб визначити рівень рішення в дереві.
-Нотатка: Функція generalChildNodes для нумерації дочірніх вузлів
+'''Нотатка: Функція generalChildNodes для нумерації дочірніх вузлів'''
   void generateChildNodes( pqueue_t *pq_p,
   queue_t *closed_q_p, node_t *node_p )

← Попередня версія		Версія за 10:30, 20 лютого 2018
Рядок 36:		Рядок 36:
	''В нотатці, в той час як вартість є f (n), ми перевіряємо g (n), щоб визначити, чи знайдено рішення. Це тому, що f (n) може бути ненульовим, оскільки		''В нотатці, в той час як вартість є f (n), ми перевіряємо g (n), щоб визначити, чи знайдено рішення. Це тому, що f (n) може бути ненульовим, оскільки
	''він включає глибину рішення (h (n)).''		''він включає глибину рішення (h (n)).''
		+	Наступна функція, generateChildNodes, приймає поточну конфігурацію дошки та перераховує всі можливі дочірні конфігурації, потенційно переміщуючи кожну королеву на одну позицію. Масив рухів визначає можливі рухи для кожного положення на дошці (-1 означає лише правий, 2 означає як ліворуч, так і праворуч, а 1 означає лише лівий). Потім дошку перераховують, і коли королева виявляється, масив ходів перевіряється на легальні ходи, а нові дочірні вузли створюються та завантажуються в список OPEN.
		+	Зауважте, що ми перевіряємо список CLOSED тут, щоб уникнути створення конфігурації дошки, яку ми бачили раніше. Після перевірки всіх позицій на поточній дошці та створення нових дочірніх вузлів, функція повертається до best_fs.
		+	Коли знайдено нову конфігурацію дошки, функція createNode викликається для виділення нової структури вузлів і розміщує цей новий вузол у списку OPEN (і у списку CLOSED). Зверніть увагу, що плюс глибина (h (n)) передається, щоб визначити рівень рішення в дереві.
		+	Нотатка: Функція generalChildNodes для нумерації дочірніх вузлів
		+	void generateChildNodes( pqueue_t *pq_p,
		+	queue_t closed_q_p, node_t node_p )
		+	{
		+	int i;
		+	unsigned short cboard1, cboard2;
		+	const int moves[16]={ -1, 2, 2, 1,
		+	-1, 2, 2, 1,
		+	-1, 2, 2, 1,
		+	-1, 2, 2, 1 };
		+	/* Generate the child nodes for the current node by
		+	* shuffling the pieces on the board.
		+	*/
		+	for (i = 0 ; i < 16 ; i++) {
		+	/* Is there a queen at this position? */
		+	if (checkPiece( node_p->board, i )) {
		+	/* Remove current queen from the board */
		+	cboard1 = cboard2 = ( node_p->board & ~(1 << (15-i) ) );
		+	if (moves[i] == -1) {
		+	/* Can only move right */
		+	cboard1 \|= ( 1 << (15-(i+1)) );
		+	if (!searchQueue( closed_q_p, cboard1)) {
		+	(void)createNode( pq_p, closed_q_p, cboard1, node_p->h+1 );
		+	}
		+	} else if (moves[i] == 2) {
		+	/* Can move left or right */
		+	cboard1 \|= ( 1 << (15-(i+1)) );
		+	if (!searchQueue( closed_q_p, cboard1)) {
		+	(void)createNode( pq_p, closed_q_p, cboard1, node_p->h+1 );
		+	}
		+	cboard2 \|= ( 1 << (15-(i-1)) );
		+	if (!searchQueue( closed_q_p, cboard2)) {
		+	(void)createNode( pq_p, closed_q_p, cboard2, node_p->h+1 );
		+	}
		+	} else if (moves[i] == 1) {
		+	/* Can only move left */
		+	cboard2 \|= ( 1 << (15-(i-1)) );
		+	if (!searchQueue( closed_q_p, cboard2)) {
		+	(void)createNode( pq_p, closed_q_p, cboard2, node_p->h+1 );
		+	}
		+	}
		+	}
		+	}
		+	return;
		+	}
		+	''ВАРІАНТИ «НАЙКРАЩОГО-ПЕРШОГО» ПОШУКУ''
		+	Один цікавий варіант найкращого першого пошуку називається жадібним «найкращим-першим» пошуком. У цьому варіанті f (n) = h (n), а список OPEN упорядковано у f порядку. Оскільки h є єдиним фактором, який використовується для визначення того, який вузол вибрати далі (ідентифікується як близькість до цілі), він визначається як жадібний. Через це жадібний «найкращий – перший» не є повним, оскільки евристика неприйнятна (оскільки вона може переоцінити шлях до мети). Ми розглянемо допустимість більш докладно в обговоренні пошуку A*.
		+	Інший варіант «найкращого-першого» пошуку - пошук пробілу, як і жадібний «найкращий-перший» пошук, він використовує евристичну функцію f (n) = h (n). Різниця з промінь-пошуком полягає в тому, що він зберігає лише набір кращих вузлів кандидатів для розширення і просто кидає інший спосіб. Це робить промінь-пошук набагато ефективнішим з більшим обсягом пам’яті, ніж жадібний «найкращий-перший» пошук, але неефективний тим, що вузли можуть бути відкинуті, і це може призвести до оптимального шляху. З цієї причини промінь-пошук не є оптимальним або повним.