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. Таким образом, клетка в маршруте может встретиться только один раз. Кроме того, необходимо контролировать попадание всех обязательных клеток в маршрут. Поскольку маршрутов удовлетворяющих данным условиям может быть найдено несколько, то из них следует выбрать оптимальный маршрут. После нахождения всех возможных маршрутов из них выбирается маршрут, имеющий наименьшее количество вершин.