Відмінності між версіями «ПОШУК «НАЙКРАЩИЙ-ПЕРШИЙ» (BEST-FS)»!!!
111 (обговорення • внесок) |
111 (обговорення • внесок) |
||
| Рядок 16: | Рядок 16: | ||
'''Нотатка: Головна функция «найкращого» пошуку''' | '''Нотатка: Головна функция «найкращого» пошуку''' | ||
| − | <code>void best_fs ( pqueue_t *open_pq_p, queue_t *closed_q_p ) | + | <code> |
| + | void best_fs ( pqueue_t *open_pq_p, queue_t *closed_q_p ) | ||
{ | { | ||
node_t *node_p; | node_t *node_p; | ||
| Рядок 32: | Рядок 33: | ||
} | } | ||
return; | return; | ||
| − | } </code> | + | } |
| + | </code> | ||
Версія за 13:03, 20 лютого 2018
У результатах пошуку «найкращий-перший» пошуковий простір оцінюється за евристичною функцією. Вузли, які ще підлягають оцінці, зберігаються у списку OPEN, а ті, які вже були оцінені, зберігаються у списку CLOSED. Список OPEN представлений як пріоритетна черга, така, що невідповідні вузли можна видалити у порядку їхньої функції оцінки (нагадаємо чергу пріорітетів з розділу 2 для пошуку рівних витрат). Функція оцінки f (n) складається з двох частин. Це евристична функція (h (n)) та орієнтовна вартість (g (n)), де (див. Формулу 3.1): f (n) = g (n) + h (n) (Формула 3.1) Ми можемо думати від оціночної вартості як вартості, що вимірюється в нашому просторі пошуку, та евристичну функцію як освічену здогадку. Список OPEN потім будується в порядку f (n). Це робить «найкращий-перший» пошук принципово жадібним, тому що він завжди обирає найкращу місцеву можливість на пошуковій межі.
- Примітка.
Межа пошуку визначається як набір можливостей вузлів, які можна знайти в наступному. У «найкращому-першому» пошуку, межа - це черга пріоритетів, відсортована у f (n) порядку. З огляду на строгий порядок f (n), вибір вузла для оцінки з черги приорітетів є жадібним.
Складність «найкращого-першого» пошуку є O(b^m ) для часу і простору (всі вузли зберігаються в пам'яті). Підтримуючи список CLOSED (щоб уникнути перегляду вузлів і, отже, уникати циклів), «найкращий- перший» пошук завершено, але це не є оптимальним, оскільки рішення можна знайти довшим шляхом (вищим h (n) з нижчою g (n ) вартістю).
- Примітка.
«Найкращий-Перший» пошук - це комбінація функцій оцінки h (n) і g (n). Зверніть увагу, що пошук «Широкий-Перший» є окремим випадком пошуку «Найкращий-Перший», де f (n) = h (n), а пошук рівномірної ціні - це особливий випадок пошуку «Найкращий-Перший», де f (n) = g (n).
«НАЙКРАЩИЙ-ПЕРШИЙ» ПОШУК.РЕАЛІЗАЦІЯ
Давайте тепер розглянемо просту реалізацію "найкращого-першого" пошуку на мові C. Ми представимо дві основні функції, які складають цей алгоритм пошуку; перша - best_fs, яка є основним циклом алгоритму. Друга функція, generateChildNodes, створює можливі стани (конфігурації дошки) з урахуванням поточного стану. Наша головна функція (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 )
{
node_t *node_p;
int cost;
/* Enumerate the Open list */
while ( !isEmptyPQueue (open_pq_p) ) {
dePQueue ( open_pq_p, (int *)&node_p, &cost );
/* Solution found? */
if (node_p->g == 0) {
printf(“Found Solution (depth %d):\n”, node_p->h);
emitBoard ( node_p );
break;
}
generateChildNodes( open_pq_p, closed_q_p, node_p );
}
return;
}
Developed by Інститут Програмних Систем
