- Логическое программирование

Презентация "Логическое программирование" по информатике – проект, доклад

Слайд 1
Слайд 2
Слайд 3
Слайд 4
Слайд 5
Слайд 6
Слайд 7
Слайд 8
Слайд 9
Слайд 10
Слайд 11
Слайд 12
Слайд 13
Слайд 14
Слайд 15
Слайд 16
Слайд 17
Слайд 18
Слайд 19
Слайд 20
Слайд 21
Слайд 22
Слайд 23
Слайд 24
Слайд 25
Слайд 26
Слайд 27
Слайд 28
Слайд 29
Слайд 30
Слайд 31
Слайд 32
Слайд 33
Слайд 34
Слайд 35

Презентацию на тему "Логическое программирование" можно скачать абсолютно бесплатно на нашем сайте. Предмет проекта: Информатика. Красочные слайды и иллюстрации помогут вам заинтересовать своих одноклассников или аудиторию. Для просмотра содержимого воспользуйтесь плеером, или если вы хотите скачать доклад - нажмите на соответствующий текст под плеером. Презентация содержит 35 слайд(ов).

Слайды презентации

Логическое программирование. Презентация 10 Решение логических задач
Слайд 1

Логическое программирование

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

Содержание. Определение и алгоритм решения головоломок Поиск в пространстве решений (в глубину/ширину) Примеры решения логических задач Общие выводы
Слайд 2

Содержание

Определение и алгоритм решения головоломок Поиск в пространстве решений (в глубину/ширину) Примеры решения логических задач Общие выводы

Логические задачи (головоломки). Логическая головоломка состоит из нескольких фактов относительно небольшого числа объектов, которые имеют различные атрибуты. Минимальное число фактов относительно объектов и атрибутов связано с желанием выдать единственный вариант назначения атрибутов объектам. Зача
Слайд 3

Логические задачи (головоломки)

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

Пример головоломки. Условие: Беседуют трое друзей: Белов, Рыжов, Чернов. Брюнет сказал Белову: «Посмотри, один из нас блондин, другой – рыжий, третий – брюнет, но ни у кого цвет волос не соответствует его фамилии». Вопрос: какой цвет волос у каждого собеседника?
Слайд 4

Пример головоломки

Условие: Беседуют трое друзей: Белов, Рыжов, Чернов. Брюнет сказал Белову: «Посмотри, один из нас блондин, другой – рыжий, третий – брюнет, но ни у кого цвет волос не соответствует его фамилии». Вопрос: какой цвет волос у каждого собеседника?

Решение головоломки. surname('Белов'). surname('Чернов'). surname('Рыжов'). color('рыжий'). color('светлый'). color('черный'). hair(X, Y) :- surname(X), color(Y), X='Белов', not(Y='черный'), not(Y='светлый'). hair(X, Y) :- surname(X), color(Y), X='Чернов', not(Y='черный'), not(hair('Белов', Y)). hai
Слайд 5

Решение головоломки

surname('Белов'). surname('Чернов'). surname('Рыжов'). color('рыжий'). color('светлый'). color('черный'). hair(X, Y) :- surname(X), color(Y), X='Белов', not(Y='черный'), not(Y='светлый'). hair(X, Y) :- surname(X), color(Y), X='Чернов', not(Y='черный'), not(hair('Белов', Y)). hair(X, Y) :- surname(X), color(Y), X='Рыжов', not(hair('Белов', Y)), not(hair('Чернов', Y)).

Поиск решения головоломки. % Конкретизируем переменные X и Y допустимыми значениями % эти значения и будут искомыми решениями задачи ?- hair(X, Y). X = 'Белов' Y = рыжий ; X = 'Чернов' Y = светлый ; X = 'Рыжов' Y = черный ; No
Слайд 6

Поиск решения головоломки

% Конкретизируем переменные X и Y допустимыми значениями % эти значения и будут искомыми решениями задачи ?- hair(X, Y). X = 'Белов' Y = рыжий ; X = 'Чернов' Y = светлый ; X = 'Рыжов' Y = черный ; No

