Искусственный интеллект

Лабораторная работа №4

«Стратегии эвристического поиска». (4 часа).

Цель работы: познакомиться с алгоритмом и характеристиками эвристического поиска, научиться использовать эти средства для решения поставленных задач.

Теоретические сведения:

Стратегии эвристического поиска являются более эффективными с точки зрения потребляемых ресурсов памяти и процессорного времени, чем стратегии слепого поиска. Стратегии эвристического поиска осуществляют выбор узла, подвергающегося расширению, на основании дополнительных знаний о проблеме, позволяющих на каждом шаге монотонно приближаться к решению.

В пространстве состояний поиска эвристика определяется как набор правил для выбора тех ветвей из пространства состояний, которые с наибольшей вероятностью приведут к приемлемому решению проблемы.

Поведение эвристики можно оценивать по ряду параметров. Например, наряду с ре­шением задачи может понадобиться алгоритм нахождения кратчайшего пути к нему. Это важно, когда каждый дополнительный шаг к цели имеет очень высокую стоимость, на­пример, при планировании пути для автономного робота в опасной среде. Эвристика, ко­торая находит самый короткий путь к цели, называется допустимой (admissible). В дру­гих приложениях кратчайший путь к решению может быть не так важен, как общая эф­фективность решения задачи.

Можно задать вопрос: существуют ли лучшие эвристики? И в каком смысле одна эв­ристика "лучше" другой? В этом состоит информированность (informedness) эвристики.

Можно ли гарантировать, что обнаруженное в процессе эвристического поиска со­стояние нельзя было найти по короткому пути от начального состояния? Это свойство называется монотонностью (nionotonicity).