Теория графов

Размещено на http://www.allbest.ru/

Лекция

Графы

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

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

Берег реки 1

Берег реки 2

Задача о кенигсбергских мостах формулируется следующим образом. Существует ли маршрут обхода города, при котором каждый мост пересекается ровно один раз? Хотя местные жители после безуспешных попыток найти такой маршрут усомнились в его существовании, никто не мог доказать его отсутствие. Создав модель графа, Эйлер реализовал альтернативное представление карты города. Берега реки (rb1 и rb2) и острова (i1 и i2) описываются вершинами графа; мосты представлены помеченными дугами между вершинами (b1 , b2, ..., b7). Представление в виде графа сохраняет существенную информацию (структуру системы мостов), а несущественные данные (расстояние и направление) игнорируются.

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

Кроме того, систему кенигсбергских мостов можно представить в терминах исчисления предикатов. Предикат connect (соединить) соответствует дуге графа и утверждает, что берега реки или острова связаны некоторым мостом. Для каждого моста необходимо задать два предиката connect -- по одному для каждого направления движения по мосту.

connect(i1, i2, b1) connect(i2, i1, b1)

connect(rb1, i1, b2) connect(i1, rb1, b2)

connect(rb1, i1, b3) connect(i1, rb1, b3)

connect(rb1, i2, b4) connect{i2, rb1, b4)

connect(rb2, i1, b5) connect(i1, rb2, b5)

connect(rb2, i1, b6) connect(i1, rb2, b6)

connect(rb2, i2, b7) connect(l2, rb2, b7)

Выражение connect(X,Y,Z)=connect(Y,X,Z), указывающее на то, что каждый мост может быть пройден в любом направлении, позволяет исключить половину предикатов.

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

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

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

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

Теория графов

Структуры данных для поиска в пространстве состояний

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

Дуги графа также могут быть размеченными. Метка дуги используется для задания именованного отношения либо веса дуги (как в задаче о коммивояжере). Дуги между двумя вершинами тоже можно различать с помощью меток.

Размеченный ориентированный граф

Граф называется ориентированным, если каждой дуге приписано определенное направление. Дуги в ориентированном графе обычно содержат стрелки, определяющие ориентацию дуги. Дуги, которые можно проходить в любом из двух направлений, могут содержать две стрелки-указателя, но чаще вовсе не имеют стрелок. На рисунке по дуге (a, b) можно двигаться лишь от вершины a к вершине b, по дуге (b, c) можно двигаться в любом из двух направлений.

Путь на графе - это последовательность дуг, соединяющих соседние вершины. Путь представляется списком дуг, систематизированным в порядке их следования. На рисунке список [a, b, c, d] представляет путь, проходящий через вершины a, b, c, d в указанном порядке.

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

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

Корневое дерево как пример семейных отношений

Для корневых деревьев или графов отношения между вершинами описываются понятиями родителя, потомка и вершин-братьев -- вершин дерева, имеющих общую вершину-родителя. Они используются в обычном смысле наследования: при проходе вдоль направленной дуги родитель предшествует потомку. Концы всех направленных дуг, исходящих из одной вершины, называются вершинами-братьями. Аналогично на пути ориентированного графа предок предшествует потомку. На рисунке вершина b является родителем вершин e и f (которые являются потомками b и вершинами-братьями). Вершины a и c являются предками вершин g, h, i, a вершины g, h, i являются потомками a и c.

Определение

Граф состоит из множества вершин N1, N2,..., Nn, которое не обязано быть конечным, и множества дуг, соединяющих некоторые пары вершин.

Дуги являются упорядоченными парами вершин; т.е. дуга (N3, N4) соединяет вершину N3 с вершиной N4, но не вершину N4 с N3, если (N4, N3) не является дугой. В противном случае дуга, соединяющая N3 с N4, является ненаправленной.

Если направленная дуга соединяет вершины Nj и Nk, то Nj называется родителем Nk, а Nk -- потомком Nj. Если граф содержит также дугу (Nj, Ni), то Nk и Ni, называются вершинами-братьями.

