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

Маршрут 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. Интерфейс пользователя

а) Запуск программы:

Для запуска программы необходимо загрузить пакет VisualProlog 5.2 PersonalEdition и открыть файл LABIRINT.PRO. Затем в главном меню приложения выбрать пункт Projects и в появившемся падающем меню выбрать строку TestGoal. Должно появиться рабочее окно программы.

б) Ввод исходных данных:

После запуска, программа выводит приветствие:

Выбор маршрута передвижения в лабиринте с посещением обязательных клеток. Схему лабиринта можно найти в приложении пояснительной записки.

Затем программа запрашивает начальную клетку:

Введите название начальной клетки =

Пользователю следует ввести название некоторой клетки (например, «а1») и нажать клавишу Enter:

Введите название начальной клетки = a1

Аналогично происходит ввод конечной клетки:

Введите название конечной клетки = d7

Ограничение:необходимо вводить название существующей.

Если будет введено название несуществующей клетки, результатом работы программы будет вывод «no».

После этого программа запрашивает количество обязательных клеток. Следует ввести целое число и нажать клавишу Enter:

Сколько обязательных клеток Вы хотите ввести:

Ограничение:необходимо вводить целое число, иначе программа потребует повторить ввод, выведя сообщение:

Необходимо ввести целое число. Пожалуйста, повторите ввод.

Сколько обязательных клеток Вы хотите ввести:

Затем программа просит ввести последовательно названия обязательных клеток (после каждого введенного названия следует нажимать клавишу Enter):

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

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

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

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

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

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

4. Тестовый пример

Введем в качестве начальной и конечной клетки, клетки принадлежащие разным линиям (например, «c1» и «b6»). Введем несколько обязательных клеток, так, чтобы они влияли на построение оптимального маршрута.

Выбор маршрута передвижения в лабиринте с посещением обязательных клеток