48229 (Программа выбора оптимального (наикратчайшего) маршрута перемещения в лабиринте)

1. Задание

Имеется некий плоский лабиринт. В нем есть некоторая точка, через которую мы обязаны пройти. В лабиринте один вход и один выход. Пройти по кратчайшему пути, обойдя все точки.

2. Описание решения и использованного алгоритма

Разрабатываемая программа относится к классу задач маршрутизации и является системой принятия решения, предназначенной для выбора оптимального (наикратчайшего) маршрута перемещения в лабиринте из начальной клетки в конечную, с учетом необходимости посещения определенных клеток.

Для решения задачи использовался пакет Visual Prolog 5.2 Personal Edition.

Введем наиболее важные понятия:

а) Клетка;

б) Свободная клетка;

в) Занятая клетка;

г) Маршрут – последовательность клеток;

д) Начальная клетка;

е) Конечная клетка;

ж) Обязательная клетка – клетка, которую необходимо включать в маршрут;

з) Линия – последовательность клеток;

и) Соседние клетки – клетки одной линии такие, что из одной можно перейти в другую;

к) Переход – смена линии;

л) Допустимый маршрут – маршрут, первая клетка которого начальная клетка, последняя – конечная клетка, при этом в данную последовательность входят обязательные клетки;

м) Оптимальный маршрут – маршрут, содержащий наименьшее количество клеток, по сравнению со всеми возможными маршрутами при определенных исходных данных.

Исходя из введенных понятий, задачу удобно свести к модели, описываемой неориентированным графом. Тогда введенные ранее понятия, необходимо интерпретировать следующим образом:

а) Клетка – вершина графа;

б) Возможность перехода – ребро графа;

в) Маршрут – последовательность вершин, соединенных ребрами;

г) Начальная клетка – начальная вершина маршрута;

д) Конечная клетка – конечная вершина маршрута;

е) Обязательная клетка – вершина, которую необходимо включать в маршрут;

ж) Линия – последовательность вершин, соединенных ребрами, без разветвлений;

и) Соседние клетки – вершины одной линии, соединенные ребром;

к) Переход – смена линии (может быть осуществлена при попадании в вершину из которой выходят более двух ребер);

л) Допустимый маршрут – маршрут, первая вершина которого начальная клетка, последняя – конечная клетка, при этом в данную последовательность входят обязательные клетки;

м) Оптимальный маршрут – маршрут, содержащий наименьшее количество вершин, по сравнению со всеми возможными маршрутами при определенных исходных данных.

Маршрут S(l₀, l₁, l₂,…, l_n) имеет не определенное число вершин. Каждый элемент l_iV, где V множество вершин графа. Множество кандидатов на место l_i есть множество вершин соединенных ребрами с вершиной l_i-1. Поиск маршрута в данной реализации алгоритма ведется от начальной вершины к конечной. При этом, для исключения циклов, на кандидатов на место l_i вводится дополнительное ограничение: l_il₁, l_il₂,…, l_il_i-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, список_симв, список_симв)

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 (ВесМаршрута, маршрут (КлНачал, КлКонеч,_, ВесМаршрута,_, [КлНачал], Обязательные, КолОбяз), СписокВесМаршрута),

мин (ВесМаршрута, СписокВесМаршрута),

маршрут (КлНачал, КлКонеч, Маршрут, ВесМаршрута,_, [КлНачал], Обязательные, КолОбяз),