Що таке ідеальна евристична функція?

Подумайте про ідеальну евристику h(n). Він дає точну найкоротшу відстань до мети від n. Тому функція вартості f(s) для кожного вузла s на найкоротшому шляху буде однаковою і дорівнюватиме довжині найкоротшого шляху: пройдена відстань плюс точна найкоротша відстань до мети.7 жовтня 2013

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

Ідеальна евристика. Визначення (ідеальна евристика) Нехай S — простір станів зі станами S. Ідеальна евристика для S, записана h∗, відображає кожен стан s ∈ S на вартість оптимального рішення для s. зауваження: h∗(s) = ∞, якщо не існує розв’язку для s.

Коли ми використовуємо евристику вибору найкращого, ми приймаємо рішення на основі лише однієї ознаки чи характеристики, яка, на нашу думку, відрізняє варіанти. Замість того, щоб розглядати всі причини, чому ми можемо обрати одну альтернативу замість іншої, ми обираємо одну причину й ґрунтуємо своє рішення виключно на цій причині.

Деякі автори використовували «пошук найкращий спочатку» для конкретного позначення пошуку з евристикою, яка намагається передбачити, наскільки близько кінець шляху до рішення (або цілі), так що шляхи, які вважаються ближчими до рішення (або цілі), продовжуються першими.

Але в більш широкому вживанні термін евристика став означати будь-яке емпіричне правило для прийняття рішень. Наприклад, якщо ви шукаєте певний експонат у Британському музеї, ви можете використати евристику першого пошуку кімнати з експозицією на пов’язану тему.