Задача выбора кратчайшего пути

Эта программа иллюстрирует те свойства Турбо Пролога, которые явля-

ются особенно полезными при разработке реальных систем. Допустим, мы хо-

тим создать систему, которая помогает выбрать оптимальный маршрут при по-

ездке из одного города США в другой. Мы можем с помощью Турбо Пролога

построить небольшой прототип такой системы (см. программу CH18EX02.PRO),

а с ее помощью оценить и исследовать различные способы решения этой зада-

чи. Модель системы должна давать нам ответы на следующие вопросы:

- Есть ли дорога от данного города в другой город?

- Какой город расположен менее чем в 10 милях от данного

города?

Следующая программа является классическим примером использования по-

иска с возвратом и рекурсии для решения такой задачи.

/* Program CH18EX02.PRO */

domains

town = symbol

distance = integer

predicates

road(town, town, distance)

route(town, town, distance)

clauses

road(tampa, houston, 200).

road(gordon, tampa, 300).

road(houston, gordon, 100).

road(houston, kansas_city, 120).

road(gordon, kansas_city, 130).

route(Town1, Town2, Distance) :-

road(Town1, Town2, Distance).

route(Town1, Town2, Distance) :-

road(Town1, X, Dist1),

route(X, Town2, Dist2),

Distance=Dist1+Dist2.

Рис. 18.1. представляет карту для прототипа системы.

Kansas City О--------------О Tampa

|

|

|

|

|

|

|

Gordon О------------О Houston

Рис. 18.1.

Каждое предложение для предиката road является фактом, который опи-

сывает дорогу, которая обладает определенной длиной и ведет из одного го-

рода в другой.

Предложение для предиката route указывает на то, что возможно проло-

жить маршрут из одного города в другой через несколько промежуточных пун-

ктов. Следуя по маршруту, можно с помощью третьего параметра (distance)

получить общую протяженность маршрута.

Предикат route описан рекурсивно, маршрут может состоять из одного

участка дороги. Тогда общая протяженность маршрута равна длине участка

дороги.

С другой стороны можно проложить маршрут из города Town1 в город

Town2, доехав сначала из города Town1 до города X, а затем проехать дру-

гим путем от города Х до города Town2. Общая протяженность маршрута равна

сумме расстояний от Town1 до Х и от Х до Town2, как показано во втором

предложении для route (дороги).

Испытайте программу с помощью целевого утверждения

route(tampa,kansas_city,X).

Может ли программа проложить маршрут для любого исходного и конечно-

го пунктов маршрута? Если нет, то как изменить программу, чтобы избежать

любых неожиданностей?

В следующем примере вы получите представление о том, как заставить

эту программу составить список всех городов, лежащих на маршруте. Это

позволяет гарантировать, что ни по какому из городов маршрут не пройдет

дважды - это позволит избежать попадания программы в бесконечный цикл.

Когда вы разберетесь со всеми этими вопросами, вы можете расширить систе-

му, добавив в нее другие города и дороги.