Решение логических задач в Турбо Прологе

Размещено на http://www.allbest.ru/

ЛАБОРАТОРНАЯ РАБОТА

“Решение логических задач в Турбо Прологе”

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

Теория. Рассмотрим следующую логическую задачу (рисунок). На рисунке кружками обозначены города (1..7). Стрелки, связывающие города, показывают пути, по которым можно из одного города попасть в другой. Задача формулируется так: можно ли, выйдя из города 1, обойти все города, побывав в каждом ровно один раз. Это - знаменитая задача о коммивояжере.

Для решения этой и подобных ей задач можно использовать логический подход. Во многих случаях такой подход достаточно эффективен с практической точки зрения.

Для реализации логического подхода следует ввести переменные, определив которые, мы получим решение задачи. Запомните, что переменные должны (в подавляющем большинстве случаев) обозначать то, что требуется найти по условиям задачи. Нам нужно найти путь, т.е. набор стрелок, по которым пойдет коммивояжер. Поэтому введем переменные, обозначающие стрелки: . Первый индекс в записи переменной указывает, из какого города выходит стрелка, а второй индекс указывает, в какой город стрелка заходит. Все эти переменные логические (булевские), т.е. принимают значения 0 или 1.

Имея в распоряжении переменные, можно составить уравнения (формулы), демонстрирующие условия задач. Эти условия говорят, что коммивояжер посещает (заходит в) каждый город ровно один раз. Следовательно, один раз он из него и выходит. Итак, для каждого города нужно составить два уравнения: одно для условия, что сумма входящих стрелок равна 1, а второе - что сумма выходящих стрелок равна 1. Эти уравнения таковы:

Теперь нам надо просто "переложить" эту систему уравнений в язык Пролог.

Программа на языке Пролог состоит из секций: domains, predicates, clauses, goal. В секции domains объявляют пользовательские типы данных. В секции predicates объявляют предикаты (имена предикатов и типы аргументов), в секции clauses объявляют предложения (формулы), связывающие одни предикаты с другими. В секции goal объявляют цель (предикат, который требуется доказать).

В настоящей работе секция domains не представлена, поскольку используем только стандартные (известные Прологу) типы данных. Наша задача - написать решатель логических задач.

Начинаем всегда с секции goal . В нашем случае она имеет такой вид:

goal

clearwindow,

find(X31,X61,X13,X12,X17,X72,X24,X26,X73,X34,X74,X45,X46,X65,X56,X57),

write(X31,X61,X13,X12,X17,X72,X24,X26,X73,X34,X74,X45,X46,X65,X56,X57),

readchar(_).

Таким образом, задача свелась к определению предиката find(…).

Определим этот предикат следующим образом:

find(X31,X61,X13,X12,X17,X72,X24,X26,X73,X34,X74,X45,X46,X65,X56,X57):-

znach(X31),

znach(X61),

znach(X13),

znach(X12),

znach(X17),

znach(X72),

znach(X24),

znach(X26),

znach(X73),

znach(X34),

znach(X45),

znach(X46),

znach(X65),

znach(X56),

znach(X57),

znach(X26),

znach(X61),

znach(X74),

X31+X61=1,

X12+X13+X17=1,

X12+X72=1,

X24+X26=1,

X13+X73=1,

X31+X34=1,

X24+X34+X74=1,

X45+X46=1,

X45+X65=1,

X56+X57=1,

X26+X46+X56=1,

X61+X65=1,

X17+X57=1,

X72+X73+X74=1.

Мы видим, что сначала идет предикат znach(…). Этот предикат указывает Прологу, какие значения могут принимать переменные. Его определение имеет такой вид:

znach(X):-

X=0; X=1.

В языке Пролог через точку запятой записывают альтернативные определения для предикатов. Можно было также использовать и такую запись:

znach(X):-

X=0.

znach(X):-

X=1.

Обе эти записи эквивалентны. Мы просто устанавливаем, что переменная может принимать значение либо 0, либо 1.

Далее по тексту определения предиката find(…) идут уравнения, использующие объявленные переменные.

Все введенные предикаты должны быть объявлены в секции predicates и определены в секции clauses. С учетом сказанного программа имеет следующий итоговый вид:

predicates

