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

В главе 3 описано исчисление предикатов - пример языка представления в искусствен­ном интеллекте. Правильно составленные выражения исчисления предикатов позволяют опи­сывать объекты и отношения в области определения, а правила вывода (например, правило тodus poпeпs) - логически получать новые знания из имеющихся описаний. Эти правила вывода определяют пространство, в котором ведется поиск решения задачи.

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

Гарантировано ли нахождение решения в процессе поиска?

Является поиск конечным, или в нем возможны зацикливания?

Если решение найдено, является ли оно оптимальным?

Как процесс поиска зависит от времени выполнения и используемой памяти?

Как интерпретатор может наиболее эффективно упростить поиск?

Как разработать интерпретатор для наиболее эффективного использования языка

представления?

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

Граф состоит из множества вершин и дуг, соединяющих пары вершин. В модели про­странства состояний решаемой задачи вершины графа представляют дискретные со­стояния процесса решения, например, результаты логического вывода или различные конфигурации игровой доски. Дуги графа описывают переходы между состояниями. Эти переходы соответствуют логическим заключениям или допустимым ходам в игре. Так, в экспертных системах состояния описывают знания о задаче на определенном этапе исследования. Экспертные заключения в форме правил "если "', то" позволяют получить новую информацию. При этом каждый случай применения правила представляется какцуга между состояниями.

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

Острова и берега реки соединены семью мостами, как показано на рисунке 10.1.

Берег реки 1

Берег реки 2

Рис. 10.1. Город Кенигсберг

