Відмінності між версіями «ПОШУК «НАЙКРАЩИЙ-ПЕРШИЙ» (BEST-FS)»!!!

Поточна версія на 13:50, 20 лютого 2018

У результатах пошуку «найкращий-перший» пошуковий простір оцінюється за евристичною функцією. Вузли, які ще підлягають оцінці, зберігаються у списку OPEN, а ті, які вже були оцінені, зберігаються у списку CLOSED. Список OPEN представлений як пріоритетна черга, така, що невідповідні вузли можна видалити у порядку їхньої функції оцінки. Функція оцінки 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;
}

• Примітка.

В нотатці, в той час як вартість є f (n), ми перевіряємо g (n), щоб визначити, чи знайдено рішення. Це тому, що f (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). Різниця з промінь-пошуком полягає в тому, що він зберігає лише набір кращих вузлів кандидатів для розширення і просто кидає інший спосіб. Це робить промінь-пошук набагато ефективнішим з більшим обсягом пам’яті, ніж жадібний «найкращий-перший» пошук, але неефективний тим, що вузли можуть бути відкинуті, і це може призвести до оптимального шляху. З цієї причини промінь-пошук не є оптимальним або повним.

Виконала Назаренко Валерія