Відмінності між версіями «ПОШУК «НАЙКРАЩИЙ-ПЕРШИЙ» (BEST-FS)»!!!
Матеріал з wiki
Onpage keywords chain search with * wildcard.
Example: sear* my nam* will find Searh my names and search my Name
111 (обговорення • внесок) (Створена сторінка: У результатах пошуку «найкращий-перший» пошуковий простір оцінюється за евристичною ф...) |
111 (обговорення • внесок) |
||
| Рядок 1: | Рядок 1: | ||
У результатах пошуку «найкращий-перший» пошуковий простір оцінюється за евристичною функцією. Вузли, які ще підлягають оцінці, зберігаються у списку OPEN, а ті, які вже були оцінені, зберігаються у списку CLOSED. Список OPEN представлений як пріоритетна черга, така, що невідповідні вузли можна видалити у порядку їхньої функції оцінки (нагадаємо чергу пріорітетів з розділу 2 для пошуку рівних витрат). | У результатах пошуку «найкращий-перший» пошуковий простір оцінюється за евристичною функцією. Вузли, які ще підлягають оцінці, зберігаються у списку OPEN, а ті, які вже були оцінені, зберігаються у списку CLOSED. Список OPEN представлений як пріоритетна черга, така, що невідповідні вузли можна видалити у порядку їхньої функції оцінки (нагадаємо чергу пріорітетів з розділу 2 для пошуку рівних витрат). | ||
| − | Функція оцінки f (n) складається з двох частин. Це евристична функція (h (n)) та орієнтовна вартість (g (n)), де (див. Формулу 3.1): | + | *Функція оцінки 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 ) вартістю). | + | *Складність «найкращого-першого» пошуку є O(b^m ) для часу і простору (всі вузли зберігаються в пам'яті). Підтримуючи список CLOSED (щоб уникнути перегляду вузлів і, отже, уникати циклів), «найкращий- перший» пошук завершено, але це не є оптимальним, оскільки рішення можна знайти довшим шляхом (вищим h (n) з нижчою g (n ) вартістю). |
| − | ''Примітка. | + | *''Примітка''. |
| − | «Найкращий-Перший» пошук - це комбінація функцій оцінки h (n) і g (n). Зверніть увагу, що пошук «Широкий-Перший» є окремим випадком пошуку «Найкращий-Перший», де f (n) = h (n), а пошук рівномірної ціні - це особливий випадок пошуку «Найкращий-Перший», де f (n) = g (n) | + | *''«Найкращий-Перший» пошук - це комбінація функцій оцінки h (n) і g (n). Зверніть увагу, що пошук «Широкий-Перший» є окремим випадком пошуку «Найкращий-Перший», де f (n) = h (n), а пошук рівномірної ціні - це особливий випадок пошуку «Найкращий-Перший», де f (n) = g (n)''. |
Версія за 12:47, 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).
