Обзор исследований в области искусственного интеллекта
в данном состоянии нет очевидного
Например, в данном состоянии нет очевидного очередного хода, т.е. оказывается, что все возможные ходы одинаково хороши (или плохи). Это не что иное, как выход на "плато" в нашем восхождении, когда ни один из возможных путей не влечет за собой подъем. Другой возможный источник затруднений — наличие локальных максимумов, из которых возможен только спуск, т.е. "ухудшение" состояния. Например, я могу взять вашего ферзя и после этого проиграть партию.
Лучшими свойствами обладает другая форма эвристического поиска, которая получила наименование сначала наилучший (best-first search). Так же, как и в варианте восхождения на гору, в нашем распоряжении имеется оценочная функция, с помощью которой можно сравнивать состояния в пространстве состояний. Основное же отличие нового метода от ранее рассмотренного состоит в том, что сравниваются не только те состояния, в которые возможен переход из текущего, но и все, до которых "можно достать".
Такой алгоритм, естественно, требует значительно больших вычислительных ресурсов, но идея состоит в том, чтобы принимать во внимание не только ближайшие состояния, т.е. локальную обстановку, а "окинуть взглядом" как можно больший участок пространства состояний и быть готовым, в случае необходимости, вернуться туда, где мы уже были, и пойти другим путем, если ближайшие претенденты не сулят существенного прогресса в достижении цели (см. описание алгоритма А во врезке 2.2). Вот эта возможность отказаться от части пройденного пути во имя глобальной цели и позволяет найти более эффективный путь. Необходимость хранить ранее сделанные оценки состояний и постоянно их обновлять, конечно, требует значительных вычислительных ресурсов.
2.2. Алгоритм А
Существует хорошо известный алгоритм поиска, который относится к группе первый лучший, получивший наименование А (произносится "А со звездочкой"). Основная идея алгоритма состоит в использовании для каждого узла п на графе пространства состояний оценочной функции вида
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий