Лабораторная работа 7. Разработка БЗ и БД для Пролог - программ решения прикладных задач

Ход выполнения работы:

1) Выбрать свой вариант задания.

2) Ознакомиться с заданием и выполнить его.

При необходимости обратиться к Пояснениям к лабораторной работе, которые приведены после пункта «Варианты лабораторной работы №7».

Варианты лабораторной работы №7

Разработать МПЗ для Базы Знаний и написать Базу Данных, Базу Фактов и Базу Правил для программы (Пролог - программы), решающую соответственно:

1) задачу о волке, козе и капусте;

2) задачу о трех каннибалах и трех миссионерах;

3) задачу о четырех ферзях на поле размером 4´ 4 клетки;

4) задачу о ферзях на поле размером 8´ 8;

5) задачу о шахматных ладьях на поле размером 8´ 8;

6) задачу о шахматных конях на поле размером 8´ 8;

7) задачу о лжецах и правдолюбцах;

8) задачу - игру в «крестики и нулики»;

9) задачу о коммивояжере;

10) задачу о Ханойских башнях.

1) Задача о “волке, козе и капусте”.

Человеку нужно переправиться через реку и перевезти с собой волка, козу и капусту. Имеется лодка, которой управляет человек. На лодке одновременно можно перевезти не более 2-х пассажиров, включая человека (он же лодочник). Если на одном и том же берегу с волком с козой нет человека, то он ее съест. Аналогично, если коза останется на берегу с капустой, то она съест капусту. Все остальные ситуации безопасны. Требуется организовать переправу через реку так, чтобы все пассажиры были доставлены в сохранности на другой берег реки.

2) Задача о “трех каннибалах и трех миссионерах”.

На правом берегу реки находятся три каннибала и три миссионера, которым нужно переправиться на левый берег на двухместной лодке, не считая 3-е место для лодочника. Никого другого на берегах нет, место лодочника занимает только он сам. Если на любом берегу каннибалов окажется больше, чем миссионеров, то первые съедят вторых. Как следует организовать переправу, чтобы все пассажиры оказались на правом берегу целыми и невредимыми, если к тому же лодка при ее курсировании с одного берега на другой обязательно должна перевозить хоть одного пассажира из 6-ти указанных (таково правило переправы на этой реке).

3) Задача о “4 ферзях” на поле размером 4´ 4 клетки.

Расставить как можно больше шахматных ферзей на доске размером 4´ 4, чтобы они не «били» друг друга (конечно, каждый из ферзей находился в отдельной клетке: два ферзя не могут находиться в одной клетке, других фигур и пешек на доске нет). Задача о размещении 4-х ферзей на шахматной доске состоит в определении того, можно ли расставить ровно 4-я ферзей на шахматной доске (4´ 4 клеток) таким образом, чтобы ни один ферзь не нападал на другого по шахматным правилам, а если можно, то каким числом способов. Правила ходов ферзя: ферзь со своей клетки может перемещаться на любую клетку по горизонтали, вертикали и диагонали, если на его пути не встречается другой ферзь. Если такой ферзь встречается, то первый ферзь должен либо срубить его и встать на его место, но не обходить ее (правило запрета), либо быть срубленным этим ферзем.

4) Задача о «8 ферзях».

Расставить 8 шахматных ферзей на доске размером 8´ 8, чтобы они не «били» друг друга (конечно, каждый из ферзей находился в отдельной клетке: два ферзя не могут находиться в одной клетке, других фигур и пешек на доске нет). Задача о размещении ферзей на шахматной доске состоит в определении того, можно ли расставить ровно восемь ферзей на шахматной доске (8´ 8 клеток) таким образом, чтобы ни один ферзь не нападал на другого по шахматным правилам, а если можно, то каким числом способов Правила ходов ферзя: ферзь со своей клетки может перемещаться на любую клетку по горизонтали, вертикали и диагонали, если на его пути не встречается другой ферзь. Если такой другой ферзь встречается, то ферзь либо должен обязательно срубить его и встать на его место, но не обходить его (правило запрета), либо бить им срубленным.

5) Задача о «шахматных ладьях» на поле размером 8´ 8 клетки.

