Программирование на языке пролог (ЛП)

Наш «изыскатель», переход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,Путь).

Эта новая программа успешно строит возможные пути в по-рядке возрастания их фактической протяженности. Может быть, вам захочется изменить ее так, чтобы вместе с ответами она печатала длины различных путей.