Дискретная математика:
логика, группы, графы, фракталы

Акимов О.Е.

3.4. Лингвистические и поисковые графы

Другие поисковые задачи

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

Не станем спешить с вычерчиванием громоздких графов. Вместо этого сразу же введем коды. Отдельным состояниям и переходам между состояниями поставим в соответствие две тройки переменных. Пусть тройка UVW характеризует переходы, а тройка XYZ — состояния. Переменные принимают следующие значения: U — число миссионеров на плоту, V — число туземцев-каннибалов на плоту, W — переменная, принимающая значение в зависимости от направления движения: либо к левому берегу (0), либо к правому берегу (1), X — число миссионеров на левом берегу, Y — число туземцев-каннибалов на левом берегу, Z — переменная, тоже принимающая значение левого (0) или правого (1) берега. Этих условных обозначений будет достаточно, чтобы, не вычерчивая полный граф разрешенных и неразрешенных состояний, указать правильные решения. В пространстве переходов цепь, приводящая к нужному решению, в соответствии с введенными кодами UVW, будет выглядеть следующим образом:

111 – 100 – 021 – 010 – 201 – 110 – 201 – 010 – 021 – 010 – 021.

Мы могли бы начать не с переходов 111 – 100 – 021, а с перехода 121 – 010 – 021, который образует короткую параллельную ветвь, также ведущую к единственному верному решению. И концовку выписанной цепи можно было бы представить иначе: вместо кодов 010 – 021 – 010 – 021 написать 010 – 100 – 110 – 021. Это еще один параллельный отрезок для решения задачи. Теперь через коды состояний XYZ выпишем цепь, ведущую к правильному решению:

330 – 221 – 320 – 301 – 310 – 111 – 220 – 021 – 030 – 011 – 020 – 001.

Существование двух небольших параллельных цепей дает возможность замены состояний 221 и 020 на 311 и 110 соответственно. Отметим также, что общее число всех состояний для данной задачи равно 43; из них 27 являются запрещенными и 16 разрешенными. Путь к правильному решению, включая начальное и конечное, состоит из 12 состояний.

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

Программист, работающий на языке ПРОЛОГ, в соответствии с нашими кодами переходов UVW и состояний XYZ мог бы ввести две трехместные предикатные функции: переход (u,v,w), состояние (x,y,z) и на базе этих предикатов составить ПРОЛОГ-программу. Перебор состояний по невычерченному нами графу поиска в ПРОЛОГЕ можно осуществить по нескольким стратегиям, начиная либо с исходного состояния, либо с целевого, либо идти с обоих концов одновременно. Часто говорят о вертикальной и горизонтальной прогонке; естественно, существует и смешенная стратегия, когда ПРОЛОГ-система спускается по вертикали вглубь до какого-то уровня, а дальше двигается по горизонтали вширь тоже до каких-то разумных пределов. Такая смешанная стратегия поиска хороша в том случае, если характер поискового графа неизвестен, но заранее известно, что он насчитывает многие тысячи и миллионы разрешенных состояний. К тем простым задачам, которые мы здесь разобрали, подобные алгоритмические ухищрения применять не нужно, так как 43 узла компьютер обойдет в доли секунды.

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

Рис. 3.66

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

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

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