Як максимум множини допустимих евристиків, домінуючих евристичних? - пошук, штучний інтелект, а-зірка, евристика

Якщо у вас є набір допустимих евристики: h1,h2,h2,...,hn

Як h = max(h1,h2,h2,...,hn) допустимий евристичний, який панує над ними всіх?

Чи не є нижчим значенням h (n) значення краще?

Для*, f = g + n, і елемент з найменшим f буде видалений зі списку. Так що не треба брати min дати домінуючу евристику?

Відповіді:

Допустимий евристичний інструмент ніколи не переоцінюєвартість досягнення мети держави. Тобто його оцінка буде нижчою, ніж фактична вартість або точно фактична вартість, але ніколи не вище. Це потрібно для жадібних підходів, таких як A * пошук, щоб знайти найкраще глобальне рішення.

Наприклад, уявіть, що ви знайшли рішення звартість 10. Найкраще рішення коштувало 8. Ви не використовуєте допустимий евристичний ефект, а оцінка евристичного рішення, яке дійсно коштує 8, становить 12 (це завищує). Оскільки у вас вже є рішення з вартістю 10, A * ніколи не буде оцінювати найкраще рішення, оскільки це, як вважається, дорожче.

В ідеалі, ваш евристичний має бути настільки ж точним, якможливо, тобто допустимий евристичний засіб не слід недооцінювати справжню вартість занадто багато.Якщо це так, A * все одно знайде найкраще рішення врешті-решт, але це може зайняти набагато довше, тому що він намагається багато рішень, які добре виглядають згідно з вашим евристичним, але виявиться поганим.

Тут лежить відповідь на ваше запитання. Ваша евристика h1, ..., hn є допустимими, тому вони оцінюють вартість, яка дорівнює чи менше реальних витрат. The максимум з цього набору оцінок є, за визначенням, оцінкою, яка є найближчий до фактичних витрат (пам'ятайте, що ви ніколи не переоцінюєте). У ідеальному випадку це буде точною ціною.

Якщо б ви мали взяти мінімальне значення, то ви отримаєте оцінку, яка є далеко від фактичної вартості - як зазначено вище, A * як і раніше знайти найкраще рішення, але набагато менш ефективним способом.