- Всё это прекрасно - скажет пресловутый пытливый читатель, - но каким образом Прологу удаётся проделывать такие фокусы ? Не обладает же он и в самом деле искусственным интеллектом ?
- Нет, - ответим мы пытливому читателю. - Пролог не обладает искусственным интеллектом. Вместо интеллекта в этот язык встроен механизм, называемый backtracking, работу которого мы сейчас подробно рассмотрим.
Для этой цели отвлечёмся от родственных связей, которые, надо думать, вам уже порядком поднадоели, и попробуем решить задачу о направленных графах[1]. Графом в математике называется множество поименнованных вершин (на рисунке можно обозначит их кружочками с буквами внутри), которые каким-то образом связаны между собой (на рисунке роль связей могут играть линии, соединяющие кружочки). Направленным называется граф, вершины которого связаны не в обе стороны, а только в одну (это проще всего изобразить стрелками). Вот типичный пример простого направленного графа:
Для работы с графом будем пользоваться двумя предикатами: edge (грань) и path (путь). Грань в этом случае - это направленная связь между двумя вершинами, например такая: edge(a,b). Как видите, порядок следования вершин определяет напавление связи. Путь - это можество граней, которые организованы таким образом, что, следуя по стрелкам от одной вершины к другой, можно дойти от первой вершины пути до последней. Например, path(a,e) - это существующий путь, потому что его можно пройти по вершинам a,c,d,e, а path(e,c) не существует, потому что никаким образом, выйдя из вершины e, нельзя достичь вершины c.
Наша задача - определить понятие пути в терминах Пролога. Естественно, путь будет определяться с помощью грани. Имея в виду только что приведённый пример, мы можем с лёгкостью выписать все известные факты о гранях:
edge(a,b).
edge(a,c).
edge(c,d).
edge(d,b).
edge(d,e).
А теперь попробуем определить путь. Как обычно, начнём с самого простого. Ни у кого не вызовет сомнений следующий тривиальный факт:
path(X,X).
Обратите внимание, что в этом случае использована переменная (а не атом ) X. Таким образом, факт этот работает для любой вершины, имя которой будет связано с переменной X. Это понятно - вершина всегда ведёт к самой себе, не проходя при этом ни по каким граням.
А вот другой, тоже не слишком сложный вывод:
path(X,Y) :- edge(X,Y).
Понятно, что, если между двумя вершинами есть грань (то есть стрелка, ведущая от первой вершины ко второй), то между ними есть и путь.
И, наконец, общий случай определения пути. Если вы вспомните, каким образом были определены понятия "потомок" и "предок", вам ничего не будет стоить понять следующее определение:
path(X,Z) :- edge(X,Y), path(Y,Z).
Как говорится, путь в тысячу ли начинается с одного шага: вот и на графе, чтобы пройти целый путь, нужно сначала сделать шаг длиной в одну грань, а потом пройти остаток пути. Читатели этого курса уже настолько свыклись с такого рода проделками, что должны чувствовать себя в этом месте словно рыба в воде.
Теперь, когда вся подготовительная работа проделана, мы готовы приступить к разбору механизма backtracking.
Предположим, что Прологу задана следующая цель:
?- path(a,e).
То есть, мы хотим узнать, существует ли путь от вершины а к вершине е на заданном графе. Пролог приступает к работе.
Первым делом, интерпретатор пробует унифицировать заданный предикат с первым, который ему известен, а именно: path(X,X).
Но а и е - вершины разные, они не унифицируются с X и X. Не получилось - идём дальше и пробуем следующее известное правило path(X,Y) :- edge(X,Y).
В этом случае переменная X связывается с именем а, а переменная Y связывается с именем е. Правило заставляет Пролог применить его правую часть к связанным переменным, и вот что получается: edge(a,e).
Неудача! Такой грани нет, то есть нет такого факта (взгляните ещё раз на факты, описывающие наш граф). Пролог, однако, не отчаивается, потому что у него в запасе ещё один - последний вариант: path(X,Z) :- edge(X,Y), path(Y,Z).
Теперь переменная X связывается с именем а, а переменная Z связывается с именем е, и в результате "раскрытия" правила получается вот что:
edge(a,Y), path(Y,e).
А именно: чтобы существовал путь от вершины а к вершине е, нужно найти грань, соединяющую вершину а с некоей вершиной Y, а затем определить, существует ли путь от этой вершины Y к вершине е.
Пролог сейчас займётся в точности этой задачей: сначала попробует найти вершину от а к некоей Y, а затем определить путь.
Чтобы связать переменную Y с именем вершины, Пролог возьмёт в качестве кандидата первый известный ему факт о гранях, в котором роль первой вершины играет а. И этот факт нам известен не хуже, чем Прологу - edge(a,b). Обратите внимание - с этого момента переменная Y связана с вершиной b, а стало быть и во всех последующих вычислениях b будет играть роль Y. С первым предикатом правила покончено (ибо он просто факт), поэтому Пролог начинает решать второй предикат правила, а именно path(Y,e), который теперь выглядит как path(b,e).
История повторяется: Прологу не удаётся унифицировать path(b,e) с двумя первыми правилами, поэтому он начинает проверять третье правило –
path(X,Z) :- edge(X,Y), path(Y,Z), которое, будучи "раскрытым", выглядит как edge(b,Y1), path(Y1,e).
Обратите внимание, что мы назвали переменную Y - Y1, потому что это уже другая переменная (хоть и взятая из того же самого правила. Ведь роль "настоящей" Y играет сейчас сама вершина b!
Далее, по логике вещей, Пролог должен подыскать факт, подходящий под определение edge(b,Y1). И вот тут-то его и ожидает неудача! Ведь такого факта попросту не существует, потому что не существует грани, первой вершиной которой была бы вершина b!
Что делать ?! Главное - не отчаиваться, потому что на помощь нам приходит тот самый backtracking, изучением которого мы и занимаемся.
Пролог сейчас должен вернуться к той самой точке, откуда и начались все беды, но - и это исключительно важно! - точка должна быть уникальной - не выше и не ниже того самого уровня на "дереве решения" задачи, откуда интерпретатор двинулся по ложному пути. Так что же это за точка ? Нам нужно вспомнить, то есть внимательно просмотреть весь ход рассуждений, а Прологу в этом поможет механизм backtracking'а!
Не поленимся и перепишем ещё раз слова, приведшие к неправильному выбору:
"...Чтобы связать переменную Y с именем вершины, Пролог возьмёт в качестве кандидата первый известный ему факт о гранях, в котором роль первой вершины играет а. И этот факт нам известен не хуже, чем Прологу - edge(a,b)...".
Стоп! Вот она - точка отсчёта. Факт оказался неправильным. Механизм backtracking'а поднимается до этого места и предлагает Прологу выбрать следующий известный ему факт о гранях, в котором роль первой вершины играет а, а именно edge(a,c).
Теперь, действуя по уже известной нам схеме, "раскроем" правило пути в такой вид: edge(c,Y2), path(Y2,e).
Удача: грань, ведущая из вершины c существует: edge(c,d).
Продолжим "раскрывать" второй предикат, используя d в качестве Y2: path(d,e). И здесь нас ждёт ещё одна удача, ведь уже второе правило path(X,Y) :- edge(X,Y)
решает заданную цель: edge(d,e) существует, а стало быть и путь path(d,e)тоже существует.
Мы дошли до победного конца - все цели достигнуты, все переменные унифицированы. И вывод из этого очень простой: путь path(a,e)существует, и на поставленный вначале вопрос Пролог ответит:
yes
А теперь, чтобы увидеть всю картину целиком, взгляните на рисунок:
Цифры на рисунке не несут какого-либо глубокого смысла, кроме того, чтобы удобнее было следить за "ходом мысли" Пролога, странствующего по дереву целей.
Раскрывать внутренние механизмы работы Пролога - занятие неблагодарное. Это то же самое, что объяснить как устроен замысловатый фокус - магия сразу же теряется. И тем не менее, изучение механизма backtracking'а необходимо для понимания сути логического программирования и для более эффективного использования этого прекрасного и в чём-то загадочного языка.
[1] С помощью нехитрого сравнения приведённого графа и генеалогического древа греческих богов читатель может легко убедиться, что далеко уйти от начальной точки нам всё-таки не удалось. Конечно же - генеалогическое древо - это частный случай направленного графа. Вы ещё раз сможете убедиться в этом, когда мы будем писать "программу" для определения понятия "путь".