Задача о кенигсбергских мостах формулируется следующим образом. Существует ли маршрут обхода города, при котором каждый мост пересекается ровно один раз? Хотя местные жители после безуспешных попыток найти такой маршрут усомнились в его существовании, никто не мог доказать его отсутствие. Создав модель графа, Эйлер реа­лизовал альтернативное представление карты города (рис. 10.2). Берега реки ( rb1

и rb2 ) и острова (i1 и i2) описываются вершинами графа; мосты представлены помеченными ду­гами между вершинами ( b1, b2,..., b7. Представление в виде графа сохраняет существенную информацию (структуру системы мостов), а несущественные данные (расстояние и направление) игнорируются.

Рис. 10.2. Граф системы мостов города Кенигсберга

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

Эйлер заметил, что если число вершин нечетной степени не равно нулю либо двум, то маршрут невозможен. Если существуют ровно две вершины нечетной степени, то можно начать путь в одной из них и закончить в другой. Если же вершин нечетной степени не существует, то маршрут может начаться и закончиться в одной и той же вершине. Итак, маршрут невозможен, если число вершин нечетной степени графа от­лично от О или 2, как в задаче о кенигсбергских мостах. Эта задача называется задачей поиска пути Эйлера на графе.

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

Определим представление задачи в пространстве состояний более формально.

Пространство состояний представляется четверкой [N,A,S,GD] со следующими обозначениями.

N - множество вершин графа или состояний в процессе решения задачи.

А - множество дуг между вершинами, соответствующих шагам в процессе решения задачи.

S - это непустое множество начальных состояний задачи.

GD - непустое подмножество N, состоящее из целевых состояний. Эти состояния описываются одним из следующих способов.

1. Измеряемыми свойствами состояний, встречающихся в процессе поиска.

2. Свойствами путей, возникающих в процессе поиска, например, стоимостью пе­ремещения по дугам пути.

Допустимый путь - это путь из вершины множества S в вершину из множества GD.

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

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

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

Вершины={ а, b, c, d, e }

Дуги=={ (а, b), (а, d), (b,c), (c, b), (c, d),

(d, а), (d, e), (e,c), (e, d)}

Рисунок 10.3. Размеченный ориентированный граф.

Для корневых деревьев или графов отношения между вершинами описываются понятиями родителя, потомка и вершин-братьев (sibliпgs) - вершин дерева, имеющих об­щую вершину-родителя. Они используются в обычном смысле наследования: при прохо­де вдоль направленной дуги родитель предшествует потомку. Концы всех направленных дуг, исходящих из одной вершины, называются вершинами-братьями. Аналогично на пути ориентированного графа предок предшествует потомку. На рис. 10.4 вершина b

яв­ляется родителем вершин e и f, которые являются потомками b и вершинами­братьями. Вершины а и c являются предками вершин g, h, i, а вершины g, h, i являются потомками а и c.

Рисунок 10.4. Корневое дерево, как пример семейных отношений.

Одна из общих особенностей графа и одна из проблем, возникающих при создании алгоритма поиска на графе, состоит в том, что состояния иногда могут быть достигнуты разными путями. Например, на рис. 10.3 путь от вершины а к вершине d может проходить через вершины b и с либо непосредственно от а к d. Поэтому важно выбрать оптималь­ный путь решения данной задачи. Кроме того, множественные пути к состоянию могут привести к петлям или циклам. Тогда алгоритм никогда не достигнет цели. Если в каче­стве целевой вершины на рис. 10.3 выбрать вершину e, а в качестве начальной­ вершину а, то образуется циклический путь abcdabcdabcd...

Если пространство поиска описывается деревом, как на рис. 10.4, проблема зацикли­вания не возникает. Именно поэтому важно отличать задачи поиска на деревьях от задач поиска на графах с петлями. Алгоритмы поиска на произвольных графах должны обна­руживать и устранять петли в допустимых путях. При этом алгоритмы поиска на деревь­ях выигрывают в эффективности за счет отсутствия этих тестов и затрат на них.

Рассмотрим ещё один пример поиска в пространстве состояний, приведенный на рис. 10.5.

	С		А

В

А

?

Рисунок 10.5. Задача перестановки кубиков.

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

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

. поставить А на стол;

. поставить А на С;

. поставить С на А.

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

Как показывает и данный пример, при анализе подобной проблемы приходится

сталкиваться с двумя основными понятиями.

1. Проблемные ситуации.

2. Допустимые шаги, или действия, которые преобразуют одни nроблемные си­туации в другие.

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

Рисунок 10.6. Представление задачи перестановки кубиков в виде пространства состояний; полужирными стрелками обозначен путь решения задачи.

1

15-головоломка 8-головоломка

Рисунок 10.7. 15-головоломка и 8-головоломка

В игре в "пятнашки" с пятнадцатью фишками, или 15-головоломке, на рис. 10.7 пятнадцать пронумерованных фишек размещены на поле из 16 клеток. Одна клетка остается пустой, так что фишки можно двигать и получать их различные конфигурации. Цель иг­ры - найти такую последовательность перемещений фишек в пустую клетку, которая привела бы к заранее заданной целевой конфигурации.

Некоторые аспекты этой игры оказались весьма интересными для исследований в об­ласти искусственного интеллекта. С одной стороны, пространство состояний этой игры является достаточно большим, чтобы представлять интерес, а с другой - вполне дос­тупным для анализа (число возможных состояний составляет 16!, если различать сим­метричные состояния). Состояния игры легко представимы. Игра достаточно богата для апробации интересных эвристик.

8-головоломка - это версия 15-головоломки размерности 3х3. В этой головоломке 8 фишек можно передвигать в пространстве из 9 клеток. Поскольку пространство состояний, этой игры меньше, чем в 15-головоломке, именно ее мы будем использовать в по­следующих примерах. В реальной жизни ходы в головоломке заключаются в перемещении фишек ("передвинуть фишку 7 вправо при условии, что пустая клетка расположена справа от нее" или "переместить фишку 3 вниз"), однако значительно удобнее говорить о "перемещении пустой клетки". Это упрощает определение хода, так как в игре участвуют 8 фишек и только одна пустая клетка. Допустимыми являются следующие ходы.

Переместить пустую клетку вверх ↑

Переместить пустую клетку вправо →

Переместить пустую клетку вниз ↓

Переместить пустую клетку влево ← ­

Чтобы сделать очередной ход, необходимо удостовериться, что пустая клетка не вый­дет за пределы игрового поля. Поэтому в определенных ситуациях некоторые из четырех ходов могут оказаться недопустимыми. Например, если пустая клетка находится в одном из углов, то допустимы лишь два хода. Если определены начальное и конечное состоя­ние в 8-головоломке, то процесс решения задачи можно описать явно (рис. 10.8). Состоя­ния описываются массивом размерности 3 х 3. Дуги в пространстве состояний определяют четыре процедуры, описывающие возможные перемещения пустой клетки.

Рис. 10.8. Пространство состояний 8-головоломки, порожденное "перемещением пустой клетки"

Следует отметить, что полное пространство состояний 8-головоломки или 15­головоломки состоит из двух не связных подграфов (одинакового размера). Отсюда сле­дует, что ровно половина состояний являются недостижимыми из любой заданной на­чальной вершины. Если поменять местами (вопреки правилам!) две соседние фишки, все состояния из другой части пространства состояний окажутся достижимыми.

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

. Пространство состояний.

. Начальная вершина.

. Целевое состояние (состояние, которое должно быть достигнуто); целевыми вершинами называются такие вершины, которые соответствуют этому состоянию.

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

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