Главная arrow Поиск arrow Поиск решений
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Поиск решений Печать

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

На рисунке показаны некоторые расширения дерева поиска, предназначенного для определения маршрута от Арада до Бухареста. Корнем этого дерева поиска является поисковый узел, соответствующий начальному состоянию, In(Arad). Первый этап состоит в проверке того, является ли это состояние целевым. Безусловно, что оно не является таковым, но необходимо предусмотреть соответствующую проверку, чтобы можно было решать задачи, содержащие в себе готовое решение, такие как «начав путешествие с города Арад, прибыть в город Арад». А в данном случае текущее состояние не является целевым, поэтому необходимо рассмотреть некоторые другие состояния.

Такой этап осуществляется путем развертывания текущего состояния, т.е применения функции определения преемника к текущему состоянию для формирования в результате этого нового множества состояний. В данном случае будут получены три новых состояния: In (Sibiu), In (Timisoara) и In (Zerind).

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

Предположим, что вначале выбран город Сибиу. Проведем проверку для определения того, соответствует ли он целевому состоянию (не соответствует), а затем развернем узел Sibiu для получения состояний In(Arad), In(Fagaras), In(Oradea) и In(RimnicuVilcea). После этого можно выбрать любое из этих четырех состояний либо вернуться и выбрать узел Timisoara или Zerind. Необходимо снова и снова выбирать, проверять и развертывать узлы до тех пор, пока не будет найдено решение или не останется больше состояний, которые можно было бы развернуть. Порядок, в котором происходит развертывание состояний, определяется стратегией поиска. Общий алгоритм поиска в дереве неформально представлен в листинге.

а) Начальное состояние

б) После развертывания узла Arad

в) После развертывания узла Sibiu


Частично развернутые деревья поиска, предназначенные для определения маршрута от Арада до Бухареста. Развернутые узлы затенены; узлы, которые были сформированы, но еще не развернуты, выделены полужирным контуром; узлы, которые еще не были сформированы, обозначены тонкими штриховыми линиями


function Tree-Search(problem, strategy) returns решение solution
  или индикатор неудачи failure
  инициализировать дерево поиска с использованием начального
  состояния задачи problem
  loop do
    if нет кандидатов на развертывание then return индикатор
      неудачи failure
      выбрать листовой узел для развертывания в соответствии
      со стратегией strategy
    if этот узел содержит целевое состояние
    then return соответствующее решение solution
    else развернуть этот узел и добавить полученные узлы
      к дереву поиска



Необходимо учитывать различие между пространством состояний и деревом поиска. В пространстве состояний для задачи поиска маршрута имеется только 20 состояний, по одному для каждого города. Но количество путей в этом пространстве состояний является бесконечным, поэтому дерево поиска имеет бесконечное количество узлов. Например, первыми тремя путями любой бесконечной последовательности путей являются маршруты Арад—Сибиу, Арад—Сибиу—Арад, Арад—Сибиу—Арад—Сибиу. (Безусловно, качественный алгоритм поиска должен исключать возможность формирования таких повторяющихся путей.)

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

  • State. Состояние в пространстве состояний, которому соответствует данный узел.
  • Parent-Node. Узел в дереве поиска, применявшийся для формирования данного узла (родительский узел).
  • Action. Действие, которое было применено к родительскому узлу для формирования данного узла.
  • Path-Cost. Стоимость пути (от начального состояния до данного узла), показанного с помощью указателей родительских узлов, которую принято обозначать как д(п).
  • Depth. Количество этапов пути от начального состояния, называемое также глубиной.

Необходимо учитывать различие между узлами и состояниями. Узел — это учетная структура данных, применяемая для представления дерева поиска, а состояние соответствует конфигурации мира. Поэтому узлы лежат на конкретных путях, которые определены с помощью указателей Parent-Node, а состояния— нет. Кроме того, два разных узла могут включать одно и то же состояние мира, если это состояние формируется с помощью двух различных путей поиска. Структура данных узла показана на рисунке.


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

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

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

  • Make-Queue (element,...). Создает очередь с заданным элементом (элементами).
  • Empty? (queue). Возвращает истинное значение, только если в очереди больше нет элементов.
  • First (queue). Возвращает первый элемент в очереди.
  • Remove-First (queue). Возвращает элемент First (queue) и удаляет его из очереди.
  • Insert (element, queue). Вставляет элемент в очередь и возвращает результирующую очередь. (Ниже будет показано, что в очередях различных типов вставка элементов осуществляется в различном порядке.)
  • Insert-All (elements, queue). Вставляет множество элементов в очередь и возвращает результирующую очередь.

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


function Tree-Search(problem, fringe) returns решение solution
или индикатор неудачи failure
  fringe
<— Insert(Make-Node(Initial-State[problem]), fringe)
  loop do
    if Empty?(fringe) then return индикатор неудачи failure
      node <— Remove-First(fringe)
    if Goal-Test[problem] применительно к State[node]
      завершается успешно
    then return Solution(node)
      fringe <— Insert-All(Expand(node, problem), fringe)
function Expand(node, problem) returns множество узлов successors
successors <— пустое множество
  for each <action, result> in Successor-Fn[problem] (State[node]) do
    s <— новый узел
    State[s] <— result
    Parent-Node[s] <— node
    Action[s] <— action
    Path-Cost[s] <— Path-Cost[node] + Step-Cost(node, action, s)
    Depth[s] <— Depth[node] + 1
    добавить узел s к множеству successors
return successors


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

  • Полнота. Гарантирует ли алгоритм обнаружение решения, если оно имеется?
  • Оптимальность. Обеспечивает ли данная стратегия нахождение оптимального решения, в соответствии с определением.
  • Временная сложность. За какое время алгоритм находит решение?
  • Пространственная сложность. Какой объем памяти необходим для осуществления поиска?

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

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

Временная сложность часто измеряется в терминах количества узлов, вырабатываемых5 в процессе поиска, а пространственная сложность— в терминах максимального количества узлов, хранимых в памяти.

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

Поэтому для вычисления суммарной стоимости нам придется складывать километры и миллисекунды. Между этими двумя единицами измерения не определен «официальный курс обмена», но в данном случае было бы резонно преобразовывать километры в миллисекунды с использованием оценки средней скорости автомобиля (поскольку для данного агента важным является именно время). Это позволяет рассматриваемому агенту найти оптимальную точку компромисса, в которой дальнейшие вычисления для поиска более короткого пути становятся непродуктивными.