Проще всего описать граф в базе данных с помощью фактов, представляющих дуги между узлами графа. На рис, 7.3 приведен пример графа и его представления с помощью фактов. Чтобы пройти от узла gк узлу а, мы можем пойти по пути g, d, e, аили по одному из многих других возможных путей. Если мы представляем ориентированный граф, то предикат а следует понимать так, что а(Х, Y)означает, что существует дуга из Xв Y, но из этого не следует существование дуги из Yв X. В данном разделе мы будем иметь дело только с неориентированными графами, у которых все дуги двунаправленные. Это допущение совпадает с тем, которое мы делаем в разд. 7.2 при поиске в лабиринте.
Простейшая программа поиска по графу, представленному так, как указано выше, выглядит следующим образом:
переход(Х,X).
переход(Х,Y):- (a(X,Z);a(Z,X)), переход(Z,Y).
К сожалению, эта программа может зацикливаться. Поэтому, как и раньше, мы используем список Т для хранения перечня тех узлов, в которых мы уже побывали в какой-либо рекурсии предиката.
переход(Х,Х,Т).
переход(Х,Y,T):- (a(X,Z);a(Z,X)), not (принадлежит(Z, Т)),переход(Z, Y,[Z|T]).
Эта программа, разработанная в разд. 7.2, осуществляет так называемый поиск «вглубь», поскольку вначале рассматривается только один из соседей узла по графу, Другие же соседи игнорируются до тех пор, пока неудачные попытки согласовать цели в рекурсивных вызовах не возвратят Пролог к рассмотрению данного узла.
Теперь давайте рассмотрим такой поиск по графу, который мог бы быть полезен на практике. Как быть, если мы должны спланировать маршрут поездки из одного города Северной Англии в другой? Для этого потребуется база данных с информацией о дорогах между городами в Северной Англии и их протяженности:
а(ньюкасл,карлайл,58).
а(карлайл,пенрит,23).
а(дарлингтон,ньюкасл,40).
а(пенрит, дарлингтон,52).
а(уэркингтон,карлайл,33).
а(уэркингтон,пенрит,39).
На некоторое время мы можем забыть о расстояниях и определить новый предикат:
a(X,Y):- a(X,Y,Z).
С помощью этого определения предиката а уже имеющаяся программа поиска по графу ( переход) будет находить пути, по которым можно переезжать из одного места на графе в любое другое. Однако программа переходимеет недостаток: когда она успешно завершается, мы не знаем, какой путь она нашла. По меньшей мере мы вправе ожидать от программы переход выдачинам в нужном порядке списка мест, которые придется посетить. Тем более, что в программе имеется перечень этих мест, правда, в порядке, обратном тому, какой нам нужен. Чтобы получить правильный список, мы можем воспользоваться программой обр, определенной в разд. 7.5. Тогда мы получим новое определение программы переход, которая возвращает найденный маршрут через свой третий аргумент:
переход(Старт,Цель,Путь):- переход0(Старт,Цель,[],R),обр(R, Путь).
переход0(Х,Х,Т,[Х|Т]).
переход0(Место,Y,Т,R):-следузел(Место,Т,Сосед),переход0(Сосед,Y,[Место|T],R).
следузел(Х,Бывали,Y):- (a(X,Y); a(Y,X)),not (принадлежит(Y,Бывали)).
Заметим, что предикат следузелпозволяет получать для узла X«правильный» узел Y, т. е. такой, к которому можно непосредственно перейти от узла X. Ниже приводится пример работы этой программы при поиске маршрута из Дарлингтона в Уэркингтон:
?- переход(дарлингтон,уэркингтон,Х)
Х=[дарлингтон,ньюкасл,карлайл,пенрит,уэркингтон]
Это не самый лучший маршрут, однако, программа найдет другие маршруты если мы инициируем процесс возврата.
У этой программы много недостатков. Она совершенно не управляет выбором следующего участка пути, поскольку у нее нет доступа к полному набору возможных вариантов, а те выборы, которые у программы имеются, не представлены явно в виде структуры, которая может анализироваться программой, а неявно предопределены схемой работы механизма возврата.
Ниже приведен переработанный вариант программы, который отличается большей универсальностью. В дальнейшем мы увидим, как с помощью простых изменений в этой программе можно получить разнообразные методы поиска.
переход(Старт,Цель,Путь):- переход1([[Старт]],Цель,R),обр(R, Путь).
переход1([Первый|Ост],Цель,Первый):- Первый =[Цель|_].
переход1([[Послед|Бывали]|Прочие],Цель,Путь):-найтивсе([Z, Послед|Бывали], следузел(Послед, Бывали,Z), Список), присоединить(Список, Прочие, НовПути), переход1(НовПути,Цель,Путь).
Предикат следузелостается прежним. Предикату переход1передается список рассматриваемых путей вместе с конечным пунктом, и в последнем аргументе он возвращает удачный путь. Список рассматриваемых путей – это просто все дороги, начинающиеся в начальной точке, которые мы уже рассмотрели. Мы надеемся, что одна из них при продлении даст путь, который приведет нас в конечный пункт. Все пути представлены в виде обратных списков населенных пунктов, так что они могут также выполнять функции перечня мест, где мы уже бывали.
В самом начале имеется только один возможный путь, который можно пытаться продлить. Это просто путь, который начинается в исходном пункте и никуда не ведет. Если мы стартуем из Дарлингтона, то это будет [дарлингтон].Если теперь исследовать пути ведущие из Дарлингтона в соседние города, то можно обнаружить, что имеются два возможных пути [ньюкасл, дарлингтон]и [пенрит, дарлингтон].Поскольку Уэркингтон не встречается ни на одном из этих путей, необходимо решить, какой из этих путей следует продолжить. Если принято решение продлить первый путь, то мы обнаружим, что существует всего один доступный узел – последний город на этом пути. Итак, кроме пути Дарлингтон – Пенрит у нас есть новый путь: [карлайл, ньюкасл, дарлингтон].
Наш «изыскатель», переход1ведет полный список путей, по которым, может быть, стоит двигаться. Как же он решает какой из путей следует рассмотреть первым? Он просто выбирает первый попавшийся.Затем он ищет все возможные способы продления этого пути до следующего населенного пункта (используя найтивседля построения списка всех таких продленных путей) и помещает получившиеся пути в началосписка для рассмотрения их на следующем уровне рекурсии.
В результате, переход1ведет себя таким образом, что он попробует все возможные способы продления первого пути прежде чем будет рассматривать альтернативные пути. Такая стратегия поиска является одним из вариантов поиска вглубь.Между прочим, переход1рассматривает пути совершенно в том же порядке, что и переход0.Быть может вам будет интересно выяснить, почему это так.
Если нас интересует кратчайший путь от Дарлингтона до Уэркингтона, то имеющаяся программа для этого не подходит. Первое найденное ею решение – это не кратчайший путь, а наоборот, самый длинный (в данном случае). Нам нужно изменить программу таким образом, чтобы она строила пути в порядке возрастания их длины. Если мы изменим ее так, чтобы она всегда продлевала более короткие пути, прежде чем рассматривать более длинные, то она будет вынуждена находить вначале кратчайшие пути (если измерять длину пути числом городов на нем). Полученная программа будет осуществлять поиск вширь.Единственное, что нужно сделать для этого – это вставлять новые альтернативы в конец всего списка возможностей, а не в начало, как в последнем примере. Мы просто исправим второе утверждение в определении переход1, чтобы он выглядел следующим образом:
переход1([[Послед|Бывали]|Прочие],Цель,Путь):-найтивсе([Z,Послед|Бывали], следузел(Послед, Бывали,Z),Список), присоединить(Прочие,Список,НовПути), переход1(НовПути,Цель, Путь).
Теперь исправленная программа находит возможные пути из Дарлингтона в Уэркингтон в следующем порядке:
[дарлингтон,пенрит,уэркингтон]
[дарлингтон,ньюкасл, карлайл,уэркингтон]
[дарлингтон,пенрит,карлайл,уэркингтон]
[дарлингтон,ньюкасл,карлайл,пенрит,уэркингтон]
Мы можем значительно упростить эту программу, если уверены, что ответ на вопрос всегда существует и если нам нужно только первое решение. В этом случае отпадает необходимость в проверке на зацикливание. Попробуйте самостоятельно выяснить, почему это так.
К сожалению, путь через наименьшее число городов не обязательно будет самым кратчайшим по километражу. До сих пор мы не принимали во внимание информацию о расстояниях, имеющуюся в нашем графе. Если же мы добавим к нашему графу несколько фиктивных городов, чтобы получить:
а(ньюкасл,карлайл,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(U c)/dx’ cU c - l(dU/dx)
d(lnU)/dx’ U -1(dU/dx)
Этот набор правил легко написать на Прологе, поскольку мы можем представить арифметические выражения как структуры и использовать знаки операций как функторы этих структур. Кроме того, сопоставление целевого утверждения с заголовком правила мы можем использовать как сопоставление образцов. Рассмотрим цель d(E,X, F), которая считается согласованной, когда производная выражения Eпо константе [12] Xесть выражение F. Помимо знаков операций +, -, *, /, которые имеют встроенные определения, нам нужно определить операцию ^, такую, что X^Yозначаете x y, а также одноместную операцию ~, такую что ~Хозначает «минус X». Эти определения операций введены исключительно для того, чтобы облегчить распознавание синтаксиса выражений. Например, после того как dопределен, можно было бы задать следующие вопросы:
?- d(x+1,x,X).
X = 1+0
?- d(x*x-2,x,X).
X = х*1+1*х-0
Заметим, что само по себе простое преобразование одного выражения в другое (на основе правил) не всегда дает результат в приведенной (упрощенной) форме. Приведение результата должно быть записано в виде отдельной процедуры (см. разд. 7.12). Программа дифференцирования состоит из определений дополнительных операций и построчной трансляции приведенных выше правил преобразования в утверждения Пролога:
?- op(10,yfx,^).
?- op(9,fx,~).
d(X,X,1):-!.
d(C,X,0):- atomic(C).
d(~U,X,~A):- d(U,X,A).
d(U+V,X,A+B):- d(U,X,A), d(V,X,B).
d(U-V,X,A-В):- d(U,X,A), d(V,X,B).
d(C*U,X,C*A):- atomic(C), C\=X, d(U,X,A),!.
d(U*V,X,B*U+A*V):- d(U,X,A), d(V,X,B).
d(U/V,X,A):- d(U*V^~1),X,A).
d(U^C,X,C*U^(C-1)*W):- atomic(C),C\=X,d(U,X,W).
d(log(U),X,A*U^(~1)):- d(U,X,A).
Обратите внимание на два места, в которых задан предикат отсечения. В первом случае отсечение обеспечивает тот факт, что производная от переменной по ней самой распознается только первым утверждением, исключая возможность применения второго утверждения. Во втором случае предусмотрено два утверждения для умножения. Первое – для специального случая. Если имеет место специальный случай, то утверждение для общего случая должно быть устранено из рассмотрения.
Как уже говорилось, данная программа выдает решения в неприведенной форме (т. е. без упрощений). Например, всякое вхождение х*1может быть приведено к х, а всякое вхождение вида х*1+1*х-0может быть приведено к 2*х. В следующем разделе рассматривается программа алгебраических преобразований, которую можно использовать для упрощения арифметических выражений. Примененный способ очень похож на тот, каким выше выводились производные.
7.12. Отображение структур и преобразование деревьев
Если некоторая структура покомпонентно копируется с целью образования новой структуры, то мы говорим, что одна структура отображаетсяв другую. Обычно при копировании каждая компонента слегка изменяется подобно тому, как в гл. 3 мы изменяли одно предложение, превращая его в другое. В том примере нам иногда нужно было скопировать какое-то слово в точности в том виде, в каком оно встретилось в исходном предложении, а иногда при копировании нам нужно было изменить слово. Для этого мы использовали следующую программу, которая отображаетпервый аргумент предиката преобразоватьво второй его аргумент:
преобразовать([],[]).
преобразовать([А|В],[С|D]):- заменить(А,С),преобразовать(В,D).
Поскольку отображение имеет довольно широкое применение, мы можем определить предикат отобспистакой, что целевое утверждение отобспис(Р, L, M)согласуется с базой данных, применяя предикат Рк каждому элементу списка Lи образуя в результате новый список М. При этом предполагается, что предикат Римеет два аргумента: первый аргумент для передачи «входного» элемента, а второй аргумент – для измененного элемента, подлежащего включению в список М.
отобспис((_,[],[]).
отобспис((P,[X|L],[Y|M]):- Q =..[P,X,Y],call(Q),отобспис(Р,L,М).
Об этом определении следует сказать несколько слов. Во-первых, определение содержит граничное условие (первое утверждение) и общий рекурсивный случай (второе утверждение). Во втором утверждении используется оператор '=..', формирующий целевое утверждение на основе предиката (Р), входного элемента (X)и переменной (Y), которую предикат Рдолжен конкретизировать, чтобы образовать измененный элемент. Затем делается попытка согласовать цель Q, в результате чего Yконкретизируется, образуя голову третьего аргумента данного вызова предиката отобспис. Наконец, рекурсивный вызов отображает хвост первого аргумента в хвост второго.
Функции предиката преобразоватьможет выполнять предикат отобспис. Полагая, что предикат заменитьопределен как в гл. 3, такое использование отобсписмогло бы выглядеть следующим образом:
?- отобспис(заменить,[уоu,аrе,а,computer],Z).
Z = [i, [am, not], a, computer]
Путем упрощения предиката отобсписполучается предикат обрабспис, который просто обрабатывает список, применяя некоторый предикат от одного аргумента к каждому элементу списка. При этом новый список не порождается.
обрабспис(_,[]).
обрабспис(Р,[Х|L]):-Q =…[Р,Х],call(Q),обрабспис(Р,L).
Заметим, что предикат печать_строкииз гл. 5 можно было бы заменить запросом вида обрабспис(put, L), где L– это строка, которую нужно напечатать.
Отображение применимо не только к спискам; оно может быть определено для структуры любого вида. Например, рассмотрим арифметическое выражение, составленное из функторов * и +, имеющих по два аргумента. Пусть мы хотим отобразить одно выражение в другое, устраняя при этом все умножения на 1. Это алгебраическое приведение могло быть определено с помощью предиката sтакого, что s(Op, L, R,Ans)означает, что выражение, состоящее из операции Орс левым аргументом Lи правым аргументом Rприводится к упрощенному выражению Ans. Факты, необходимые для устранения умножений на 1, могли бы выглядеть так (из-за коммутативности умножения нужны два факта):
s(*,X,1,X).
s(*,1,X,X).
Эта таблицы упрощений позволяет нам любое выражение вида 1*Х отобразить в X. Посмотрим, как можно воспользоваться этим в программе.
При приведении выражения Ес помощью такой таблицы упрощений, мы вначале должны привести левый аргумент Е, затем привести правый аргумент Еи, наконец, посмотреть, подходит ли этот приведенный результат под случаи, предусмотренные в нашей таблице. Если это так, то мы порождаем новое выражение в соответствии с указаниями таблицы. В качестве «листьев» дерева, представляющего выражение, фигурируют целые числа или атомы, поэтому для приведения листьев к ним самим в граничном условии мы должны использовать встроенный предикат atomic.Как и выше, мы можем использовать ' =..', чтобы разложить выражение Ена функтор и компоненты;
привести(Е,Е):- atomic(E), 1.
привести(Е,F):-Е =.. [Op,L,R],привести(L,Х),привести(R, Y),s(Op,X,Y,F).
Итак, предикат привестиотображает выражение Ев выражение F, используя для этого факты, имеющиеся в таблице упрощений s. А что делать, если невозможны никакие упрощения? Чтобы избежать в этом случае неудачного завершения s(Op,X, Y, F),мы должны поместить в конец каждого раздела таблицы упрощений, относящегося к определенному оператору, правило-ловушку. Приведенная ниже таблица упрощений содержит правила для сложения и умножения. Кроме того, в ней выделены правила-ловушки для каждого вида операций.
s(+,X,0,X).
s(+,0,X,X).
s(+,X,Y,X + Y) /* ловушка для + */
s(*,_,0,0).
s(*,0,_,0).
s(*,1,X,X).
s(*,X,1,X).
s(*,X,Y,X*Y). /* ловушка для * */
При наличии правил-ловушек возникает вопрос о выборе способа упрощения некоторых выражений. Например, если нам дано выражение 3+0, мы можем либо использовать первый факт, либо применить правило-ловушку для +. Благодаря способу упорядочения фактов, прежде чем применить правило-ловушку Пролог всегда будет пытаться применить правила для специальных случаев. Поэтому первое решение, полученное предикатом привести,всегда будет являться действительно упрощенным выражением (если оно возможно). Однако альтернативные решения будут иметь не самый простой вид из всех возможных.
Другое упрощение, используемое при выполнении алгебраических преобразований с помощью ЭВМ, известно как свертка констант. В выражении 3*4+aконстанты 3 и 4 могут быть «свернуты», что дает в результате выражение 12+а.Правила свертки констант могут быть добавлены всоответствующие места приведенной выше таблицы упрощений. Правило для сложения констант выглядит следующим образом:
s(+,X,Y,Z):- integer(X), integer(Y), Z is X+Y.
Соответствующие правила для других арифметических операций имеют аналогичный вид.
В коммутативных операциях, таких как умножение и деление, указанные выше упрощения могут давать различный эффект на выражениях, которые записаны по-разному, но алгебраически эквивалентны. Например, если правило свертки констант задано для умножения, то предикат привестисовершенно правильно преобразует 2*3*ав 6*а, но а*2*3или 2*а*3будут преобразовываться в самих себя. Чтобы понять, почему это так, подумайте над тем, как выглядят деревья, представляющие эти выражения (см. рис. 7.4).