1. Задание
Имеется некийплоский лабиринт. В нем есть некоторая точка, через которую мы обязаны пройти.В лабиринте один вход и один выход. Пройти по кратчайшему пути, обойдя всеточки.
2.Описание решения и использованного алгоритма
Разрабатываемаяпрограмма относится к классу задач маршрутизации и является системой принятиярешения, предназначенной для выбора оптимального (наикратчайшего) маршрутаперемещения в лабиринте из начальной клетки в конечную, с учетом необходимостипосещения определенных клеток.
Для решениязадачи использовался пакет Visual Prolog 5.2 Personal Edition.
Введемнаиболее важные понятия:
а) Клетка;
б) Свободнаяклетка;
в) Занятаяклетка;
г) Маршрут –последовательность клеток;
д) Начальнаяклетка;
е) Конечнаяклетка;
ж)Обязательная клетка – клетка, которую необходимо включать в маршрут;
з) Линия –последовательность клеток;
и) Соседниеклетки – клетки одной линии такие, что из одной можно перейти в другую;
к) Переход –смена линии;
л) Допустимыймаршрут – маршрут, первая клетка которого начальная клетка, последняя – конечнаяклетка, при этом в данную последовательность входят обязательные клетки;
м) Оптимальныймаршрут – маршрут, содержащий наименьшее количество клеток, по сравнению совсеми возможными маршрутами при определенных исходных данных.
Исходя извведенных понятий, задачу удобно свести к модели, описываемой неориентированнымграфом. Тогда введенные ранее понятия, необходимо интерпретировать следующимобразом:
а) Клетка –вершина графа;
б) Возможностьперехода – ребро графа;
в) Маршрут –последовательность вершин, соединенных ребрами;
г) Начальнаяклетка – начальная вершина маршрута;
д) Конечнаяклетка – конечная вершина маршрута;
е) Обязательнаяклетка – вершина, которую необходимо включать в маршрут;
ж) Линия –последовательность вершин, соединенных ребрами, без разветвлений;
и) Соседние клетки– вершины одной линии, соединенные ребром;
к) Переход –смена линии (может быть осуществлена при попадании в вершину из которой выходятболее двух ребер);
л) Допустимыймаршрут – маршрут, первая вершина которого начальная клетка, последняя –конечная клетка, при этом в данную последовательность входят обязательныеклетки;
м)Оптимальный маршрут – маршрут, содержащий наименьшее количество вершин, посравнению со всеми возможными маршрутами при определенных исходных данных.
Маршрут S(l0,l1, l2,…, ln) имеет не определенное числовершин. Каждый элемент liÎV, где V множество вершинграфа. Множество кандидатов на место li есть множество вершинсоединенных ребрами с вершиной li-1. Поиск маршрута в даннойреализации алгоритма ведется от начальной вершины к конечной. При этом, дляисключения циклов, на кандидатов на место li вводится дополнительноеограничение: li¹l1, li¹l2,…, li¹li-1. Такимобразом, клетка в маршруте может встретиться только один раз. Кроме того,необходимо контролировать попадание всех обязательных клеток в маршрут.Поскольку маршрутов удовлетворяющих данным условиям может быть найденонесколько, то из них следует выбрать оптимальный маршрут. После нахождения всехвозможных маршрутов из них выбирается маршрут, имеющий наименьшее количествовершин./>/>/>/>/>/>/>3. Интерфейс пользователя
а) Запускпрограммы:
Для запускапрограммы необходимо загрузить пакет Visual Prolog 5.2 Personal Edition и открыть файл LABIRINT.PRO. Затем в главном менюприложения выбрать пункт Projects и в появившемся падающем меню выбрать строку Test Goal. Должно появитьсярабочее окно программы.
б) Вводисходных данных:
Послезапуска, программа выводит приветствие:
Выбормаршрута передвижения в лабиринте с посещением обязательных клеток. Схему лабиринтаможно найти в приложении пояснительной записки.
Затемпрограмма запрашивает начальную клетку:
Введитеназвание начальной клетки =
Пользователюследует ввести название некоторой клетки (например, «а1») и нажать клавишу Enter:
Введитеназвание начальной клетки = a1
Аналогичнопроисходит ввод конечной клетки:
Введитеназвание конечной клетки = d7
Ограничение:необходимо вводить название существующей.
Если будетвведено название несуществующей клетки, результатом работы программы будетвывод «no».
После этогопрограмма запрашивает количество обязательных клеток. Следует ввести целоечисло и нажать клавишу Enter:
Сколько обязательныхклеток Вы хотите ввести:
Ограничение:необходимо вводить целое число, иначе программа потребует повторить ввод,выведя сообщение:
Необходимоввести целое число. Пожалуйста, повторите ввод.
Сколько обязательныхклеток Вы хотите ввести:
Затемпрограмма просит ввести последовательно названия обязательных клеток (послекаждого введенного названия следует нажимать клавишу Enter):
Введите обязательнуюклетку: a4
Введите обязательнуюклетку: c3
Ограничение:необходимо вводить различные названия клеток. Если на этом этапе одно название клеткибудет введено несколько раз, программа выдаст предупреждение и попроситповторить ввод:
Клетка стаким названием уже была введена
Введите обязательнуюклетку:
Если будетвведено название несуществующей клетки, это приведет к невозможности выполнениязадачи.
4.Тестовый пример
Введем вкачестве начальной и конечной клетки, клетки принадлежащие разным линиям(например, «c1»и «b6»). Введем несколько обязательныхклеток, так, чтобы они влияли на построение оптимального маршрута.
Выбормаршрута передвижения в лабиринте с посещением обязательных клеток
Схемулабиринта можно найти в приложении пояснительной записки
Введитеназвание начальной клетки = 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, список_симв, список_симв)
nondetermwrite_маршрут (список_симв, symbol)
nondetermrun
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|Хвост]): – Элемент=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