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



         

РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ НА ПРОЛОГЕ


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

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

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

Рис. 3.17. Задача «конверт»

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

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

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

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

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

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

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

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




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