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

1. Задание

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

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

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

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

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

а) Клетка;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничение: необходимо вводить различные названия клеток. Если на этом этапе одно название клетки будет введено несколько раз, программа выдаст предупреждение и попросит повторить ввод:

Клетка с таким названием уже была введена

Введите обязательную клетку:

Если будет введено название несуществующей клетки, это приведет к невозможности выполнения задачи.