Поиск в пространстве состояний

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

Definition

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

Scope

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

Core questions

• Как задача представляется в виде состояний, действий, модели перехода и целевого критерия?
• Чем отличаются поиск в ширину, поиск в глубину, поиск с равномерной стоимостью и поиск с итеративным углублением по порядку обработки границы?
• Каковы гарантии полноты, оптимальности, времени и пространства для каждой неинформированной стратегии?
• Как графовый поиск избегает расточительного повторного исследования состояний, которое допускает древовидный поиск?

Key concepts

• начальное состояние и целевой критерий
• модель перехода и преемники
• граница (открытый список) и исследованное множество
• поиск в ширину
• поиск в глубину
• поиск с равномерной стоимостью
• итеративное углубление
• древовидный поиск против графового поиска

Key theories

Порядок обработки границы определяет стратегию

Неинформированные алгоритмы поиска различаются только порядком, в котором они удаляют состояния из границы: очередь FIFO дает поиск в ширину, стек LIFO дает поиск в глубину, а очередь с приоритетом по стоимости пути дает поиск с равномерной стоимостью.

Итеративное углубление как оптимальный по пространству вариант

Поиск в глубину с итеративным углублением многократно выполняет поиск в глубину с ограничением глубины с увеличивающимися пределами, сочетая линейное пространство поиска в глубину с полнотой и оптимальностью (при единичных затратах) поиска в ширину.

Clinical relevance

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

History

Систематический поиск в пространстве состояний берет начало от алгоритмов обхода графов 1950-х годов, включая работы Мура и Дейкстры по кратчайшим путям, и был сформулирован как модель решения задач в раннем ИИ. Анализ Корфа 1985 года итеративного углубления установил его оптимальность среди допустимых древовидных поисков с линейным пространством.

Key figures

• Nils J. Nilsson
• Richard E. Korf
• Edward F. Moore
• Edsger W. Dijkstra

Seminal works

• nilsson1971
• russell2020

Frequently asked questions

Когда поиск в ширину оптимален?

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

Почему следует использовать итеративное углубление вместо обычного поиска в ширину?

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