Корневой граф имеет единственную вершину Ns, в которую не входит ни одна дуга. Таким образом, корень графа не имеет родителей.

Концевая вершина -- это вершина, которая не имеет потомков.

Упорядоченная последовательность вершин [N1, N2, N3, ..., Nn], где каждая пара (Ni, Ni+1) является дугой, называется путем длины n-1 на графе.

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

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

Дерево -- это граф, в котором существует единственный путь между любыми двумя вершинами. (Следовательно, пути в дереве не содержат циклов).

Ребра в корневом дереве ориентированы от корня. Каждая вершина в корневом дереве имеет единственного родителя.

Две вершины называются связными, если существует путь, содержащий эти вершины.

Представление задачи в пространстве состояний

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

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

Определение

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

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

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

задачи.

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

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

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

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

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

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

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

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

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

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

Пример “Крестики-нолики”

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

Состояниями в пространстве являются все возможные конфигурации из крестиков и ноликов, которые могут возникнуть в процессе игры. Конечно, большинство из возможных З вариантов расположения символов {пусто, X, О} в девяти клетках никогда не возникает в реальной игре. Дуги определяются допустимыми ходами игры, которые состоят в поочередном записывании X или О в пустую клетку. Граф пространства состояний не является деревом, поскольку некоторые состояния третьего и более глубоких уровней могут быть достигнуты различными путями. Однако в пространстве состояний нет циклов, так как ориентированные дуги графа не позволяют возвращаться в уже пройденное состояние. Если состояние достигнуто, вернуться вверх по графу невозможно. Следовательно, нет необходимости проверки на цикл. Граф с этим свойством называется ациклическим ориентированным графом и часто встречается при поиске в пространстве состояний.

Вид пространства состояний дает возможность определить сложность задачи. В игре "крестики-нолики" возможны девять первых ходов и восемь ответов противника на каждый из них, затем следуют семь возможных вариантов поставить крестик и т.д. Следовательно, имеется 9х8х7х...х1=9! всевозможных путей. Такое количество путей (362880) компьютер способен обработать непосредственно полным перебором. Однако существует немало важных задач, имеющих очень высокую факториальную или экспоненциальную сложность, которая на много порядков выше, чем в этом случае. Например, в шахматах имеется 10 возможных игровых путей; в шашках -- 10, причем некоторые из них никогда не возникают в реальных играх. Такие пространства чрезвычайно сложны, и их невозможно исследовать простым перебором вариантов. Стратегии поиска в пространствах больших размеров используют эвристики, позволяющие уменьшить сложность поиска.

Пример “8-головоломка”

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

В игре в "пятнашки" с пятнадцатью фишками, или 15-головоломке, на рисунке пятнадцать пронумерованных фишек размещены на поле из 16 клеток. Одна клетка остается пустой, так что фишки можно двигать и получать их различные конфигурации. Цель игры -- найти такую последовательность перемещений фишек в пустую клетку, которая привела бы к заранее заданной целевой конфигурации. С одной стороны, пространство состояний этой игры является достаточно большим, чтобы представлять интерес, а с другой -- вполне доступным для анализа. Число возможных состояний составляет 16!. 8-головоломка -- это версия 15-головоломки размерности 3x3. В этой головоломке 8 фишек можно передвигать в пространстве из 9 клеток.

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

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

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

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

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

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

Как и при игре в «крестики-нолики», пространство состояний этой игры является графом, большинство вершин которого имеет много предков. Но, в отличие от крестиков-ноликов, в этом графе возможны циклы. Множество целевых состояний, или GD, -- это особое множество конфигураций. Если одно из них встречается на пути, поиск прекращается. Путь из начальной вершины в целевую -- искомая последовательность ходов.

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

Пример “Задача коммивояжера”

