У Клоксин - ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ ПРОЛОГ

переход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, чтобы он выглядел следующим образом: