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. ............