Предположим, коммивояжер должен посетить пять городов и возвратиться домой. Задача состоит в том, чтобы найти кратчайший путь. На рисунке дан пример этой задачи. Вершины графа представляют города, а метка на каждой дуге указывает стоимость путешествия по ней. Эта стоимость может означать длину отрезка пути в милях, если коммивояжер пользуется автомобилем, или цену авиабилета при использовании самолета. Для удобства предположим, что коммивояжер проживает в городе А и должен вернуться в город А. Это предположение попросту сводит задачу с n-городами к проблеме с n-1 городом.

Рассмотрим один из возможных путей [A, D, C, B, E, A] длиной (стоимостью путешествия) в 450 миль. Целью является нахождение пути кратчайшей длины, т.е. построение цепочки с минимальной стоимостью. Цель -- это глобальное свойство графа, а не свойство отдельного состояния.

Путь: ABCDEA Путь: ABCEDA Путь: ABDCEA …

Стоимость: 375 Стоимость: 425 Стоимость: 475

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

Исчерпывающий поиск в задаче коммивояжера состоит в переборе (N-1)! вариантов, где N -- число вершин графа (или число городов). Для 9 городов можно непосредственно проверить все вершины. Но в реальных ситуациях, например для 50 городов, непосредственный перебор невозможен. На самом деле сложность вычислений N! растет столь быстро, что очень скоро прямой перебор всех вариантов станет неосуществимым.

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

Представление рассуждений в пространстве состояний на основе исчисления предикатов

Описание пространства состояний логической системы

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

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

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

Пример “Исчисление высказываний”

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

qp

rp

vq

sr

tr

su

s

t

Из этого набора утверждений на основе правила модус поненс могут быть выведены определенные высказывания, в том числе p, r и u. Другие высказывания, в частности, v и q, не могут быть выведены таким способом. Действительно, они логически не следуют из этих утверждений. Отношения между начальными утверждениями и выведенными из них описаны на рисунке с помощью ориентированного графа.

Граф пространства состояний набора импликаций в исчислении высказываний

Дуги на рисунке соответствуют логическим импликациям (). Утверждения, которые считаются истинными (s и t), соответствуют исходным данным задачи. Логические следствия из данного набора утверждений соответствуют достижимым узлам. Путь на графе отражает последовательность применения правила модус поненс. Например, путь [s, r, р] соответствует такому ряду логических выводов.

Из s и sr следует r.

Из r и rр следует р.

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

Графы И/ИЛИ

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

В выражениях вида qrp для обеспечения истинности p должны быть истинны как q, так и r. В выражениях вида qrp истинность q или r достаточна для доказательства того, что p -- истина. Поскольку импликации (), содержащие дизъюнктивные () предпосылки, могут быть записаны как пары отдельных импликаций, это выражение часто записывается в виде qp, rp. Чтобы представить различные отношения графически, на графах И/ИЛИ различают узлы и(and) и или(or). Если предпосылки импликаций связаны оператором , они называются и-узлами графа, а дуги, ведущие от этих узлов, соединяются кривой.

Граф И/ИЛИ для выражения qrp

Кривая, соединяющая дуги на рисунке, означает, что для доказательства p должны быть истинными обе предпосылки: q и r. Если предпосылки соединены оператором ИЛИ, на графе они представляются узлами или. Дуги, ведущие от узлов или к следующей вершине, не соединяются кривой. Это указывает на то, что истина любой из предпосылок является достаточным условием для истинности заключения.

Граф И/ИЛИ выражения qrp

Граф И/ИЛИ является частным случаем гиперграфа, в котором узлы соединены не отдельными дугами, а множеством дуг. Приведем определение гиперграфа.

Определение

Гиперграф состоит из следующих элементов.

N -- множество вершин.

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

Гипердуги также называют k-коннекторами, где k -- мощность множества порожденных вершин. Если k= 1, то можно считать, что потомок является вершиной ИЛИ. Если k> 1, то элементы множества потомков являются вершинами и. В этом случае коннекторы изображаются в виде отдельных ребер, ведущих от родителя к каждой из порожденных вершин и соединенных изогнутой линией.

предикат граф логический поиск

Размещено на Allbest.ru