Контрольная работа: Программа выбора оптимального (наикратчайшего) маршрута перемещения в лабиринте
💣 👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
Имеется некий плоский лабиринт. В нем есть некоторая точка, через которую мы обязаны пройти. В лабиринте один вход и один выход. Пройти по кратчайшему пути, обойдя все точки.
2. Описание решения и использованного алгоритма
Разрабатываемая программа относится к классу задач маршрутизации и является системой принятия решения, предназначенной для выбора оптимального (наикратчайшего) маршрута перемещения в лабиринте из начальной клетки в конечную, с учетом необходимости посещения определенных клеток.
Для решения задачи использовался пакет VisualProlog 5.2 PersonalEdition.
г) Маршрут – последовательность клеток;
ж) Обязательная клетка – клетка, которую необходимо включать в маршрут;
з) Линия – последовательность клеток;
и) Соседние клетки – клетки одной линии такие, что из одной можно перейти в другую;
л) Допустимый маршрут – маршрут, первая клетка которого начальная клетка, последняя – конечная клетка, при этом в данную последовательность входят обязательные клетки;
м) Оптимальный маршрут – маршрут, содержащий наименьшее количество клеток, по сравнению со всеми возможными маршрутами при определенных исходных данных.
Исходя из введенных понятий, задачу удобно свести к модели, описываемой неориентированным графом. Тогда введенные ранее понятия, необходимо интерпретировать следующим образом:
б) Возможность перехода – ребро графа;
в) Маршрут – последовательность вершин, соединенных ребрами;
г) Начальная клетка – начальная вершина маршрута;
д) Конечная клетка – конечная вершина маршрута;
е) Обязательная клетка – вершина, которую необходимо включать в маршрут;
ж) Линия – последовательность вершин, соединенных ребрами, без разветвлений;
и) Соседние клетки – вершины одной линии, соединенные ребром;
к) Переход – смена линии (может быть осуществлена при попадании в вершину из которой выходят более двух ребер);
л) Допустимый маршрут – маршрут, первая вершина которого начальная клетка, последняя – конечная клетка, при этом в данную последовательность входят обязательные клетки;
м) Оптимальный маршрут – маршрут, содержащий наименьшее количество вершин, по сравнению со всеми возможными маршрутами при определенных исходных данных.
Маршрут S(l 0
, l 1
, l 2
,…, l n
) имеет не определенное число вершин. Каждый элемент l i
ÎV, где V множество вершин графа. Множество кандидатов на место l i
есть множество вершин соединенных ребрами с вершиной l i-1
. Поиск маршрута в данной реализации алгоритма ведется от начальной вершины к конечной. При этом, для исключения циклов, на кандидатов на место l i
вводится дополнительное ограничение: l i
¹l 1
, l i
¹l 2
,…, l i
¹l i-1.
Таким образом, клетка в маршруте может встретиться только один раз. Кроме того, необходимо контролировать попадание всех обязательных клеток в маршрут. Поскольку маршрутов удовлетворяющих данным условиям может быть найдено несколько, то из них следует выбрать оптимальный маршрут. После нахождения всех возможных маршрутов из них выбирается маршрут, имеющий наименьшее количество вершин.
Для запуска программы необходимо загрузить пакет VisualProlog 5.2 PersonalEdition и открыть файл LABIRINT.PRO. Затем в главном меню приложения выбрать пункт Projects и в появившемся падающем меню выбрать строку TestGoal. Должно появиться рабочее окно программы.
После запуска, программа выводит приветствие:
Выбор маршрута передвижения в лабиринте с посещением обязательных клеток. Схему лабиринта можно найти в приложении пояснительной записки.
Затем программа запрашивает начальную клетку:
Введите название начальной клетки =
Пользователю следует ввести название некоторой клетки (например, «а1») и нажать клавишу Enter:
Введите название начальной клетки = a1
Аналогично происходит ввод конечной клетки:
Введите название конечной клетки = d7
Ограничение:необходимо вводить название существующей.
Если будет введено название несуществующей клетки, результатом работы программы будет вывод «no».
После этого программа запрашивает количество обязательных клеток. Следует ввести целое число и нажать клавишу Enter:
Сколько обязательных клеток Вы хотите ввести:
Ограничение:необходимо вводить целое число, иначе программа потребует повторить ввод, выведя сообщение:
Необходимо ввести целое число. Пожалуйста, повторите ввод.
Сколько обязательных клеток Вы хотите ввести:
Затем программа просит ввести последовательно названия обязательных клеток (после каждого введенного названия следует нажимать клавишу Enter):
Ограничение: необходимо вводить различные названия клеток. Если на этом этапе одно название клетки будет введено несколько раз, программа выдаст предупреждение и попросит повторить ввод:
Клетка с таким названием уже была введена
Если будет введено название несуществующей клетки, это приведет к невозможности выполнения задачи.
Введем в качестве начальной и конечной клетки, клетки принадлежащие разным линиям (например, «c1» и «b6»). Введем несколько обязательных клеток, так, чтобы они влияли на построение оптимального маршрута.
Выбор маршрута передвижения в лабиринте с посещением обязательных клеток
Схему лабиринта можно найти в приложении пояснительной записки
Введите название начальной клетки = d1
Введите название конечной клетки = b6
Сколько обязательных клеток Вы хотите ввести: 2
Введите последнюю обязательную клетку: e5
d1 – d2 – e2 – f2 – g2 – g1 – h1 – h2 – h3 – h4 – g4 – g5 – f5 – e5 – d5 – d6 – c6 – b6
nondeterm линия (symbol, список_симв)
nondeterm принадлежит (symbol, список_симв)
nondeterm посл (symbol, symbol, список_симв)
nondeterm соседние (symbol, symbol, symbol)
nondeterm переход (symbol, symbol, symbol)
nondeterm маршрут (symbol, symbol, список_симв, integer, symbol, список_симв, список_симв, integer)
nondeterm ввод_обяз (список_симв, integer)
nondeterm ввод_назв_обяз (integer, список_симв, список_симв)
nondeterm write_маршрут (список_симв, symbol)
линия (линия_b, [b3, b4, b5, b6, b7, b8]).
линия (линия_d, [d1, d2, d3, d4, d5, d6]).
линия (линия_ee, [e5, e6, e7, e8]).
линия (линия_g, [g1, g2, g3, g4, g5, g6, g7, g8]).
линия (линия_3, [a3, b3, c3, d3, e3]).
линия (линия_6, [b6, c6, d6, e6, f6, g6, h6]).
линия (линия_8, [a8, b8, c8, d8, e8]).
/* ПОИСК МИНИМАЛЬНОГО ЭЛЕМЕНТА В СПИСКЕ */
мин_1 (Элемент, [X|Хвост]): – Элемент<=X, мин_1 (Элемент, Хвост).
мин (Элемент, [X|Хвост]): – Элемент=X, мин_1 (Элемент, Хвост),!; мин (Элемент, Хвост).
/* ПРОВЕРКА НА ПРИНАДЛЕЖНОСТЬ ЭЛЕМЕНТА СПИСКУ */
принадлежит (Элемент, [Элемент|_]).
принадлежит (Элемент, [_|Хвост]): – принадлежит (Элемент, Хвост).
/* ПРОВЕРКА ДВУХ ЭЛЕМЕНТОВ НА ПОСЛЕДОВАТЕЛЬНОЕ РАСПОЛОЖЕНИЕ В СПИСКЕ */
посл (Элемент1, Элемент2, [Элемент1, Элемент2|_]).
посл (Элемент1, Элемент2, [_|Хвост]): – посл (Элемент1, Элемент2, Хвост).
/* ПРОВЕРКА: ЯВЛЯЮТСЯ ЛИ КЛЕТКИ СОСЕДНИМИ */
соседние (Клетка1, Клетка2, Линия):-
принадлежит (Клетка1, Список), принадлежит (Клетка2, Список),
принадлежит (Клетка1, Список), принадлежит (Клетка2, Список),
/* ПРОВЕРКА КЛЕТКИ НА ВОЗМОЖНОСТЬ СОВЕРШЕНИЯ ПЕРЕСАДКИ */
переход (Клетка, Линия1, Линия2): – линия (Линия1, Список1), линия (Линия2, Список2),
принадлежит (Клетка, Список1), принадлежит (Клетка, Список2),
маршрут (Клетка, Клетка, [Клетка], 1, Линия,_, Обязательные, КолОбяз): – линия (Линия, Список), принадлежит (Клетка, Список), КолОбяз=0.
% нахождение следующей клетки в маршруте без перехода
маршрут (КлНачал, КлКонеч, [КлНачал, КлНачал2|Хвост], ВесМаршрута1, Линия, Недоступные, Обязательные, КолОбяз1):-
соседние (КлНачал, КлНачал2, Линия),
not (принадлежит (КлНачал2, Недоступные)),
маршрут (КлНачал2, КлКонеч, [КлНачал2|Хвост], ВесМаршрута2, Линия, [КлНачал2|Недоступные], Обязательные, КолОбяз1),
соседние (КлНачал, КлНачал2, Линия),
not (принадлежит (КлНачал2, Недоступные)),
принадлежит (КлНачал2, Обязательные),
маршрут (КлНачал2, КлКонеч, [КлНачал2|Хвост], ВесМаршрута2, Линия, [КлНачал2|Недоступные], Обязательные, КолОбяз2),
% нахождение следующей клетке в маршруте с переходом
маршрут (КлНачал, КлКонеч, [КлНачал, КлНачал2|Хвост], ВесМаршрута1, Линия, Недоступные, Обязательные, КолОбяз1):-
переход (КлНачал, Линия, Новая_Линия),
соседние (КлНачал, КлНачал2, Новая_Линия),
not (принадлежит (КлНачал2, Недоступные)),
маршрут (КлНачал2, КлКонеч, [КлНачал2|Хвост], ВесМаршрута2, Новая_Линия, [КлНачал2|Недоступные], Обязательные, КолОбяз1),
переход (КлНачал, Линия, Новая_Линия),
соседние (КлНачал, КлНачал2, Новая_Линия),
not (принадлежит (КлНачал2, Недоступные)),
принадлежит (КлНачал2, Обязательные),
маршрут (КлНачал2, КлКонеч, [КлНачал2|Хвост], ВесМаршрута2, Новая_Линия, [КлНачал2|Недоступные], Обязательные, КолОбяз2),
write_маршрут([Клетка], Линия): – линия (Линия, Список),
принадлежит (Клетка, Список), write(Клетка).
write_маршрут([Клетка, Клетка2|Хвост], Линия):-
write_маршрут([Клетка2|Хвост], Линия).
write_маршрут([Клетка, Клетка2|Хвост], Линия):-
переход (Клетка, Линия, Новая_Линия),
соседние (Клетка, Клетка2, Новая_Линия),
write_маршрут([Клетка2|Хвост], Новая_Линия).
ввод_назв_обяз (1, Обязательные, ВведенныеОбяз):-
write («Введите последнюю обязательную клетку:»),
not (принадлежит (Клетка, ВведенныеОбяз)),
ввод_назв_обяз (КолОбяз, Обязательные, ВведенныеОбяз):-
write («Введите обязательную клетку:»),
not (принадлежит (Клетка, ВведенныеОбяз)),
ввод_назв_обяз (КолОбяз2, Обязательные2, [Клетка|ВведенныеОбяз]),
Обязательные=[Клетка|Обязательные2],!;
write («Клетка с таким названием уже была введена»),
ввод_назв_обяз (КолОбяз, Обязательные, ВведенныеОбяз).
write («Сколько обязательных клеток Вы хотите ввести:»),
write («Необходимо ввести целое число. Пожалуйста, повторите ввод.»),
ввод_обяз (Обязательные, КолОбяз): – ввод_кол_обяз(КолОбяз), ввод_назв_обяз (КолОбяз, Обязательные, []).
run: – write («Выбор маршрута передвижения в лабиринте с посещением обязательных клеток»), nl,
write («Схему лабиринта можно найти в приложении пояснительной записки»), nl,
write («Введите название начальной клетки =»), readln(КлНачал),
write («Введите название конечной клетки =»), readln(КлКонеч),
findall (ВесМаршрута, маршрут (КлНачал, КлКонеч,_, ВесМаршрута,_, [КлНачал], Обязательные, КолОбяз), СписокВесМаршрута),
мин (ВесМаршрута, СписокВесМаршрута),
маршрут (КлНачал, КлКонеч, Маршрут, ВесМаршрута,_, [КлНачал], Обязательные, КолОбяз),
write («Оптимальный маршрут:»), nl,
write («Количество шагов:», КолСт), nl.
Схема использованного в программе лабиринта
Название: Программа выбора оптимального (наикратчайшего) маршрута перемещения в лабиринте
Раздел: Рефераты по информатике, программированию
Тип: контрольная работа
Добавлен 07:22:25 14 ноября 2010 Похожие работы
Просмотров: 70
Комментариев: 15
Оценило: 3 человек
Средний балл: 5
Оценка: неизвестно Скачать
Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.
Контрольная работа: Программа выбора оптимального (наикратчайшего) маршрута перемещения в лабиринте
Курсовая Работа На Тему Предпринимательские Риски
Курсовая работа: Современные методы подбора очковой коррекции
Сочинение Рассуждение Грамматика
Дипломная работа: Вода на Марсі
Реферат по теме Статистическое наблюдение, первоначальная обработка и представление ее данных
Реферат: История русского искусства
Дипломная работа по теме Специфика отбора детей 7-8 лет в спортивное плавание
Курсовая Работа На Тему Финансовая Система Российской Федерации
Реферат по теме Промышленность Бирмы
Контрольные Работы 5 Класс Бунимович Скачать Бесплатно
Курсовая работа по теме Выбор параметров и анализ режимов электропередачи
Реферат: Факторы межкультурной адаптации
Дипломная работа по теме Становление, развитие и современное состояние молодежной культуры 'хип-хоп'
Реферат по теме Методика преподавание темы Обыкновенные дроби в школьном курсе математики
Реферат по теме Понимание духовности в христианстве
Учебное пособие: Методические указания для студентов по прохождению практики
Русский Язык Литература Итоговое Выпускное Сочинение
Реферат: Антони ван Левенгук. Скачать бесплатно и без регистрации
Реферат: Имущество как предмет бухгалтерского учета
Дипломная работа: Єдність економічної і соціальної ефективності виробничої організації
Реферат: Основные черты мировой экономики на рубеже ХХ–ХXI веков
Доклад: Аденома предстательной железы
Реферат: Проблеми ліквідації банків