Информатика -продвинутый курс




РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ НА ПРОЛОГЕ - часть 2


write_list([]).

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

Задание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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




Содержание  Назад  Вперед