Содержание
- 2. Содержание Определение и алгоритм решения головоломок Поиск в пространстве решений (в глубину/ширину) Примеры решения логических задач
- 3. Логические задачи (головоломки) Логическая головоломка состоит из нескольких фактов относительно небольшого числа объектов, которые имеют различные
- 4. Пример головоломки Условие: Беседуют трое друзей: Белов, Рыжов, Чернов. Брюнет сказал Белову: «Посмотри, один из нас
- 5. Решение головоломки surname('Белов'). surname('Чернов'). surname('Рыжов'). color('рыжий'). color('светлый'). color('черный'). hair(X, Y) :- surname(X), color(Y), X='Белов', not(Y='черный'), not(Y='светлый').
- 6. Поиск решения головоломки % Конкретизируем переменные X и Y допустимыми значениями % эти значения и будут
- 7. Более сложный пример: поиск соответствий В автомобильных гонках три первых места заняли Алеша, Петя и Коля.
- 8. Решение головоломки Запишем правила и предикат поиска решения /* Устанавливаем взаимно-однозначное соответствие между базами данных, X
- 9. Запускаем решатель… ?- решение(X1,Y1,X2,Y2,X3,Y3). X1 = петя Y1 = первое X2 = коля Y2 = второе
- 10. Логические задачи Пространство состояний - это граф, вершины которого соответствуют ситуациям, встречающимся в задаче ("проблемные ситуации"),
- 11. Пример: задача с кубиками Задача состоит в выработке плана переупорядочивания кубиков, поставленных друг на друга, как
- 12. Граф состояний Как показывает рассмотренный пример, с задачами такого рода связано два типа понятий: Проблемные ситуации.
- 13. Решение задачи о кубиках % удаление элемента Х из списка, результат - в L del(X, [X
- 14. Стратегия поиска в глубину Для того, чтобы найти решающий путь Sol из заданной вершины N в
- 15. Оптимизация поиска: избавляемся от циклов Мы говорим "в глубину", имея в виду тот порядок, в котором
- 16. Реализация поиска в глубину без зацикливаний % solve( Node, Solution): % Решение Solution представляет собой ациклический
- 17. Поиск в ширину В противоположность поиску в глубину стратегия поиска в ширину предусматривает переход в первую
- 18. Граф поиска в ширину Простое пространство состояний: а - стартовая вершина, f и j - целевые
- 19. Реализация поиска в ширину Чтобы выполнить поиск в ширину при заданном множестве путей нужно: если голова
- 20. Задача о ханойской башне Автор: математик Люка,1883 год. "Где-то в непроходимых джунглях, недалеко от города Ханоя,
- 21. Решение задачи о Ханойских башнях % move(число_дисков, откуда, куда, через) move(1,X,Y,_) :- write('Перемещаем диск с '),
- 22. Находим решение ханойской задачи… ?- hanoi(4). Перемещаем диск с лев. стержня на центр. Перемещаем диск с
- 23. Более сложная задача: Фермер (вол-коза-капуста) Условия: Действующие лица: фермер ( Farmer ), волк ( Wolf ),
- 24. Решение задачи: описание условий % противоположные берега opposite('ПРАВ.', 'ЛЕВ.'). opposite('ЛЕВ.', 'ПРАВ.'). % возможные перемещения move(state(X,X,G,C), state(Y,Y,G,C)):-
- 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):- !. %
- 26. Для организации удобной формы вывода… member(X,[X|_]). member(X,[_|L]):- member(X,L). write_move( state(X,W,G,C), state(Y,W,G,C) ) :-!, write('Фермер переплывает реку
- 27. Получаем готовое решение ?- go. Порядок перемещений (решение): Фермер перевозит козу с ЛЕВ. берега реки на
- 28. Еще одна головоломка… Побег от Зурга Персонажи фильма «История игрушек»: Базз, Вуди, Рекс и Хэмм -
- 29. Решение задачи «Побег от Зурга» % факты: время прохождения моста каждым героем time(buzz, 5). time(woody,10). time(rex,
- 30. Продолжение решения: определяем допустимые переходы /* Идея – в представлении промежуточных состояний переходов через мост фактами
- 31. Поиск решений % cross/2 формулирует поисковую задачу, % задавая начальную и конечную конфигурации пространства поиска. cross(M,D)
- 32. Задача о ферзях Задача о расстановке на шахматной доске ферзей таким образом, чтобы ни один из
- 33. Решение задачи о ферзях solution ([ ]). solution ([queen (X,Y)|Rest]):- solution (Rest), belongs (Y, [1,2,3,4,5,6,7,8]), notbeat
- 34. Полученные решения [queen (1,4), queen (2,2), queen (3,7), queen (4,3), queen (5,6), queen (6,8), queen (7,5),
- 36. Скачать презентацию