Программирование на языке пролог
Шрифт:
Упражнение 7.7.Напишите Пролог-программу случайный_выбортакую, что цель случайный_выбор(L, Е)конкретизирует Е случайно выбранным элементом списка L. Подсказка: используйте генератор случайных чисел и определите предикат, который возвращает N-й элемент списка.
Упражнение 7.8.Задана цель найтивсе(Х,G, L). Что произойдет, если в Gимеются неконкретизированные переменные не сцепленные с X?
7.9. Поиск по графу
Граф – это сеть, состоящая
Проще всего описать граф в базе данных с помощью фактов, представляющих дуги между узлами графа. На рис, 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).
С помощью этого определения предиката а уже имеющаяся программа поиска по графу ( переход) будет находить пути, по которым можно переезжать из одного места на графе в любое другое. Однако программа переходимеет недостаток: когда она успешно завершается, мы не знаем, какой путь она нашла. По меньшей мере мы вправе
переход(Старт,Цель,Путь):- переход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передается список рассматриваемых путей вместе с конечным пунктом, и в последнем аргументе он возвращает удачный путь. Список рассматриваемых путей – это просто все дороги, начинающиеся в начальной точке, которые мы уже рассмотрели. Мы надеемся, что одна из них при продлении даст путь, который приведет нас в конечный пункт. Все пути представлены в виде обратных списков населенных пунктов, так что они могут также выполнять функции перечня мест, где мы уже бывали.
В самом начале имеется только один возможный путь, который можно пытаться продлить. Это просто путь, который начинается в исходном пункте и никуда не ведет. Если мы стартуем из Дарлингтона, то это будет [дарлингтон].Если теперь исследовать пути ведущие из Дарлингтона в соседние города, то можно обнаружить, что имеются два возможных пути [ньюкасл, дарлингтон]и [пенрит, дарлингтон].Поскольку Уэркингтон не встречается ни на одном из этих путей, необходимо решить, какой из этих путей следует продолжить. Если принято решение продлить первый путь, то мы обнаружим, что существует всего один доступный узел – последний город на этом пути. Итак, кроме пути Дарлингтон – Пенрит у нас есть новый путь: [карлайл, ньюкасл, дарлингтон].