1. Завдання
Є якийсь плоский лабіринт. У ньому є деяка точка, через яку ми зобов'язані пройти. У лабіринті один вхід і один вихід. Пройти по найкоротшому шляху, обійшовши всі крапки.
2. Опис рішення і використаного алгоритму
Розробляється програма відноситься до класу задач маршрутизації і є системою прийняття рішення, призначеної для вибору оптимального (найкоротшого) маршруту переміщення в лабіринті з початкової клітини в кінцеву, з урахуванням необхідності відвідування певних клітин.
Для вирішення завдання використовувався пакет Visual Prolog 5.2 Personal Edition.
Введемо найбільш важливі поняття:
а) Клітина;
б) Вільна клітина;
в) Зайнята клітина;
г) Маршрут - послідовність клітин;
д) Початкова клітина;
е) Кінцева клітина;
ж) Обов'язкова клітина - клітина, яку необхідно включати у маршрут;
з) Лінія - послідовність клітин;
і) Сусідні клітини - клітини однієї лінії такі, що з однієї можна перейти в іншу;
к) Перехід - зміна лінії;
л) Допустимий маршрут - маршрут, перша клітина якого початкова клітина, остання - кінцева клітина, при цьому до цієї послідовність входять обов'язкові клітини;
м) Оптимальний маршрут - маршрут, який містить найменшу кількість клітин, в порівнянні з усіма можливими маршрутами при певних вихідних даних.
Виходячи з введених понять, завдання зручно звести до моделі, що описується неорієнтованим графом. Тоді введені раніше поняття, необхідно інтерпретувати в такий спосіб:
а) Клітина - вершина графа;
б) Можливість переходу - ребро графа;
в) Маршрут - послідовність вершин, з'єднаних ребрами;
г) Початкова клітина - початкова вершина маршруту;
д) Кінцева клітина - кінцева вершина маршруту;
е) Обов'язкова клітина - вершина, яку необхідно включати у маршрут;
ж) Лінія - послідовність вершин, з'єднаних ребрами, без розгалужень;
і) Сусідні клітини - вершини однієї лінії, з'єднані ребром;
к) Перехід - зміна лінії (може бути здійснена при попаданні в вершину з якої виходять більше двох ребер);
л) Допустимий маршрут - маршрут, перша вершина якого початкова клітина, остання - кінцева клітина, при цьому до цієї послідовність входять обов'язкові клітини;
м) Оптимальний маршрут - маршрут, який містить найменшу кількість вершин, у порівнянні з усіма можливими маршрутами при певних вихідних даних.
Маршрут S (l 0, l 1, l 2, ..., l n) має не визначене число вершин. Кожен елемент l i Î V, де V безліч вершин графа. Безліч кандидатів на місце l i є безліч вершин з'єднаних ребрами з вершиною l i-1. Пошук маршруту у даній реалізації алгоритму ведеться від початкової вершини до кінцевої. При цьому, для виключення циклів, на кандидатів на місце l i вводиться додаткове обмеження: l i ¹ l 1, l i ¹ l 2, ..., l i ¹ l i-1. Таким чином, клітина в маршруті може зустрітися тільки один раз . Крім того, необхідно контролювати потрапляння всіх обов'язкових клітин в маршрут. Оскільки маршрутів задовольняють даним умовам може бути знайдено кілька, то з них слід вибрати оптимальний маршрут. Після знаходження всіх можливих маршрутів з них вибирається маршрут, що має найменшу кількість вершин.
3. Інтерфейс користувача
а) Запуск програми:
Для запуску програми необхідно завантажити пакет Visual Prolog 5.2 Personal Edition і відкрити файл LABIRINT. PRO. Потім у головному меню програми вибрати пункт Projects і в який з'явився падаючому меню вибрати рядок Test Goal. Має з'явитися робоче вікно програми.
б) Введення вихідних даних:
Після запуску, програма виводить привітання:
Вибір маршруту пересування в лабіринті з відвідуванням обов'язкових клітин. Схему лабіринту можна знайти у додатку пояснювальної записки.
Потім програма запитує початкову клітину:
Введіть назву початкової клітини =
Користувачеві слід ввести назву деякої клітини (наприклад, «а1») і натиснути клавішу Enter:
Введіть назву початкової клітини = a1
Аналогічно відбувається введення кінцевої клітини:
Введіть назву кінцевої клітини = d7
Обмеження: необхідно вводити назву існуючої.
Якщо буде введено назву неіснуючої клітини, результатом роботи програми буде висновок «no».
Після цього програма запитує кількість обов'язкових клітин. Слід ввести ціле число і натиснути клавішу Enter:
Скільки обов'язкових клітин Ви хочете ввести:
Обмеження: необхідно вводити ціле число, інакше програма вимагає повторити введення, вивівши повідомлення:
Необхідно ввести ціле число. Будь ласка, повторіть введення.
Скільки обов'язкових клітин Ви хочете ввести:
Потім програма просить ввести послідовно назви обов'язкових клітин (після кожного введеного назви слід натискати клавішу Enter):
Введіть обов'язкову клітку: a4
Введіть обов'язкову клітку: c3
Обмеження: необхідно вводити різні назви клітин. Якщо на цьому етапі одна назва клітини буде введено кілька разів, програма видасть попередження і попросить повторити введення:
Клітка з такою назвою вже була введена
Введіть обов'язкову клітку:
Якщо буде введено назву неіснуючої клітини, це призведе до неможливості виконання завдання.
4. Тестовий приклад
Введемо в якості початкової і кінцевої клітини, клітини належать різним лініям (наприклад, «c 1» і «b 6»). Введемо декілька обов'язкових клітин, так, щоб вони впливали на побудову оптимального маршруту.
Вибір маршруту пересування в лабіринті з відвідуванням обов'язкових клітин
Схему лабіринту можна знайти у додатку пояснювальної записки
Введіть назву початкової клітини = d1
Введіть назву кінцевої клітини = b6
Скільки обов'язкових клітин Ви хочете ввести: 2
Введіть обов'язкову клітку: g1
Введіть останню обов'язкову клітку: e5
Оптимальний маршрут:
d1 - d2 - e2 - f2 - g2 - g1 - h1 - h2 - h3 - h4 - g4 - g5 - f5 - e5 - d5 - d6 - c6 - b6
Кількість кроків: 18
yes
5. Текст програми
DOMAINS
/ * ОПИС ТИПІВ ДАНИХ * /
спісок_сімв = symbol *
спісок_цел = integer *
PREDICATES
/ * ОПИС Предикат * /
nondeterm лінія (symbol, список _ симв)
nondeterm хв _1 (real, список _ цілий)
nondeterm хв (real, список _ цілий)
nondeterm належить (symbol, спісок_сімв)
nondeterm посл (symbol, symbol, список _ симв)
nondeterm сусідні (symbol, symbol, symbol)
nondeterm перехід (symbol, symbol, symbol)
nondeterm маршрут (symbol, symbol, список _ симв, integer, symbol, список _ симв, список _ симв, integer)
nondeterm введення _ зобов (список _ симв, integer)
nondeterm введення _ к _ зобов (integer)
nondeterm введення _ назв _ зобов (integer, список _ симв, список _ симв)
nondeterm write_ маршрут (список _ симв, symbol)
nondeterm run
CLAUSES
/ * ОПІІСАНІЕ ЛІНІЙ * /
лінія (лінія _a, [a1, a2, a3, a4]).
лінія (лінія _a, [a7, a8]).
лінія (лінія_b, [b3, b4, b5, b6, b7, b8]).
лінія (лінія_d, [d1, d2, d3, d4, d5, d6]).
лінія (лінія_e, [e2, e3]).
лінія (лінія_ee, [e5, e6, e7, e8]).
лінія (лінія_f, [f5, f6]).
лінія (лінія_g, [g1, g2, g3, g4, g5, g6, g7, g8]).
лінія (лінія_h, [h1, h2, h3, h4]).
лінія (лінія_h, [h6, h7, h8]).
лінія (лінія_1, [a1, b1, c1, d1]).
лінія (лінія_11, [g1, h1]).
лінія (лінія_2, [d2, e2, f2, g2]).
лінія (лінія_3, [a3, b3, c3, d3, e3]).
лінія (лінія_33, [g3, h3]).
лінія (лінія_4, [a4, b4]).
лінія (лінія_44, [g4, h4]).
лінія (лінія_5, [d5, e5, f5, g5]).
лінія (лінія_6, [b6, c6, d6, e6, f6, g6, h6]).
лінія (лінія_7, [a7, b7]).
лінія (лінія_77, [g7, h7]).
лінія (лінія_8, [a8, b8, c8, d8, e8]).
лінія (лінія_88, [g8, h8]).
/ * ПОШУК МІНІМАЛЬНОГО ЕЛЕМЕНТА У СПИСКУ * /
мін_1 (_, []).
мін_1 (Елемент, [X | Хвіст]): - Елемент <= X, мін_1 (Елемент, Хвіст).
хв (Елемент, [X | Хвіст]): - Елемент = X, мін_1 (Елемент, Хвіст),!; хв (Елемент, Хвіст).
/ * ПЕРЕВІРКА НА НАЛЕЖНІСТЬ ЕЛЕМЕНТА СПИСКУ * /
належить (Елемент, [Елемент |_]).
належить (Елемент, [_ | Хвіст]): - належить (Елемент, Хвіст).
/ * ПЕРЕВІРКА ДВОХ ЕЛЕМЕНТІВ НА послідовне розташування У СПИСКУ * /
посл (Елемент1, Елемент2, [Елемент1, Елемент2 |_]).
посл (Елемент1, Елемент2, [_ | Хвіст]): - посл (Елемент1, Елемент2, Хвіст).
/ * ПЕРЕВІРКА: ЧИ Є клітини сусідніх * /
сусідні (Клетка1, Клетка2, Лінія): -
лінія (Лінія, Список),
належить (Клетка1, Список), належить (Клетка2, Список),
посл (Клетка1, Клетка2, Список);
лінія (Лінія, Список),
належить (Клетка1, Список), належить (Клетка2, Список),
посл (Клетка2, Клетка1, Список).
/ * ПЕРЕВІРКА КЛІТИНИ НА МОЖЛИВІСТЬ ВЧИНЕННЯ ПЕРЕСАДКИ * /
перехід (Клітка, Лінія1, Лінія2): - лінія (Лінія1, список1), лінія (Лінія2, список2),
належить (Клітка, список1), належить (Клітка, список2),
Лінія1 <> Лінія2.
/ * ПОШУК МАРШРУТУ * /
маршрут (Клітка, Клітка, [Клітка], 1, Лінія, _, Обов'язкові, КолОбяз): - лінія (Лінія, Список), належить (Клітка, Список), КолОбяз = 0.
% Знаходження наступної клітини в маршруті без переходу
маршрут (КлНачал, КлКонеч, [КлНачал, КлНачал2 | Хвіст], ВесМаршрута1, Лінія, Недоступні, Обов'язкові, КолОбяз1): -
сусідні (КлНачал, КлНачал2, Лінія),
not (належить (КлНачал2, Недоступні)),
маршрут (КлНачал2, КлКонеч, [КлНачал2 | Хвіст], ВесМаршрута2, Лінія, [КлНачал2 | Недоступні], Обов'язкові, КолОбяз1),
ВесМаршрута1 = ВесМаршрута2 + 1;
сусідні (КлНачал, КлНачал2, Лінія),
not (належить (КлНачал2, Недоступні)),
належить (КлНачал2, Обов'язкові),
КолОбяз2 = КолОбяз1 - 1,
маршрут (КлНачал2, КлКонеч, [КлНачал2 | Хвіст], ВесМаршрута2, Лінія, [КлНачал2 | Недоступні], Обов'язкові, КолОбяз2),
ВесМаршрута1 = ВесМаршрута2 + 1.
% Знаходження наступної клітці в маршруті з переходом
маршрут (КлНачал, КлКонеч, [КлНачал, КлНачал2 | Хвіст], ВесМаршрута1, Лінія, Недоступні, Обов'язкові, КолОбяз1): -
перехід (КлНачал, Лінія, Новая_Лінія),
сусідні (КлНачал, КлНачал2, Новая_Лінія),
not (належить (КлНачал2, Недоступні)),
маршрут (КлНачал2, КлКонеч, [КлНачал2 | Хвіст], ВесМаршрута2, Новая_Лінія, [КлНачал2 | Недоступні], Обов'язкові, КолОбяз1),
ВесМаршрута1 = ВесМаршрута2 + 1;
перехід (КлНачал, Лінія, Новая_Лінія),
сусідні (КлНачал, КлНачал2, Новая_Лінія),
not (належить (КлНачал2, Недоступні)),
належить (КлНачал2, Обов'язкові),
КолОбяз2 = КолОбяз1 - 1,
маршрут (КлНачал2, КлКонеч, [КлНачал2 | Хвіст], ВесМаршрута2, Новая_Лінія, [КлНачал2 | Недоступні], Обов'язкові, КолОбяз2),
ВесМаршрута1 = ВесМаршрута2 + 1.
/ * ВИСНОВОК МАРШРУТУ * /
% Висновок останньої клітини маршруту
write_маршрут ([Клітка], Лінія): - лінія (Лінія, Список),
належить (Клітка, Список), write (Клітка).
% Висновок клітини без переходу
write_маршрут ([Клітка, Клетка2 | Хвіст], Лінія): -
сусідні (Клітка, Клетка2, Лінія),
write (Клітка, »-»),
write_маршрут ([Клетка2 | Хвіст], Лінія).
% Висновок клітини c переходом
write_маршрут ([Клітка, Клетка2 | Хвіст], Лінія): -
перехід (Клітка, Лінія, Новая_Лінія),
сусідні (Клітка, Клетка2, Новая_Лінія),
write (Клітка, »-»),
write_маршрут ([Клетка2 | Хвіст], Новая_Лінія).
/ * ВВІД ОБОВ'ЯЗКОВИХ СТАНЦІЙ * /
ввод_назв_обяз (0, [], []): -!.
ввод_назв_обяз (1, Обов'язкові, ВведенниеОбяз): -
write («Введіть останню обов'язкову клітку:»),
readln (Клітка),
not (належить (Клітка, ВведенниеОбяз)),
Обов'язкові = [Клітка],!.
ввод_назв_обяз (КолОбяз, Обов'язкові, ВведенниеОбяз): -
КолОбяз> 1,
write («Введіть обов'язкову клітку:»),
readln (Клітка),
not (належить (Клітка, ВведенниеОбяз)),
КолОбяз2 = КолОбяз-1,
ввод_назв_обяз (КолОбяз2, Обязательние2, [Клітка | ВведенниеОбяз]),
Обов'язкові = [Клітка | Обязательние2],!;
write («Клітка з такою назвою вже була введена»),
nl,
ввод_назв_обяз (КолОбяз, Обов'язкові, ВведенниеОбяз).
ввод_кол_обяз (КолОбяз): -
write («Скільки обов'язкових клітин Ви хочете ввести:»),
readln (Рядок),
str_int (Рядок, КолОбяз),!;
write («Необхідно ввести ціле число. Будь ласка, повторіть введення.»),
nl,
ввод_кол_обяз (КолОбяз).
ввод_обяз (Обов'язкові, КолОбяз): - ввод_кол_обяз (КолОбяз), ввод_назв_обяз (КолОбяз, Обов'язкові, []).
/ * ЗАПУСК ПРОГРАМИ * /
run: - write («Вибір маршруту пересування в лабіринті з відвідуванням обов'язкових клітин»), nl,
write («Схему лабіринту можна знайти у додатку пояснювальній записки»), nl,
write («Введіть назву початкової клітини =»), readln (КлНачал),
write («Введіть назву кінцевої клітини =»), readln (КлКонеч),
ввод_обяз (Обов'язкові, КолОбяз),
findall (ВесМаршрута, маршрут (КлНачал, КлКонеч, _, ВесМаршрута, _, [КлНачал], Обов'язкові, КолОбяз), СпісокВесМаршрута),
хв (ВесМаршрута, СпісокВесМаршрута),
маршрут (КлНачал, КлКонеч, Маршрут, ВесМаршрута, _, [КлНачал], Обов'язкові, КолОбяз),
write («Оптимальний маршрут:»), nl,
write_маршрут (Маршрут, _), nl,
КолСт = round (ВесМаршрута),
write («Кількість кроків:», КолСт), nl.
GOAL
run.
Додаток
Схема використаного в програмі лабіринту
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
A | X | X | ||||||
B | X | |||||||
C | X | X | X | X | ||||
D | X | |||||||
E | X | X | ||||||
F | X | X | X | X | X | |||
G | ||||||||
H | X |