PDF-лекции, страница 11

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

1(а). В ней используетсяпятнадцать пронумерованных (от 1 до 15) подвижных фишек, расположенных в клетках квадрата 44.Одна клетка этого квадрата остается всегда пустой, так что одну из соседних с ней фишек можнопередвинуть на место этой пустой клетки, изменив тем самым местоположение пустой клетки. Заметим,что более простым вариантом этой головоломки является квадрат 33 и восемь фишек на нем – примерсоответствующей задачи показан на рис.1(б).На рис.1(а) изображены две конфигурации фишек. В головоломке требуется преобразоватьпервую, или начальную, конфигурацию во вторую, или целевую конфигурацию. Решением этой задачибудет подходящая последовательность сдвигов фишек, например: передвинуть фишку 8 вверх, фишку 6влево и т.д.111713Рис.1935248101512614а)1591326101437111548122 8 31 6 47  5б)1 2 38  47 6 5Важной особенностью класса задач, к которому принадлежит рассмотренная головоломка,относится наличие в задаче точно определенной начальной ситуации и точно определенной цели.Имеется также некоторое множество операций, или ходов, переводящих одну конфигурацию в другую.Именно из таких ходов состоит искомое решение задачи, которое можно в принципе получить методомпроб и ошибок.

Действительно, отправляясь от начальной ситуации, можно построить конфигурации,возникающие в результате выполнения возможных в этой ситуации ходов, затем построить множествоконфигураций, получающихся после применения следующего хода, и так далее – пока не будетдостигнута целевая конфигурация.Введем теперь основные понятия, используемые при формализации задачи в пространствесостояний. Центральным из них является понятие состояния, характеризующего некоторый момент37решения задачи. Например, для игры в пятнадцать (или в восемь) состояние – это просто некотораяконкретная конфигурация фишек.Среди всех состояний задачи выделяются начальное состояние и целевое состояние, всовокупности определяющие задачу, которую надо решить  примеры их приведены на рис.1.Другим важным понятием является понятие оператора, т.е.

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

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

Тогда решение задачи будет путь в этом графе, ведущий от начальногосостояния к целевому. На рис.2 показана часть пространства состояний для игры в пятнадцать: в каждойвершине помещена та конфигурация фишек, которую она представляет. Все дуги между вершинамиявляются двунаправленными, поскольку в этой головоломке для любого оператора есть обратный ему(точнее, множество операторов состоит из двух пар взаимно-обратных операторов: влево-вправо, вверхвниз).Пространства состояний могут быть большими и даже бесконечными, но в любом случаепредполагается счетность множества состояний.Таким образом, в подходе к решению задачи с использованием пространства состояний задачарассматривается как тройка ( SI , O , SG ) , гдеSI – начальное состояние;O – конечное множество операторов, действующих на не более чем счетном множестве состояний;SG – целевое состояние.Дальнейшая формализация решения задачи с использованием пространства состоянийпредполагает выбор некоторой конкретной формы описания состояний задачи.

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

При использовании же продукционного языка, эти операторы задаются в виде правил продукцийвида: «исходное состояние  результирующее состояние».В рассмотренных выше примерах (игры в пятнадцать и восемь) искомое целевое состояниезадавалось явно, т.е. известно было местоположение каждой фишки в целевой конфигурации. В болеесложных случаях игры может быть несколько целевых состояний, либо же целевое состояние можетбыть определено неявно, т.е. охарактеризовано некоторым свойством, например, как состояние, вкотором сумма номеров фишек в верхнем ряду не превосходит 10. В подобных случаях свойство,которому должно удовлетворять целевое состояние, должно быть описано исчерпывающим образом, кпримеру, путем задания булевской функции, реализующей проверку нужного свойства состояниязадачи.Итак, для представления задачи в пространстве состояний необходимо определить следующее: форму описания состояний задачи и описание начального состояния; множество операторов и их воздействий на описания состояний;38 множество целевых состояний или же описание их свойств.Перечисленные составляющие задают неявно граф-пространство состояний, в котором требуетсяпровести поиск решения задачи.

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

Действительно, просмотр осуществляется как последовательный поиск, или переборвершин, в пространстве состояний. В исходной точке процесса к начальному состоянию применяетсятот или иной оператор и строится новая вершина-состояние, а также связывающие ее с корневойвершиной дуги. На каждом последующем шаге поиска к одной из уже полученных вершин-состоянийприменяется допустимый оператор и строится еще одна вершина графа и связывающие дуги. Этотпроцесс поиска продолжается до тех пор, пока не будет построена вершина, соответствующая целевомусостоянию.Рис.21117131117139524381015126141117131117133529481015126149352481093524810151261411171315126141117139352154810126149352412810156141117131117139352481093524 158 12 610 141512614Примеры пространств состоянийРазберем два характерных примера представления в пространстве состояний, показывающих,что такое представление возможно для различных типов задач.

Подчеркнем заранее, чтопредлагаемые ниже представления, хотя и являются достаточно естественными, не являютсяединственно допустимыми в этих задачах, возможны и другие варианты.Вообще, от выбора представления, т.е. рассмотренных выше составляющих, зависит размер пространства состояний, а значит, иэффективность поиска в нем. Очевидно, желательны представления с малыми пространствами состояний, но нахождение сужающихпространство поиска удачных представлений требует обычно некоторого дополнительного анализа решаемой задачи.Рассмотрим формализацию в пространстве состояний известной задачи о коммивояжере (представляющей классическуюпереборную проблему). Коммивояжер, располагая картой дорог, соединяющей 7 городов (рис. 3), должен построить свой маршрут так,чтобы выехав из города А, посетить каждый из других шести городов B, C, D, E, H, G в точности по одному разу и затем вернуться вABGE39DHРис.

3Cисходный город. В другом, более сложном варианте задачи требуется также, чтобы маршрут имел минимальную протяженность.Состояние решаемой задачи можно задать как список городов, которые уже проехалкоммивояжер к текущему моменту. Тогда возможным состояниям соответствуют списки из элементовA, B, C, D, E, H, G без повторений, исключение составляет только город A, он может встретиться всписке дважды – в начале списка и его конце. Пример списка-состояния – (A B C H). Начальное жесостояние определяется как список (A), а целевое – как любой допустимый список, начинающийся икончающийся элементом A.

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