Что такое государственный космический поиск в искусственном интеллекте

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

CSC447 – Весна 2009 г.

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

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

Чтобы получить интуитивное представление о концепции пространства состояний, давайте рассмотрим довольно простой конкретный пример — головоломку с числом 8. Если вы не знакомы с этой головоломкой со скользящими блоками, вот три программы, которые вы можете скачать, чтобы набраться опыта:

Обратите внимание, что четвертый включает расширения головоломки до 4 х 4, 5 х 5 и 6 х 6.

Довольно простую головоломку с восьмерками можно сделать более интересной, установив ее в трех измерениях вместо двух. Поскольку представить трехмерную головоломку непросто, и даже в этом случае невозможно увидеть все 27 блоков одновременно, она была представлена ​​в виде трех двухмерных головоломок. Головоломки с тремя разными начальными конфигурациями здесь:

8 Пространство состояния головоломки:

Легко видеть, что каждое перемещение меняет конфигурацию плиток. Каждая такая конфигурация называется государство. Из любой конфигурации можно сделать два, три или четыре хода. И, конечно же, каждый ход приводит к новой конфигурации. Таким образом, состояния (конфигурации) связаны друг с другом ходами. На этом этапе мы можем опираться на концепции дискретной математики. Каждое состояние может быть представлено вершиной, а каждое движение — ребром, что дает нам неориентированный граф. Граф неориентированный, так как каждое движение обратимо.

Полученный таким образом граф называется государственное пространство. Еще одно замечание: ученые-компьютерщики обычно называют вершины узлы и края дуги.

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

Будучи головоломкой, головоломку 8 можно рассматривать как проблему: какая последовательность ходов позволит нам вернуть головоломку в исходное состояние? И чаще всего мы ставим второе условие задачи — найти кратчайшую последовательность таких ходов.

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

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

объявить: puzzGraph(1, numNodes) :: gNode

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

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

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

Некоторые основные термины:

Теперь мы готовы дать определения основных концепций поиска в пространстве состояний.

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

в виде последовательности действий.

Состояние: дискретная, идентифицируемая конфигурация, которую может принять проблема.

Исходное(ые) состояние(я): одно или несколько состояний, представляющих отправную точку в

поиск целевого состояния (состояний).

Целевое состояние (состояния): одно или несколько состояний, которые представляют собой решение проблемы.

Действия: шаги, которые можно предпринять для продвижения к цели.

Оператор: специальное описание действия, которое может указывать (1)

условия, необходимые для совершения действия, и (2) положение о том, что

результат этого действия.

Пространство состояний: множество всех состояний, достижимых из начального состояния любым

последовательность действий — часто представляемая в виде графа с состояниями

узлы и действия дуги.

Путь в пространстве состояний: любая последовательность действий, ведущих из одного состояния в другое.

Целевой тест: тест, который можно применить, чтобы определить, является ли текущее состояние

Функция стоимости пути: функция, которая назначает стоимость пути, обозначается грамм.

в виде последовательности действий.

Эвристическая функция: функция, которая оценивает стоимость пути от текущего

состояние к целевому состоянию.

Решение: путь из начального состояния в состояние, удовлетворяющее целевому тесту.

Коэффициент ветвления: количество состояний (в среднем), в которые можно попасть из

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

Эффективный коэффициент ветвления: количество новый произведены узлы.

Fringe (граница): набор узлов, ожидающих расширения.

Расширение узла: выполнение всех возможных действий и создание узлов для состояний

Стратегия поиска: рубрика для принятия решения о том, какой узел расширять следующим

Измерение эффективности решения проблем:

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

1. Находит ли решение?

2. Является ли это хорошим решением (недорогой путь)?

3. Какова стоимость поиска?

В отношении каждого из них необходимо сделать пояснение. Во-первых, не каждая стратегия гарантированно находит решение, даже если оно существует.Во-вторых, хотя в идеале мы хотели бы найти оптимальное решение, в некоторых случаях мы довольствуемся «хорошим» решением, если затраты на поиск оптимального решения чрезмерны. И в-третьих, затраты на поиск чаще всего связаны с пространством (требованиями к памяти) и временем.

Таким образом, мы можем измерить эффективность стратегии, используя следующие критерии:

Полнота: гарантированно ли стратегия найдет решение, когда оно есть?

Оптимальность: если есть несколько решений, находит ли лучшее?

Временная сложность: сколько времени нужно, чтобы найти решение?

Пространственная сложность: сколько памяти нужно для поиска?

Основные категории поиска:

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

Неинформированный поиск (слепой поиск): не использует информацию о поиске

пространство (даже если такая информация доступна), кроме базового узла/узла

Информированный поиск (эвристический поиск): использует дополнительную информацию о

пространство поиска, такое как оценки расстояния несмежных узлов.