Более сложный пример: поиск соответствий. В автомобильных гонках три первых места заняли Алеша, Петя и Коля. Какое место занял каждый из них, если Петя занял не второе и не третье место, а Коля - не третье? Сперва запишем факты (очевидные данные): /* База данных имен */ имя(алеша). имя(петя). имя(ко
Слайд 7

Более сложный пример: поиск соответствий

В автомобильных гонках три первых места заняли Алеша, Петя и Коля. Какое место занял каждый из них, если Петя занял не второе и не третье место, а Коля - не третье? Сперва запишем факты (очевидные данные): /* База данных имен */ имя(алеша). имя(петя). имя(коля). /* База данных призовых мест */ место(первое). место(второе). место(третье).

Запишем правила и предикат поиска решения /* Устанавливаем взаимно-однозначное соответствие между базами данных, X - элемент из базы данных имен, Y - элемент из базы данных занятых мест */ /* Петя занял не второе и не третье место */ соответствие(X, Y) :- имя(X), X=петя, место(Y), not(Y=второе), not
Слайд 8

Запишем правила и предикат поиска решения /* Устанавливаем взаимно-однозначное соответствие между базами данных, X - элемент из базы данных имен, Y - элемент из базы данных занятых мест */ /* Петя занял не второе и не третье место */ соответствие(X, Y) :- имя(X), X=петя, место(Y), not(Y=второе), not(Y=третье). /* Коля занял не третье место */ соответствие(X, Y) :- имя(X), X=коля, место(Y), not(Y=третье). соответствие(X, Y) :- имя(X), X=алеша, место(Y). /* У всех ребят разные места */ решение(X1,Y1,X2,Y2,X3,Y3) :- X1=петя, соответствие(X1,Y1), X2=коля, соответствие(X2,Y2), X3=алеша, соответствие(X3,Y3), Y1\=Y2, Y2\=Y3, Y1\=Y3.

Запускаем решатель…. ?- решение(X1,Y1,X2,Y2,X3,Y3). X1 = петя Y1 = первое X2 = коля Y2 = второе X3 = алеша Y3 = третье
Слайд 9

Запускаем решатель…

?- решение(X1,Y1,X2,Y2,X3,Y3). X1 = петя Y1 = первое X2 = коля Y2 = второе X3 = алеша Y3 = третье

Логические задачи. Пространство состояний - это граф, вершины которого соответствуют ситуациям, встречающимся в задаче ("проблемные ситуации"), а решение задачи сводится к поиску пути в этом графе. Примеры задач, где используется поиск в пространстве состояний: Ханойские башни Задача о вол
Слайд 10

Логические задачи

Пространство состояний - это граф, вершины которого соответствуют ситуациям, встречающимся в задаче ("проблемные ситуации"), а решение задачи сводится к поиску пути в этом графе. Примеры задач, где используется поиск в пространстве состояний: Ханойские башни Задача о волке, козе и капусте Игра в 15 Задача коммивояжера Другие логические задачи (эвристика, олимпиадные задачи, проблемы ИИ,…) Рассмотрим на примерах, как формулируются задачи в терминах пространства состояний, а также обсудим общие методы решения сооотв. задач. Процесс решения задачи включает в себя поиск в графе, при этом, как правило, возникает проблема, как обрабатывать альтернативные пути поиска. Мы рассмотрим две основные стратегии перебора альтернатив: поиск в глубину и поиск в ширину.

Пример: задача с кубиками. Задача состоит в выработке плана переупорядочивания кубиков, поставленных друг на друга, как показано на рисунке. На каждом шагу разрешается переставлять только один кубик. Кубик можно взять только тогда, когда его верхняя поверхность свободна. Кубик можно поставить либо н
Слайд 11

Пример: задача с кубиками

Задача состоит в выработке плана переупорядочивания кубиков, поставленных друг на друга, как показано на рисунке. На каждом шагу разрешается переставлять только один кубик. Кубик можно взять только тогда, когда его верхняя поверхность свободна. Кубик можно поставить либо на стол, либо на другой кубик. Для того, чтобы построить требуемый план, мы должны отыскать последовательность ходов, реализующую заданную трансформацию. Эту задачу можно представлять себе как задачу выбора среди множества возможных альтернатив. В исходной ситуации альтернатива всего одна: поставить кубик С на стол. После того как кубик С поставлен на стол, мы имеем три альтернативы: поставить А на стол или поставить А на С, или поставить С на А.

Граф состояний. Как показывает рассмотренный пример, с задачами такого рода связано два типа понятий: Проблемные ситуации. Разрешенные ходы или действия, преобразующие одни проблемные ситуации в другие. Проблемные ситуации вместе с возможными ходами образуют направленный граф, называемый пространств
Слайд 12

Граф состояний

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

Примечание: Каждому разрешенному ходу или действию можно приписать его стоимость. Например, в нашей задаче стоимости, приписанные перемещениям кубиков, будут указывать нам на то, что некоторые кубики перемещать труднее, чем другие. В тех случаях, когда каждый ход имеет стоимость, мы заинтересованы в отыскании решения минимальной стоимости. Стоимость решения - это сумма стоимостей дуг, из которых состоит "решающий путь" - путь из стартовой вершины в целевую. Либо может потребоваться найти кратчайший путь по кол-ву состояний…

Решение задачи о кубиках. % удаление элемента Х из списка, результат - в L del(X, [X | L], L). del(X, [Y | L], [Y | L1]):- del(X, L, L1). % переход между состояниями: s(X, Y) % где X - предыдущий, Y - последующий допустимый шаг/состояние % перенести верхний кубик Top1 на столбик Stack2 s( Stacks, [S
Слайд 13

Решение задачи о кубиках

% удаление элемента Х из списка, результат - в L del(X, [X | L], L). del(X, [Y | L], [Y | L1]):- del(X, L, L1). % переход между состояниями: s(X, Y) % где X - предыдущий, Y - последующий допустимый шаг/состояние % перенести верхний кубик Top1 на столбик Stack2 s( Stacks, [Stackl, [Top1 | Stack2] | OtherStacks] ) :- del([Top1 | Stackl], Stacks, Stacksl), % Найти первый столбик del(Stack2, Stacksl, OtherStacks). % Найти второй столбик goal(Situation):- member([a,b,c], Situation). % Целевое состояние Алгоритмы поиска реализуются в программе в виде отношения: solve(Start, Solution) где Start — начальный узел в пространстве состояний, a Solution — путь от узла Start до любого целевого узла. % Вызов поиска: ?- solve([[c,a,b], [], []], Solution). % Определение см. далее

Стратегия поиска в глубину. Для того, чтобы найти решающий путь Sol из заданной вершины N в некоторую целевую вершину, необходимо: если N - это целевая вершина, то положить Sol = [N], или если для исходной вершины N существует вершина-преемник N1, такая, что можно провести путь Sol1 из N1 в целевую
Слайд 14

Стратегия поиска в глубину

Для того, чтобы найти решающий путь Sol из заданной вершины N в некоторую целевую вершину, необходимо: если N - это целевая вершина, то положить Sol = [N], или если для исходной вершины N существует вершина-преемник N1, такая, что можно провести путь Sol1 из N1 в целевую вершину, то положить Sol = [N | Sol1]. % целевая вершина solve(N, [N]):- goal(N). % составной путь solve(N, [N | Sol1]):- s(N, N1), solve(N1, Sol1).

Рис. 11. 4. Пример простого пространства состояний: а - стартовая вершина, f и j - целевые вершины. Порядок, в которой происходит проход по вершинам пространства состояний при поиске в глубину: а, b, d, h, e, i, j. Найдено решение [a, b, e, j]. После возврата: [а, с, f].

Оптимизация поиска: избавляемся от циклов. Мы говорим "в глубину", имея в виду тот порядок, в котором рассматриваются альтернативы в пространстве состояний. Всегда, когда алгоритму поиска в глубину надлежит выбрать из нескольких вершин ту, в которую следует перейти для продолжения поиска,
Слайд 15

Оптимизация поиска: избавляемся от циклов

Мы говорим "в глубину", имея в виду тот порядок, в котором рассматриваются альтернативы в пространстве состояний. Всегда, когда алгоритму поиска в глубину надлежит выбрать из нескольких вершин ту, в которую следует перейти для продолжения поиска, он предпочитает самую "глубокую" из них. Самая глубокая вершина - это вершина, расположенная дальше других от стартовой вершины Поиск в глубину наиболее адекватен рекурсивному стилю программирования, принятому в Прологе. Причина этого состоит в том, что, обрабатывая цели, пролог-система сама просматривает альтернативы именно в глубину. Очевидное усовершенствование – добавление механизма обнаружения циклов: Ни одну из вершин, уже содержащихся в пути, построенном из стартовой вершины в текущую вершину, не следует вторично рассматривать в качестве возможной альтернативы продолжения поиска. Правило можно сформулировать в виде: depthfirst( Path, Node, Solution)

Начинаясь в а, поиск заканчивается бесконечным циклом между d и h: a, b, d, h, d, h, d ...

Реализация поиска в глубину без зацикливаний. % solve( Node, Solution): % Решение Solution представляет собой ациклический путь (узлы в % котором указаны в обратном порядке) между узлом Node и целью solve( Node, Solution):- depthfirst( [], Node, Solution). % depthfirst( Path, Node, Solution): % реше
Слайд 16

Реализация поиска в глубину без зацикливаний

% solve( Node, Solution): % Решение Solution представляет собой ациклический путь (узлы в % котором указаны в обратном порядке) между узлом Node и целью solve( Node, Solution):- depthfirst( [], Node, Solution). % depthfirst( Path, Node, Solution): % решение Solution формируется в результате продления пути % [Node | Path] до целевого узла depthfirst( Path, Node, [Node | Path] ) :- goal( Node). depthfirst( Path, Node, Sol) :- s( Node, Node1), not member( Node1, Path), % Предотвращение цикла depthfirst( [Node | Path], Node1, Sol).

Поиск в ширину. В противоположность поиску в глубину стратегия поиска в ширину предусматривает переход в первую очередь к вершинам, ближайший к стартовой вершине. В результате процесс поиска имеет тенденцию развиваться более в ширину, чем в глубину (см. рис). Поиск в ширину программируется не так ле
Слайд 17

Поиск в ширину

В противоположность поиску в глубину стратегия поиска в ширину предусматривает переход в первую очередь к вершинам, ближайший к стартовой вершине. В результате процесс поиска имеет тенденцию развиваться более в ширину, чем в глубину (см. рис). Поиск в ширину программируется не так легко, как поиск в глубину. Причина состоят в том, что нам приходится сохранять все множество альтернативных вершин-кандидатов, а не только одну вершину, как при поиске в глубину. Более того, если мы желаем получить при помощи процесса поиска решающий путь, то одного множества вершин недостаточно. Поэтому мы будем хранить не множество вершин-кандидатов, а множество путей-кандидатов. Таким образом, цель breadthfirst( Paths, Solution) истинна только тогда, когда существует путь из множества кандидатов Пути, который может быть продолжен вплоть до целевой вершины. Этот продолженный путь и есть Solution.

Граф поиска в ширину. Простое пространство состояний: а - стартовая вершина, f и j - целевые вершины. Применение стратегии поиска в ширину дает следующий порядок прохода по вершинам: а, b, c, d, e, f. Более короткое решение: [a, c, f] найдено раньше, чем более длинное: [а, b, e, j]
Слайд 18

Граф поиска в ширину

Простое пространство состояний: а - стартовая вершина, f и j - целевые вершины. Применение стратегии поиска в ширину дает следующий порядок прохода по вершинам: а, b, c, d, e, f. Более короткое решение: [a, c, f] найдено раньше, чем более длинное: [а, b, e, j]

Реализация поиска в ширину. Чтобы выполнить поиск в ширину при заданном множестве путей нужно: если голова первого пути - это целевая вершина, то взять этот путь в качестве решения иначе удалить первый путь из множества кандидатов и породить множество всех возможных продолжений этого пути на один ша
Слайд 19

Реализация поиска в ширину

Чтобы выполнить поиск в ширину при заданном множестве путей нужно: если голова первого пути - это целевая вершина, то взять этот путь в качестве решения иначе удалить первый путь из множества кандидатов и породить множество всех возможных продолжений этого пути на один шаг; множество продолжений добавить в конец множества кандидатов, а затем выполнить поиск в ширину с полученным новым множеством. % solve( Start, Solution): % Решение Solution – путь из вершины Start к цели solve( Start, Solution) :- breadthfirst( [ [Start] | Z] - Z, Solution). breadthfirst( [ [Node | Path] | _] - _, [Node | Path] ) :- goal( Node). breadthfirst( [Path | Paths] - Z, Solution) :- extend( Path, NewPaths), conc( NewPaths, Z1, Z), % Добавить NewPaths в конец Paths \== Z1, % Множество возможных путей – не пустое breadthfirst( Paths - Z1, Solution).

Задача о ханойской башне. Автор: математик Люка,1883 год. "Где-то в непроходимых джунглях, недалеко от города Ханоя, есть монастырь бога Брамы. В начале времен, когда Брама создавал Мир, он воздвиг в этом монастыре три высоких алмазных стержня и на один из них возложил 64 диска, сделанных из чи
Слайд 20

Задача о ханойской башне

Автор: математик Люка,1883 год. "Где-то в непроходимых джунглях, недалеко от города Ханоя, есть монастырь бога Брамы. В начале времен, когда Брама создавал Мир, он воздвиг в этом монастыре три высоких алмазных стержня и на один из них возложил 64 диска, сделанных из чистого золота. Он приказал монахам перенести эту башню на другой стержень (в соответствии с правилами, разумеется). С этого времени монахи работают день и ночь. Когда они закончат свой труд, наступит конец света." В нашем примере будем использовать всего 4 диска и 3 стержня. Правила перемещения дисков: разрешается снимать со стержня только верхний диск, запрещается класть больший диск на меньший, при каждом ходе передвигается только один диск. В решении будем использовать рекурсивный поиск всевозможных вариантов.

Решение задачи о Ханойских башнях. % move(число_дисков, откуда, куда, через) move(1,X,Y,_) :- write('Перемещаем диск с '), write(X), write(' стержня на '), write(Y), nl. move(N,X,Y,Z) :- N>1, M is N-1, move(M,X,Z,Y), move(1,X,Y,_), move(M,Z,Y,X). % Предикат для запуска поиска решений задачи разме
Слайд 21

Решение задачи о Ханойских башнях

% move(число_дисков, откуда, куда, через) move(1,X,Y,_) :- write('Перемещаем диск с '), write(X), write(' стержня на '), write(Y), nl. move(N,X,Y,Z) :- N>1, M is N-1, move(M,X,Z,Y), move(1,X,Y,_), move(M,Z,Y,X). % Предикат для запуска поиска решений задачи размерности X hanoi(X):- move(X, 'лев.', 'прав.', 'центр.').

Находим решение ханойской задачи…. ?- hanoi(4). Перемещаем диск с лев. стержня на центр. Перемещаем диск с лев. стержня на прав. Перемещаем диск с центр. стержня на прав. Перемещаем диск с лев. стержня на центр. Перемещаем диск с прав. стержня на лев. Перемещаем диск с прав. стержня на центр. Переме
Слайд 22

Находим решение ханойской задачи…

?- hanoi(4). Перемещаем диск с лев. стержня на центр. Перемещаем диск с лев. стержня на прав. Перемещаем диск с центр. стержня на прав. Перемещаем диск с лев. стержня на центр. Перемещаем диск с прав. стержня на лев. Перемещаем диск с прав. стержня на центр. Перемещаем диск с лев. стержня на центр. Перемещаем диск с лев. стержня на прав. Перемещаем диск с центр. стержня на прав. Перемещаем диск с центр. стержня на лев. Перемещаем диск с прав. стержня на лев. Перемещаем диск с центр. стержня на прав. Перемещаем диск с лев. стержня на центр. Перемещаем диск с лев. стержня на прав. Перемещаем диск с центр. стержня на прав. Yes

Более сложная задача: Фермер (вол-коза-капуста). Условия: Действующие лица: фермер ( Farmer ), волк ( Wolf ), козел ( Goat ) капуста ( Cabbidge ) находятся на одном (правом) берегу У берега находится лодка, в которую могут поместиться только двое. Нельзя оставлять на одном берегу козу и капусту, коз
Слайд 23

Более сложная задача: Фермер (вол-коза-капуста)

Условия: Действующие лица: фермер ( Farmer ), волк ( Wolf ), козел ( Goat ) капуста ( Cabbidge ) находятся на одном (правом) берегу У берега находится лодка, в которую могут поместиться только двое. Нельзя оставлять на одном берегу козу и капусту, козу и волка. Задание: Надо перебраться на другой (левый) берег на лодке.

Решение задачи: описание условий. % противоположные берега opposite('ПРАВ.', 'ЛЕВ.'). opposite('ЛЕВ.', 'ПРАВ.'). % возможные перемещения move(state(X,X,G,C), state(Y,Y,G,C)):- opposite(X,Y). /* фермер с волком */ move(state(X,W,X,C), state(Y,W,Y,C)):- opposite(X,Y). /* фермер с козой */ move(state(X
Слайд 24

Решение задачи: описание условий

% противоположные берега opposite('ПРАВ.', 'ЛЕВ.'). opposite('ЛЕВ.', 'ПРАВ.'). % возможные перемещения move(state(X,X,G,C), state(Y,Y,G,C)):- opposite(X,Y). /* фермер с волком */ move(state(X,W,X,C), state(Y,W,Y,C)):- opposite(X,Y). /* фермер с козой */ move(state(X,W,G,X), state(Y,W,G,Y)):- opposite(X,Y). /* фермер с капустой */ move(state(X,W,G,C), state(Y,W,G,C)):- opposite(X,Y). /* фермер один */ % недопустимые состояния unsafe( state(F,X,X,_) ):- opposite(F,X). % волк съест козу unsafe( state(F,_,X,X) ):- opposite(F,X). % коза съест капусту

Поиск путей решения. path(S,G,L,L1):- move(S,S1), not( unsafe(S1) ), not( member(S1,L) ), path( S1,G,[S1|L],L1),!. path(G,G,T,T):- !. % найдено финальное состояние % Для вызова решения можно использовать: go:- go(state('ПРАВ.','ПРАВ.','ПРАВ.','ПРАВ.'), state('ЛЕВ.','ЛЕВ.','ЛЕВ.','ЛЕВ.')). go(S,G):-
Слайд 25

Поиск путей решения

path(S,G,L,L1):- move(S,S1), not( unsafe(S1) ), not( member(S1,L) ), path( S1,G,[S1|L],L1),!. path(G,G,T,T):- !. % найдено финальное состояние % Для вызова решения можно использовать: go:- go(state('ПРАВ.','ПРАВ.','ПРАВ.','ПРАВ.'), state('ЛЕВ.','ЛЕВ.','ЛЕВ.','ЛЕВ.')). go(S,G):- path(S,G,[S],L), nl,write('Порядок перемещений (решение):'), nl, write_path(L), fail. go(_,_).

Для организации удобной формы вывода…. member(X,[X|_]). member(X,[_|L]):- member(X,L). write_move( state(X,W,G,C), state(Y,W,G,C) ) :-!, write('Фермер переплывает реку с '), write(X), write(' реки на '), write(Y), nl. write_move( state(X,X,G,C), state(Y,Y,G,C) ) :-!, write('Фермер перевозит волка с
Слайд 26

Для организации удобной формы вывода…

member(X,[X|_]). member(X,[_|L]):- member(X,L). write_move( state(X,W,G,C), state(Y,W,G,C) ) :-!, write('Фермер переплывает реку с '), write(X), write(' реки на '), write(Y), nl. write_move( state(X,X,G,C), state(Y,Y,G,C) ) :-!, write('Фермер перевозит волка с '), write(X), write(' берега реки на '), write(Y), nl. write_move( state(X,W,X,C), state(Y,W,Y,C) ) :-!, write('Фермер перевозит козу с ' ), write(X), write(' берега реки на '), write(Y), nl. write_move( state(X,W,G,X), state(Y,W,G,Y) ) :-!, write('Фермер перевозит капусту с '), write(X), write(' берега реки на '), write(Y), nl. write_path( [H1,H2|T] ) :- !, write_move(H1,H2),write_path([H2|T]). write_path( _ ).

Получаем готовое решение. ?- go. Порядок перемещений (решение): Фермер перевозит козу с ЛЕВ. берега реки на ПРАВ. Фермер переплывает реку с ПРАВ. реки на ЛЕВ. Фермер перевозит капусту с ЛЕВ. берега реки на ПРАВ. Фермер перевозит козу с ПРАВ. берега реки на ЛЕВ. Фермер перевозит волка с ЛЕВ. берега р
Слайд 27

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

?- go. Порядок перемещений (решение): Фермер перевозит козу с ЛЕВ. берега реки на ПРАВ. Фермер переплывает реку с ПРАВ. реки на ЛЕВ. Фермер перевозит капусту с ЛЕВ. берега реки на ПРАВ. Фермер перевозит козу с ПРАВ. берега реки на ЛЕВ. Фермер перевозит волка с ЛЕВ. берега реки на ПРАВ. Фермер переплывает реку с ПРАВ. реки на ЛЕВ. Фермер перевозит козу с ЛЕВ. берега реки на ПРАВ. Yes

Еще одна головоломка…. Побег от Зурга Персонажи фильма «История игрушек»: Базз, Вуди, Рекс и Хэмм - убегают от Зурга. Им осталось только перейти через последний мост, и они будут свободны. Однако, мост очень ветхий и сможет одновременно выдержать только двоих из них. Также, что бы перейти мост и не
Слайд 28

Еще одна головоломка…

Побег от Зурга Персонажи фильма «История игрушек»: Базз, Вуди, Рекс и Хэмм - убегают от Зурга. Им осталось только перейти через последний мост, и они будут свободны. Однако, мост очень ветхий и сможет одновременно выдержать только двоих из них. Также, что бы перейти мост и не попасть в ловушки и ямы в нём, нужен фонарик. Проблема в том, что у наших четырёх друзей всего один фонарик и заряда батареи в нём осталось всего лишь на 60 (шестьдесят) минут. Игрушки могут перейти мост в одну сторону за различное время: Игрушка Время Базз 5 минут Вуди 10 минут Рекс 20 минут Хэмм 25 минут Так как одновременно на мосту могут находиться только две игрушки, они не могут перейти мост сразу все вместе. Так как им нужен фонарик для перехода через мост, кому-то из двоих, перешедших через мост, нужно будет вернуться к оставшимся игрушкам, что бы отдать им фонарик. Вопрос: в каком порядке эти четыре игрушки должны пересечь мост за время не более 60 минут, что бы спастись от Зурга?

Решение задачи «Побег от Зурга». % факты: время прохождения моста каждым героем time(buzz, 5). time(woody,10). time(rex, 20). time(hamm, 25). % список действующих персонажей toys([buzz,hamm,rex,woody]). cost([],0) :- !.% цена перехода моста равно 0, если все перешли cost([X|L],C) :- % иначе равна вр
Слайд 29

Решение задачи «Побег от Зурга»

% факты: время прохождения моста каждым героем time(buzz, 5). time(woody,10). time(rex, 20). time(hamm, 25). % список действующих персонажей toys([buzz,hamm,rex,woody]). cost([],0) :- !.% цена перехода моста равно 0, если все перешли cost([X|L],C) :- % иначе равна времени самого медлительного time(X,S), cost(L,D), C is max(S,D). % вспомогательный предикат: вычисляется каждая допустимая группа % игрушек, двигающаяся направо (выдает списки длины 2) split(L,[X,Y],M) :- member(X,L), % если X есть в L member(Y,L), % и Y есть в L compare(

Продолжение решения: определяем допустимые переходы. /* Идея – в представлении промежуточных состояний переходов через мост фактами вида st(P,L), где L - список игрушек, находящихся в данный момент на левой стороне моста, а P - признак, показывающий положение фонарика (левая или правая сторона) */ m
Слайд 30

Продолжение решения: определяем допустимые переходы

/* Идея – в представлении промежуточных состояний переходов через мост фактами вида st(P,L), где L - список игрушек, находящихся в данный момент на левой стороне моста, а P - признак, показывающий положение фонарика (левая или правая сторона) */ move(st(l,L1),st(r,L2),r(M),D) :- split(L1,M,L2), cost(M,D). move(st(r,L1),st(l,L2),l(X),D) :- toys(T), subtract(T,L1,R), member(X,R), merge_set([X],L1,L2), time(X,D). % trans/4 в основном генерирует все возможные переходы через мост вместе с требуемым временем trans(st(r,[]),st(r,[]),[],0). trans(S,U,L,D) :- move(S,T,M,X), trans(T,U,N,Y), append([M],N,L), D is X + Y.

Поиск решений. % cross/2 формулирует поисковую задачу, % задавая начальную и конечную конфигурации пространства поиска. cross(M,D) :- toys(T), trans(st(l,T),st(r,[]),M,D0), D0=
Слайд 31

Поиск решений

% cross/2 формулирует поисковую задачу, % задавая начальную и конечную конфигурации пространства поиска. cross(M,D) :- toys(T), trans(st(l,T),st(r,[]),M,D0), D0=

Задача о ферзях. Задача о расстановке на шахматной доске ферзей таким образом, чтобы ни один из ферзей не находился под боем другого. Для того, чтобы задача была решена, требуется расставить ферзей таким образом, чтобы все ферзи занимали разные горизонтали, разные вертикали и разные диагонали. Резул
Слайд 32

Задача о ферзях

Задача о расстановке на шахматной доске ферзей таким образом, чтобы ни один из ферзей не находился под боем другого. Для того, чтобы задача была решена, требуется расставить ферзей таким образом, чтобы все ферзи занимали разные горизонтали, разные вертикали и разные диагонали. Результат можно представить в виде списка, где каждый элемент списка - это координаты одного из ферзей. Заранее можно ограничить перебор, расставив ферзей по разным горизонталям. Решить поставленную задачу можно следующим образом: 1. если список ферзей пуст, то это одно из решений задачи; 2. если список ферзей не пуст, то он будет являться решением в случае, если ферзи в хвосте списка не будут бить друг друга, то есть хвост списка сам будет решением, и ферзь, находящийся в голове списка, не будет бить ни одного ферзя из хвоста списка.

Решение задачи о ферзях. solution ([ ]). solution ([queen (X,Y)|Rest]):- solution (Rest), belongs (Y, [1,2,3,4,5,6,7,8]), notbeat (queen (X,Y),Rest). notbeat (_,[ ]):- !. notbeat (queen (X,Y), [queen (X1,Y1)|Rest]):- YY1, TmpY1=Y1-Y, TmpX1=X1-X, TmpY1TmpX1, TmpX=X-X1, TmpY1TmpX, notbeat (queen (X,Y)
Слайд 33

Решение задачи о ферзях

solution ([ ]). solution ([queen (X,Y)|Rest]):- solution (Rest), belongs (Y, [1,2,3,4,5,6,7,8]), notbeat (queen (X,Y),Rest). notbeat (_,[ ]):- !. notbeat (queen (X,Y), [queen (X1,Y1)|Rest]):- YY1, TmpY1=Y1-Y, TmpX1=X1-X, TmpY1TmpX1, TmpX=X-X1, TmpY1TmpX, notbeat (queen (X,Y),Rest). belongs (X, [X|L]). belongs (X, [Y|L]):- belongs (X,L). templ ([queen (1,Y1),queen (2,Y2),queen (3,Y3),queen (4,Y4),queen (5,Y5),queen (6,Y6),queen (7,Y7),queen (8,Y8)]). start:- templ (S), write(S), solution(S), write(S), nl, fail.

Полученные решения. [queen (1,4), queen (2,2), queen (3,7), queen (4,3), queen (5,6), queen (6,8), queen (7,5), queen (8,1)] [queen (1,5), queen (2,2), queen (3,4), queen (4,7), queen (5,3), queen (6,8), queen (7,6), queen (8,1)] [queen (1,3), queen (2,5), queen (3,2), queen (4,8), queen (5,6), quee
Слайд 34

Полученные решения

[queen (1,4), queen (2,2), queen (3,7), queen (4,3), queen (5,6), queen (6,8), queen (7,5), queen (8,1)] [queen (1,5), queen (2,2), queen (3,4), queen (4,7), queen (5,3), queen (6,8), queen (7,6), queen (8,1)] [queen (1,3), queen (2,5), queen (3,2), queen (4,8), queen (5,6), queen (6,4), queen (7,7), queen (8,1)] [queen (1,3), queen (2,6), queen (3,4), queen (4,2), queen (5,8), queen (6,5), queen (7,7), queen (8,1)] [queen (1,5), queen (2,7), queen (3,1), queen (4,3), queen (5,8), queen (6,6), queen (7,4), queen (8,2)] [queen (1,4), queen (2,6), queen (3,8), queen (4,3), queen (5,1), queen (6,7), queen (7,5), queen (8,2)] [queen (1,3), queen (2,6), queen (3,8), queen (4,1), queen (5,4), queen (6,7), queen (7,5), queen (8,2)] [queen (1,5), queen (2,3), queen (3,8), queen (4,4), queen (5,7), queen (6,1), queen (7,6), queen (8,2)] [queen (1,5), queen (2,7), queen (3,4), queen (4,1), queen (5,3), queen (6,8), queen (7,6), queen (8,2)] …

Выводы. Пространство состояний - это направленный граф, вершины которого соответствуют проблемным ситуациям, а дуги - возможным ходам. Конкретная задача определяется стартовой вершиной и целевым условием. Решению задачи соответствует путь в графе. Таким образом, решение задачи сводится к поиску пути
Слайд 35

Выводы

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

Список похожих презентаций

Фрагментированное программирование

Фрагментированное программирование

Цель работы. Распараллеливание исполнительной системы (ИС) фрагментированного программирования и её оптимизация. Постановка задачи. Разработка многопоточной ...
Что такое программирование

Что такое программирование

Назначение программирования- разработка программ управления компьютером с целью решения различных информационных задач. Специалисты, профессионально ...
Параллельное программирование WinAPI и OpenMP 7

Параллельное программирование WinAPI и OpenMP 7

Литература. 1. И. Одинцов Профессиональное программирование. Системный подход. – «БХВ-Петербург» - 2004. – 610 с. 2. Джин Бэкон, Тим Харрис Операционные ...
Тест Алгоритмизация и программирование

Тест Алгоритмизация и программирование

В этой презентации приводятся тренировочные задания из нескольких источников: открытого сегмента федерального банка тестовых заданий, демонстрационных ...
Объектно-ориентированное программирование

Объектно-ориентированное программирование

Содержание:. Графы: определения и примеры Ориентированные графы Путь в орграфе Матрица смежности Иерархический список Алгоритм Дейкстры Программа ...
Объектно-ориентированное программирование

Объектно-ориентированное программирование

основано на принципах логического вывода из базы знаний – фактов и правил. Логическое программирование. основано на принципе последовательной детализации ...
Введение в программирование

Введение в программирование

«Моя кошка замечательно разбирается в программировании. Стоит мне объяснить проблему ей - и все становится ясно.». «Кодируй так, как будто человек, ...
Нелинейное программирование

Нелинейное программирование

Отличия от ЗЛП: 1. ОДЗ не обязательно выпуклая. 2. Экстремум не обязан находится на границе ОДЗ. - задача классической оптимизации. Пример:. . Метод ...
Введение в объектно-ориентированное программирование

Введение в объектно-ориентированное программирование

X, Y – координаты центра круга;. Draw R – радиус круга; Color – цвет круга. 1 способ. Draw1: R=10; x=5; y=10; color=3; Draw2: R=45; x=15; y=3; color=2;. ...
Введение в параллельное программирование

Введение в параллельное программирование

Содержание лекции. Формальный подход к определению параллельной программы Меры качества параллельных программ Предел ускорения вычислений при распараллеливании ...
Аспектно-ориентированное программирование

Аспектно-ориентированное программирование

Сквозная функциональность. Ведение журналов Авторизация. Модуль оформления заказов. Модуль принятия товаров. Проблемы сквозной функциональности. Запутанность ...
Алгоритмы и программирование

Алгоритмы и программирование

АЛГОРИТМ Линейный Циклический С ветвлением С процедурой. Программа – запись алгоритма на языке программирования для компьютера. Алфавит языка. Алфавит ...
Алгоритмизация и программирование в Pascal

Алгоритмизация и программирование в Pascal

Вводная часть. Процесс решения задачи на ПК – это совместная деятельность человека и машины. Его условно можно разделить на несколько этапов. Человеку ...
Алгоритмизация и программирование

Алгоритмизация и программирование

Исполнители алгоритмов. КАЛЬКУЛЯТОР 1. У исполнителя Калькулятор две команды, которым присвоены номера: вычти 1; умножь на 3. Первая из них уменьшает ...
Введение в программирование

Введение в программирование

Основные понятия. Программирование – это раздел информатики, занимающийся вопросами разработки программ управления компьютером. Язык программирования ...
Методика изучения темы "Алгоритмизация и программирование"

Методика изучения темы "Алгоритмизация и программирование"

Основные понятия, которые с которыми учащиеся знакомятся в курсе изучаемого раздела это - алгоритм, исполнитель алгоритма, система команд исполнителя, ...
Введение в программирование

Введение в программирование

Тема 1: Введение в программирование. Какой язык понимает процессор? Процессор понимает язык электрических сигналов. Он не различает сильный или слабый ...
Объектно – ориентированное программирование на DELPHI - 11

Объектно – ориентированное программирование на DELPHI - 11

Объектно – ориентированное программирование на DELPHI - 11. @ Краснополянская школа № 1 Домнин Константин Михайлович 2006 год. На этом уроке: Мы создадим ...
Введение в программирование Turbo Pascal

Введение в программирование Turbo Pascal

Тема 1: Введение в программирование. Какой язык понимает процессор? Процессор понимает язык электрических сигналов. Он не различает сильный или слабый ...
Объектно-ориентированное программирование

Объектно-ориентированное программирование

Литература. Васильев А.Н. Java. Объектно-ориентированное программирование. – СПб.: Питер, 2011. Монахов В. В. Язык программирования Java и среда Netbeans. ...

Конспекты

Линейное программирование на языке TurboPascal

Линейное программирование на языке TurboPascal

Интегрированный урок информатика и экология 7 классе. Тема урока : Линейное программирование на языке TurboPascal. Цель:.  . Сформировать навыки ...
Структурное, модульное, объектно-ориентированное программирование, облачные технологии

Структурное, модульное, объектно-ориентированное программирование, облачные технологии

УРОК 5. Класс:. 10. Дата проведения:. . Тема урока:. . Структурное, модульное, объектно-ориентированное программирование, облачные технологии. ...
WEB- программирование

WEB- программирование

Коммунальное Государственное Учреждение. «Первомайский комплекс «Общеобразовательная средняя школа – детский сад имени Д.М. Карбышева» отдела образования ...

Советы как сделать хороший доклад презентации или проекта

  1. Постарайтесь вовлечь аудиторию в рассказ, настройте взаимодействие с аудиторией с помощью наводящих вопросов, игровой части, не бойтесь пошутить и искренне улыбнуться (где это уместно).
  2. Старайтесь объяснять слайд своими словами, добавлять дополнительные интересные факты, не нужно просто читать информацию со слайдов, ее аудитория может прочитать и сама.
  3. Не нужно перегружать слайды Вашего проекта текстовыми блоками, больше иллюстраций и минимум текста позволят лучше донести информацию и привлечь внимание. На слайде должна быть только ключевая информация, остальное лучше рассказать слушателям устно.
  4. Текст должен быть хорошо читаемым, иначе аудитория не сможет увидеть подаваемую информацию, будет сильно отвлекаться от рассказа, пытаясь хоть что-то разобрать, или вовсе утратит весь интерес. Для этого нужно правильно подобрать шрифт, учитывая, где и как будет происходить трансляция презентации, а также правильно подобрать сочетание фона и текста.
  5. Важно провести репетицию Вашего доклада, продумать, как Вы поздороваетесь с аудиторией, что скажете первым, как закончите презентацию. Все приходит с опытом.
  6. Правильно подберите наряд, т.к. одежда докладчика также играет большую роль в восприятии его выступления.
  7. Старайтесь говорить уверенно, плавно и связно.
  8. Старайтесь получить удовольствие от выступления, тогда Вы сможете быть более непринужденным и будете меньше волноваться.

Информация о презентации

Ваша оценка: Оцените презентацию по шкале от 1 до 5 баллов
Дата добавления:1 ноября 2018
Категория:Информатика
Содержит:35 слайд(ов)
Поделись с друзьями:
Скачать презентацию
Смотреть советы по подготовке презентации