Обучение лучшим способам поиска
Выше было представлено несколько стратегий поиска (поиск в ширину, жадный поиск по первому наилучшему совпадению и т.д.), которые были разработаны учеными и специалистами по компьютерным наукам. Но может ли сам агент обучаться лучшим способам поиска? Ответ на этот вопрос является положительным, а применяемый при этом метод обучения опирается на важную концепцию, называемую пространством состояний, рассматриваемым на метауровне, или метауровневым пространством состояний. Каждое состояние в метауровневом пространстве состояний отражает внутреннее (вычислительное) состояние программы, выполняющей поиск в пространстве состояний, рассматриваемом на уровне объектов, или в объектно-уровневом пространстве состояний, таком как карта Румынии. Например, внутреннее состояние алгоритма А* включает в себя текущее дерево поиска. Каждое действие в метауровневом пространстве состояний представляет собой этап вычисления, который изменяет внутреннее состояние, например, на каждом этапе вычисления в процессе поиска А* развертывается один из листовых узлов, а его преемники добавляются к дереву. Таким образом, рис. 4.2, на котором показана последовательность все больших и больших деревьев поиска, может рассматриваться как изображающий путь в метауровневом пространстве состояний, где каждое состояние в пути является объектно-уровневым деревом поиска.
В настоящее время путь, показанный на рис. 4.2, имеет пять этапов, включая один этап (развертывание узла Fagaras), который нельзя назвать слишком полезным. Может оказаться, что при решении более сложных задач количество подобных ненужных этапов будет намного больше, а алгоритм метауровневого обучения может изучать этот опыт, чтобы в дальнейшем избегать исследования бесперспективных поддеревьев. Методы, используемые при обучении такого рода, описаны в главе 21. Целью обучения является минимизация суммарной стоимости решения задач, а также поиск компромисса между вычислительными издержками и стоимостью пути.
В этом разделе будут рассматриваться эвристические функции для задачи игры в восемь, что позволяет лучше продемонстрировать характерные особенности всех эвристических функций в целом.
Головоломка "игра в восемь" была одной из первых задач эвристического поиска. Как было указано в разделе 3.2, в ходе решения этой головоломки требуется передвигать фишки по горизонтали или по вертикали на пустой участок до тех пор, пока полученная конфигурация не будет соответствовать целевой конфигурации.