Решение логических задач на языке Пролог

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

Рассмотрим пример: нарисовать конверт, не отрывая карандаша от бумаги и не проводя два раза по одной и той же линии.

Введем обозначения, как показано на рис. 2.3, а. Ребра графа обозначены буква­ми а, б, в... (литерные константы), вершины –
цифрами 1, 2, 3... Опишем струк­туру графа предикатом вида
“ребро (S, А, В)”, что означает, что от вершины А к вершине В идет
ребро S. Так как граф неориентированный, помимо предикатов вида “ребро (S, А, В)” нужны и предикаты “ребро (S, В, А)”. Знания о структуре графа можно представить так, как это записано
на рис. 2.3, б.

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

 

путь(Т,П): - длина(П,8), write_list(П),!. (1)

путь(Т,П): - ребро(Р,Т,Н),не_принад(Р,П),путь(Н,[Р|П]). (2)

 

Переменная Т обозначает текущую вершину графа, а П – список пройденных ребер. Правило 1 означает, что если длина списка П пройденных вершин становит­ся равной 8, список П выводится на печать. Это правило ограничивает рекурсив­ный перебор вершин и ребер, проводимый правилом 2. Правило 2 является генера­тором перебора, оно перебирает предикаты “ребро()”и находит такое ребро Р из текущей вершины Т в новую Н, чтобы оно не принадлежало списку П, затем это ребро добавляется в качестве головы к списку П, и поиск дальнейшего пути произ­водится уже из новой вершины Н.

Нам потребуется программа, определяющая длину списка,

 

длина ([],0).

длина ([А | В], N):- длина (В, М), N is M+1.

 

а также программа вывода элементов списка на экран

 

write_list([ ]).

write_list([H | T]):-write(H),write_list(Т).

 

Задание

?-путь(4,[ ]).

-искать путь, начиная с вершины 4 и пустого списка пройденных ребер.

Ответ: з, ж, в, а, б, е, г, д.

На вопрос?-путь(1,[ ]) ответ – “НЕТ”.

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

Программа будет состоять:

1) из базы знаний о структуре графа – вершинах и связывающих их ребрах (каждому ребру может сопоставляться набор весов);

2) из правил, выражающих дополнительные условия и ограничения на решения задачи и часто связанных с обработкой списков;

3) из рекурсивного правила – генератора перебора ребер и вершин с некоторым ограничивающим предложением, целевым условием;

4) из дополнительных процедур и промежуточных определений.

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

1) наличие неких дискретных состояний, число которых конечно, и одно из них принимается за начальное, а другое (или несколько других) за конечное (искомое);

2) определены правила перехода между состояниями;

3) для каждого состояния заданы определенные условия допустимости (оценки) этого состояния.

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

Рассмотрим задачу: имеются два сосуда – на 3 и на 5 литров. Как отмерить с их помощью 4 литра воды?

В этой задаче состояния связаны с определенным количеством воды V в первом сосуде и W во втором. Начальным состоянием является V=0, W=0, а конечным V=0, W=4. Переходы между состояниями можно записать в виде правил:

 

сосуды(VI, W1):- сосуды(V2, W2).

 

Например, правило:

сосуды(0, W):- сосуды(V, W).

 

означает, что вся вода из первого сосуда вылита. Обратим внимание на слово “вода” в условии задачи. Для предметной области, связанной с водой, характерно то, что воду можно просто выливать, и данное правило перехода между состояния­ми допустимо. Если бы задача решалась для молока, то его просто выливать было бы нельзя, и такое правило было бы недопустимым.

Правило:

 

сосуды(3, W):- сосуды(V, W).

 

означает, что первый сосуд заполнен полностью.

Не разливая, жидкость можно перелить из одного сосуда в другой только так, что один станет пустым, а другой наполнится. Это можно записать в виде правил:

 

сосуды(3,W):-сосуды(V,W–V+3).

сосуды(V,0):- сосуды(V–W,W).

сосуды(V,5):- сосуды(V–W+5,W).

сосуды(0,W):- сосуды (V, W–V).

 

При решении данной задачи необходимо также избежать повторения одних и тех же состояний – “переливания из пустого в порожнее”. Для этого в предикат “сосуды()” следует добавить 3-й аргумент – список пройденных состояний П. Элементы в него будут добавляться парами:

 

сосуды(V1,W1, [V1,W1 | П]):- не_принад(V1,W1,П), сосуды (V2, W2, П).

 

Условие, ограничивающее рекурсию, должно иметь вид:

 

сосуды(_,4,П):- write_list(П),!.