2.4. ЗАПИСЬ В ВИДЕ ГРАФА

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

Граф состоит из множества (не обязательно конечного) вершин. Некоторые пары вершин соединены с помощью дуг, и эти дуги направлены от одного члена этой пары к другому. Такие графы носят название направленных графов. Если некоторая дуга направлена от вершины к вершине то говорят, что вершина является дочерней вершиной для вершины я», а вершина является родительской вершиной для Может оказаться, что некие две вершины будут дочерними друг для друга; в этом случае пара направленных дуг называется иногда ребром графа. В случае когда граф используется для

представления пространства состояний, с его вершинами связывают описания состояний, а с его дугами — операторы.

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

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

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

Найти путь между вершиной и любым элементом множества вершин

Найти путь между любым элементом множества и любым элементом множества

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

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

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

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

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