Категория
Информатика
Тип
реферат
Страницы
10 стр.
Дата
16.03.2014
Формат файла
.html — Html-документ
Архив
1006824.zip — 5.28 kb
  • programma-vybora-optimalnogo-naikratchajshego-marshruta-peremeshhenija-v-labirinte_1006824_1.html — 22.05 Kb
  • Readme_docus.me.txt — 125 Bytes
Оцените работу
Хорошо  или  Плохо


Текст работы

1. Задание

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

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

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

Для решениязадачи использовался пакет Visual Prolog 5.2 Personal Edition.

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

а) Клетка;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



Ваше мнение



CAPTCHA