У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ
Мы можем значительно упростить эту программу, если уверены, что ответ на вопрос всегда существует и если нам нужно только первое решение. В этом случае отпадает необходимость в проверке на зацикливание. Попробуйте самостоятельно выяснить, почему это так.
К сожалению, путь через наименьшее число городов не обязательно будет самым кратчайшим по километражу. До сих пор мы не принимали во внимание информацию о расстояниях, имеющуюся в нашем графе. Если же мы добавим к нашему графу несколько фиктивных городов, чтобы получить:
а(ньюкасл,карлайл,58).
а(карлайл,пенрит,23).
а(городБ,городаА,15).
а(пенрит, дарлингтон,52).
а(городБ,городВ,10).
а(уэркингтон, карлайл, 33).
а(уэркингтон,городВ,5).
а(уэркингтон,пенрит,39).
а(дарлингтон,городА,25).
то путь, кратчайший по километражу, фактически будет построен последним, поскольку он проходит через большое число городов. С каждым путем, который может быть продолжен, нам нужно связать и поддерживать в процессе работы программы указатель текущей длины этого пути. Тогда программа будет всегда продлевать путь с наименьшим километражем. Такая стратегия называется поиском по критерию первый-лучший. Будем теперь представлять путь в списке альтернативных путей в виде структуры г(М, П), где М – общая длина пути в километрах, а П – список мест, где мы уже побывали. Модифицированный предикат переходЗ находит кратчайший путь в списке альтернатив. Предикат кратчайший выделяет кратчайший путь в отдельный список, а остальные пути – в другой список. Предикат продлить находит все допустимые продолжения текущего кратчайшего пути и добавляет их к списку. Это в свою очередь требует новой версии предиката следузел, которая прибавляет расстояние до следующего города к уже вычисленному расстоянию. В целом программа выглядит так:
переходЗ (Пути,Цель,Путь):-кратчайший (Пути,Кратчайший,ОстПути), продлить(Кратчайший,Цель,ОстПути,Путь).
продлить(г(Расст,Путь),Цель,_,Путь):- Путь = [Цель|_].
продлить(г(Расст,[Послед| Бывали]),Цель,Пути,Путь):-найтивсе(г(D1,[Z,Послед|Бывали]),следузел(Послед,Бывали,Z,Расст,D1),Список), присоединить(Список,Пути,НовПути), переходЗ(НовПути,Цель,Пути).
кратчайший([Путь[Пути],Кратчайший,[ПутьЮст]):-кратчайший(Пути,Кратчайший,Ост), короче(Кратчайший,Путь),!.
кратчайший(Путь|Ост],Путь,Ост). короче(г(М1,_),г(М2, _):- M1 ‹ М2.
следузел(Х,Бывали,Y,Расст,НовРасст):-(a(X,Y,Z); a(Y,X,Z)),not(принадлежит(Y,Бывали)),НовРасст is Расст+Z.
Чтобы использовать эту программу, необходимо задать вопрос, содержащий предикат переход, определенный следующим образом:
переход (Старт,Цель,Путь):-переход3([г(0,[Старт])],Цель,R), обр(R,Путь).
Эта новая программа успешно строит возможные пути в по-рядке возрастания их фактической протяженности. Может быть, вам захочется изменить ее так, чтобы вместе с ответами она печатала длины различных путей.
Мы лишь затронули вопрос о возможных способах организации поиска по графу. Сведения о том, как осуществлять поиск по графу с использованием более эффективных критериев, чем «первый лучший», можно найти в литературе по искусственному интеллекту. Например: Nilsson N. Principles of Artificial Intelligence, Springer-Verlag, 1982[10] и Winstone P. Artificial Intelligence, (second edition), Addison-Wesley, 1984.[11]
7.10. Просеивай Двойки, Просеивай Тройки
Просеивай Двойки,
Просеивай Тройки,
Эратосфена Решето,
Пусть все кратные им отсеем,
Простые числа получим зато.
Простое число – это целое положительное число, которое делится нацело только на 1 и на само себя. Например, число 5 – простое, а число 15 – нет, поскольку оно делится на 3. Один из методов построения простых чисел называется «решетом Эратосфена». Этот метод, «отсеивающий» простые числа, не превышающие N, работает следующим образом:
1. Поместить все числа от 2 до N в решето.
2. Выбрать и удалить из решета наименьшее число.
3. Включить это число в список простых.
4. Просеять через решето (удалить) все числа, кратные этому числу.
5. Если решето не пусто, то повторить шаги 2-5.
Чтобы перевести эти правила на Пролог, мы определим предикат целые для получения списка целых чисел, предикат отсеять для проверки каждого элемента решета и предикат удалить для создания нового содержимого решета путем удаления из старого всех чисел, кратных выбранному числу. Это новое содержимое опять передается предикату отсеять. Предикат простые - это предикат самого верхнего уровня, такой что простые(N, L) конкретизирует L списком простых чисел, заключенных в диапазоне от 1 до N включительно.
простые(Предел,Рs):- целые(2,Предел,Is),отсеять(Is,Рs).
целые (Min,Max,[Min|Oct]):-Min=‹Max,!, М is Min+1,целые(М,Мах,Ост).
целые(_,_,[]).
отсеять([],[]).
отсеять([I|Is],[I|Ps]):-удалить(I,Is,Нов),отсеять(Нов,Рs).
удалить(Р,[],[]).
удалить (P,[I|Is],[I|Nis]):-not(0 is I mod Р),!,удалить(Р,Is,Nis).
удалить (P,[I|Is],Nis):-0 is I mod Р,!,удалить(Р,Is,Nis).
Продолжая эту арифметическую тему, рассмотрим Пролог-программу, реализующую рекурсивную формулировку алгоритма Евклида для нахождения наибольшего общего делителя (НОД) и наименьшего общего кратного (НОК) двух чисел. Целевое утверждение нод(I,J,K) доказуемо, если K является наибольшим общим делителем чисел I и J. Целевое утверждение нок(I,J,K) доказуемо, если K является наименьшим общим кратным чисел I и J:
нод(I,0,I).
нод(I,J,K):- R is I mod J, нод(J,R,K).
нок(I,J,K):- нод(I,J,R), K is (I*J)/R.
Заметим, что из-за особенностей способа вычисления остатка эти предикаты не являются «обратимыми». Это означает, что для того чтобы они работали, необходимо заблаговременно конкретизировать переменные I и J.
Упражнение 7.10. Если числа X, Y и Z таковы, что квадрат Z равен сумме квадратов X и Y (т. е. если Z²=X²+Y²), то про такие числа говорят, что они образуют Пифагорову тройку. Напишите программу, порождающую Пифагоровы тройки. Определите предикат pythag такой что, задав вопрос
?- pythag(X,Y,Z).
и запрашивая альтернативные решения, мы получим столько разных Пифагоровых троек, сколько пожелаем. Подсказка: используйте предикаты, подобные целое_число из гл. 4.
7.11. Символьное дифференцирование
Символьным дифференцированием в математике называется операция преобразования одного арифметического выражения в другое арифметическое выражение, которое называется производной. Пусть U обозначает арифметическое выражение, которое может содержать переменную х. Производная от U по х записывается в виде dU/dx и определяется рекурсивно с помощью некоторых правил преобразования, применяемых к U. Вначале следуют два граничных условия. Стрелка означает «преобразуется в»; U и V обозначают выражения, а с – константу:
dc/dx → 0
dx/dx → 1
d(-U)/dx → -(dU/dx)
d(U+V)/dx → dU/dx+dV/dx
d(U-V)/dx → dU/dx-dV/dx
d(cU)/dx → c(dU/dx)
d(UV)/dx → U(dV/dx) + V(dU/dx)
d(U/V)dx → d(UV-1)/dx
d(Uc)/dx → cUc-l(dU/dx)
d(lnU)/dx → U-1(dU/dx)
Этот набор правил легко написать на Прологе, поскольку мы можем представить арифметические выражения как структуры и использовать знаки операций как функторы этих структур. Кроме того, сопоставление целевого утверждения с заголовком правила мы можем использовать как сопоставление образцов. Рассмотрим цель d(E,X, F), которая считается согласованной, когда производная выражения E по константе[12] X есть выражение F. Помимо знаков операций +, -, *, /, которые имеют встроенные определения, нам нужно определить операцию ^, такую, что X^Y означаете xy, а также одноместную операцию ~, такую что ~Х означает «минус X». Эти определения операций введены исключительно для того, чтобы облегчить распознавание синтаксиса выражений. Например, после того как d определен, можно было бы задать следующие вопросы:
?- d(x+1,x,X).