nondeterm find(integer,integer,integer,integer,integer,integer,integer,integer,integer,integer,integer,integer,

integer,integer,integer,integer)

nondeterm znach(integer)

clauses

find(X31,X61,X13,X12,X17,X72,X24,X26,X73,X34,X74,X45,X46,X65,X56,X57):-

znach(X31),

znach(X61),

znach(X13),

znach(X12),

znach(X17),

znach(X72),

znach(X24),

znach(X26),

znach(X73),

znach(X34),

znach(X45),

znach(X46),

znach(X65),

znach(X56),

znach(X57),

znach(X26),

znach(X61),

znach(X74),

X31+X61=1,

X12+X13+X17=1,

X12+X72=1,

X24+X26=1,

X13+X73=1,

X31+X34=1,

X24+X34+X74=1,

X45+X46=1,

X45+X65=1,

X56+X57=1,

X26+X56=1,

X61+X65=1,

X17+X57=1,

X72+X73+X74=1.

znach(X):-

X=0; X=1.

goal

find(X31,X61,X13,X12,X17,X72,X24,X26,X73,X34,X74,X45,X46,X65,X56,X57),

write(X31,X61,X13,X12,X17,X72,X24,X26,X73,X34,X74,X45,X46,X65,X56,X57),

readchar(_).

логическая задача пролог

Выполним эту программу в системе Visual Prolog 5.2. Запустим пролог и в меню Project выберем пункт New Project

Введем имя проекта, затем щелкнем мышью в поле Name of .VPR File и установим рабочий каталог. После этого перейдем по кнопке Target в окно

и установим платформу DOS. Нажмем кнопку CREATE:

Для того чтобы открыть окно редактора кода дважды щелкните на имени файла (выделено синим фоном на последнем скриншоте). Откроется окно редактора кода, куда Вы и поместите приведенный выше листинг:

Запустите программу на выполнение, нажав F9. Вы получите следующий результат:

Результирующие значения переменных перечислены в двоичной последовательности. Эта последовательность определяет следующий искомый путь:

X12, X26,X61, X34,X45,X57,X73.

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

X12+X26+X61<3.

Получим новое решение

Это решение дает окончательный итоговый ответ c одним единственным циклом:

X13, X34,X45,X57,X72,X26,X61.

ЗАДАНИЕ.

1. Составить логическую систему уравнений и решить задачу о назначении. Имеются работники Р1, Р2, Р3,Р4,Р5,Р6,Р7 и работы А1, А2.А3.А4,А5.А6,А7. Каждый работник должен получить одну работу и каждая работа должна быть назначена одному работнику. При этом работник может получить только ту работу, которую он может сделать. Матрица назначения имеет такой вид:

Усложним задачу таким образом: учесть дополнительное условие: если работник Р1 получает работу А1, то Р3 не может получить А2.

2. Задача о раскраске графа. Имеется граф (рисунок).

Нужно покрасить вершины в три цвета (красный, белый, зеленый) так, чтобы каждая вершина была закрашена в один цвет и никакие две свзязанные вершины не были покрашены одинаково.

3. Изделие состоит из трех узлов: А, B, C. Узел А может быть реализован в одном из трех вариантов: A1, A2, A3. Узел B может быть реализован в одном из двух вариантов: B1, B2. Узел С может быть реализован в одном из двух вариантов: С1. С2.

Несовместимыми являются варианты: 1) A1 и B1, 2) B1 и C2, 3) A3 и С1, 4) A2 и С2. Указать возможную реализацию изделия с учетом совместимости вариантов.

Укажите еще две другие возможные реализации изделия.

4. Задача о паросочетаниях. Имеются четыре мужчины M1, M2, M3, M4 и четыре женщины: Ж1, Ж2, Ж3, Ж4. Известно, что М1 недолюбливает Ж2 и Ж3. М2 недолюбливает Ж1. Ж1 недолюбливает М2 и М4. Наконец, Ж3 недолюбливает М1 и М2. Нужно разбить этих лиц по парам так, чтобы ни в одной паре не было кого-то, кто недолюбливал бы другого. Введите переменные и составьте уравнения.

5. Решить на Прологе систему логических уравнений:

Размещено на Allbest.ru