Расставить как можно больше шахматных ладей на доске размером 8´ 8, чтобы они не «били» друг друга (конечно, каждая из ладей находился в отдельной клетке: две ладьи не могут находиться в одной клетке, других фигур и пешек на доске нет). Задача о размещении ладей на шахматной доске состоит в определении максимального числа ладей, которые можно расставить на шахматной доске (8´ 8 клеток) таким образом, чтобы ни одна ладья не нападала на другую, а если можно, то каким числом способов Правила ходов ладьи: ладья со своей клетки может перемещаться на соответствующую клетку по известному шахматному правилу, если на ее пути не встречается другая ладья. Если такая другая ладья встречается, то ладья должна срубить ее и встать на ее место, но не обходить ее (правило запрета), либо быть ею срубленной.

6) Задача о «шахматных конях» на поле размером 8´ 8 клетки.

Расставить как можно больше шахматных коней на доске размером 8´ 8, чтобы они не «били» друг друга (конечно, каждый из коней находился в отдельной клетке: два коня не могут находиться в одной клетке, других фигур и пешек на доске нет). Задача о размещении коней на шахматной доске состоит в определении максимального количества коней, которых можно расставить на шахматной доске (8´ 8 клеток) таким образом, чтобы ни один конь не нападал на другого по шахматным правилам, а если можно, то каким числом способов. Правила ходов: конь со своей клетки может перемещаться на соответствующую клетку по шахматным правилам, если на этой клетке нет другого коня (правило запрета). В противном случае он должен срубить этого коня либо быть им срубленным.

7) Задача - логическая головоломка «Правдолюбцы и лжецы».

Население города состоит из правдолюбцев, всегда говорящих правду и только правду, и лжецов, всегда и только лгущих. В город приехал гость. Некоторые разговоры жителей этого города, которые он услышал, ему показались интересными.

Разговор 1. Житель А говорит жителю В: “либо я - лжец, либо ты правдолюбец”.

Разговор 2. Житель Д говорит жителям З и К: “либо я - лжец, либо З правдолюбец”.

Разговор 3. Один житель, подойдя к жителям Р, П и Т спросил их: “а сколько среди вас правдолюбцев? ”. Р ответил неопределенно, а П и говорит: “Р сказал, что среди нас есть один правдолюбец”. Но тут вмешался Т: “П лжет”.

Гость предлагает Вам выяснить, рассуждая логически, кто из жителей этого города - правдолюбец, а кто - лжец в каждом из 3-х случаев, исходя только из информации, приведенной в соответствующем разговоре.

8) Задача - игра в «крестики и нулики».

Исходным состоянием игры «Крестики-нолики» является пустая игровая доска размера 3´ 3, а конечным или целевым состоянием - доска на которой будет в одной строке, столбце или по диагонали располагается 3 крестика или нолика (в зависимости от того, чья победа предполагается). Путь из исходного состояния в конечное содержит последовательность ходов, ведущих к победе игрока, ставящего в клетке только х - крестик или только 0 - нолик.

9) Задача о коммивояжере.

Коммивояжер должен посетить каждый из пяти городов, не заходя более одного раза в каждый город. Между каждой парой городов имеется путь, длина которого (в километрах) указана на графе, см. рис. 1, а. Нужно, отправляясь из города, например, A, найти самый короткий путь, по которому коммивояжер по одному разу проходит через каждый город и в конце поездки возвращается в город А (рис. 3а).

Описание состояний, которым соответствуют вершины графа, осуществляется с помощью списка, элементами которого являются буквы. Последняя буква указывает город, которому соответствует данная вершина и в котором находится коммивояжер; предшествующая последовательность букв указывает путь, по которому коммивояжер попал в данный город. В пространстве состояний ищется решение. На рис. 3б это решение представлено последовательностью дуг (путем), ведущей из начальной вершины (А) в целевую вершину (ACDEBA), и составляет минимальный суммарный путь в 34 км.

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

10) Задача-головоломка «Ханойская башня» состоит в следующем. Имеется три стержня: а, b, с (рис. 4). В начале на стержне, а нанизано 64 диска уменьшающихся размеров (исходная башня). Все диски имеют разный диаметр, внизу находится самый большой диск, а наверху - самый маленький. Никакой диск большего диаметра не может находиться выше диска меньшего диаметра. В начале на стержнях b и с дисков нет. Задача: переложить все диски с а на b в том же порядке, в каком они были на а, пользуясь стержнем с как вспомогательным. При этом ни на одном из стержней никогда не должно возникать ситуации, при которой диск большего диаметра лежит на диске меньшего диаметра.

а Ь с

Рис. 4. Ханойская башня

1 2 345