Page 31 - 4800

Використовуючи це відношення, можна сформувати базу даних по
транспортних магістралях, з допомогою якої можна виконувати пошук маршруту між
двома заданими містами і визначення відстані між ними. Таким чином, постає задача
розробки процедури формування нового відношення
Шлях(Місто_1, Місто_2, Довжина_шляху),
на основі вихідного відношення “дорога”. Метод рекурсії, що використовувався при
складанні процедури “предок” можна застосувати і в цьому випадку.
/* програма 3.2 */
domains
town = string
distance = integer
predicates
road(town, town, distance)
route(town,town,distance)
clauses
road(„Івано-Франківськ”, ”Львів”, 135).
road(„Івано-Франківськ”, „Тернопіль”, 137).
rоаd(„Луцьк”, „Львів”, 152).
road(„Луцьк”, „Тернопіль”, 163).
rоаd(„Львів”, „Тернопіль”, 127).
route(Town1, Town2, Distance):-road(Town1 ,Town2, Distance).
route(Town1, Town2, Distance):-road(Town1, X, Dist1), route(X, Town2, Dist2),
Distance=Dist1+Dist2, !.
У процедурі route() відношення між двома містами буде дотримуватися, якщо
існує дорога, якою можна добратися з одного міста в іншій через ряд населених
пунктів. Кожна пропозиція для предиката road() описує дорогу з одного міста в іншій,
що має визначену відстань.
Правила процедури route() указують на можливість як прямого маршруту, так і
маршруту через інші міста. Предикат route() визначений рекурсивно.
Якщо маршрут містить тільки одну ділянку дороги, то в цьому випадку відстань
між містами дорівнює довжині цієї ділянки.
У випадку, якщо маршрут з Міста_1 у Місто_2 є сумою маршрутів з Міста_1 у
Х і з Х в Місто_2, то відстань між Містом_1 і Містом_2 буде дорівнює відстані між
Містом_1 і Х плюс відстань між Містом_2 і X, тобто сумі двох відстаней.
Друге правило є рекурсивним. Відношення, записане в заголовку правила,
залежить від більш простої версії самого себе. Перше правило визначає граничну умова
виходу з рекурсії. Як тільки воно стане істинним, то процес рекурсії припинитися.

Луцьк
163

152 Тернопіль
127

Львів 137
135
Івано-
Франківськ

Рисунок 3.3 – Симетричне транзитивне відношення
Дана програма не здатна врахувати всі можливі комбінації початкових і
кінцевих точок маршрутів, тому що при формуванні процедури не враховані
обмеження, що забезпечують цілісність відношень.

31