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

1. Задание

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

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

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

Для решения задачи использовался пакет VisualProlog 5.2 PersonalEdition.

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

а) Клетка;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--