Решение логистических задач методом поиска
Алгоритмы решения задачи построения маршрута из одной заданной точки в другую. Построение графа маршрута, его сравнение с неинформированным поиском. Алгоритм поиска в ширину, в глубину, с итерационным заглублением. Двунаправленный и информированный поиск.
| Рубрика | Транспорт |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 30.11.2014 |
| Размер файла | 329,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://allbest.ru
1. Изучение алгоритмов поиска
Цель задания: Исследование алгоритмов решения задач методом поиска.
Описание предметной области. Имеется транспортная сеть, связывающая города СНГ. Связи являются двусторонними, т.е. допускают движение в обоих направлениях. Необходимо проложить маршрут из одной заданной точки в другую.
Этап 1. Неинформированный поиск. На этом этапе известна только топология связей между городами. Выполнить:
1) поиск в ширину;
2) поиск в глубину;
3) поиск с ограничением глубины;
4) поиск с итеративным углублением;
5) двунаправленный поиск.
Отобразить движение по дереву на его графе с указанием сложности каждого вида поиска. Сделать выводы.
Этап 2. Информированный поиск. Воспользовавшись информацией о протяженности связей от текущего узла, выполнить:
1) жадный поиск по первому наилучшему соответствию;
2) затем, используя информацию о расстоянии до цели по прямой от каждого узла, выполнить поиск методом минимизации суммарной оценки
Отобразить на графе выбранный маршрут и сравнить его сложность с неинформированным поиском. Сделать выводы.
Казань-Таллин
Исходный вариант (рис.1):
Рис.1
Алгоритм поиска в ширину.
Поиск в ширину - это простая стратегия, в которой в начале развертывается корневой узел, затем все преемники корневого узла, после этого развертываются преемники этих преемников и т.д. Алгоритм обхода графа в ширину находит путь, который содержит наименьшее.
Рис.2 - Алгоритм поиска в ширину
При обходе в ширину, узлы графа, равноудаленные от начальной вершины обрабатываются одним шагом алгоритма. Сначала просматриваются вершины: Казань- (Москва, Уфа), затем вершины-потомки этих вершин: Москва-(Минск, Орел, Донецк, Санкт-Петербург, Нижний Новгород); Уфа-Самара; так как не найден целевой узел, поиск осуществляется дальше. В конечном итоге, придем к решению (Казань-Москва-Санкт-Петербург-Рига-Таллин).
Общее число выработанных узлов (временная сложность) равно O(), где b -- коэффициент ветвления, d -- глубина поиска.
Временная сложность(О) =
Вывод: Такая стратегия не всегда является оптимальной; чтобы понять, с чем это связано, необходимо определить, какое количество времени и какой объем памяти требуются для выполнения поиска.
Поиск в ширину гарантирует нахождение решения, если оно существует, однако имеет большую сложность, так как необходимо запоминать все пройденные вершины.
2.Алгоритм поиска в глубину
Path = [ (kazan, moskva), (moskva, nizhnovgorod), (nizhnovgorod, vitebsk), (vitebsk, brest), (brest, vilnus), (vilnus, kaliningrad), (kaliningrad, spb), (spb, riga), (riga, tallin)]
Рисунок 3 Этапы поиска решения обходом графа в глубину
На каждом шаге поиска в глубину алгоритм выбирает новую вершину, смежную с текущей и продолжает поиск уже из нее. Такое «погружение» продолжается до тех пор, пока не будет найдена вершина, смежная с конечной или алгоритм не зайдет в тупик. Если алгоритм на рис 3. выберет узел «Уфа», то он зайдет в тупик, так как из Уфы ветвление только в Самару. Значит, алгоритм он выберет новую вершину, Москва, далее он будет «углубляться» по данной ветке в Нижний Новгород, а из Нижнего Новгорода есть 1 вариант движения: Витебск. Алгоритм выберет этот путь и будет продолжать путь по ней, пока не дойдет до конечного узла или не зайдет в тупик.
Временная сложность(О) = =
Временная сложность(О) = =
Временная сложность(О) = =
Вывод: Может быть сделан неправильный выбор и переход в тупиковую ситуацию, связанную с прохождением вниз по очень длинному (или даже бесконечному) пути, при том, что другой вариант мог бы привести к решению, находящемуся недалеко от корня дерева поиска. Имеет скромные потребности в памяти(bm).
Поиск с ограничением глубины
Рисунок 4 - Этапы нахождения решения поиском с ограничением глубины.
Решение не найдено, так как L<d.
Зададим L=4. Это значит, что поиск на глубине больше, чем 4 не осуществляется.
Рисунок 5 - Этапы нахождения решения поиском с ограничением глубины.
Применение предела глубины позволяет решить проблему бесконечного пути. К сожалению, в этом подходе также вводится дополнительный источник неполноты, если будет выбрано значение L<d, иными словами, если самая поверхностная цель выходит за пределы глубины. (Такая ситуация вполне вероятна, если значение d неизвестно.)
Кроме того, поиск с ограничением глубины будет неоптимальным при выборе значения L>d. Его временная сложность равна O(bL), а пространственная сложность -- O(bL).
Временная сложность: O()=
Вывод: позволяет решить проблему бесконечного пути.
3.Поиск с итерационным заглублением
Итак, зададим значение максимальной глубины последовательно: глубина 1 (рис. 6 а) - решений нет, глубина 2-решений нет (рис. 6 б), глубина 3-решений нет (рис. 6 в), глубина 4-решение найдено (рис. 6 г).
Рис.6
Вывод: предпочтительный метод неинформированного поиска при тех условиях, когда имеется большое пространство поиска, а глубина решения неизвестна.
4.Двунаправленный поиск
Рисунок 7 - Этапы нахождения решения двунаправленным поиском
Один поиск запускается с начального узла, другой-с конечного. Задача завершается, когда оба находят общий узел.
Вывод: Нужна память для хранения дерева поиска для того, чтобы можно было выполнить проверку принадлежности листа другому дереву. Общего способа эффективного решения такой проблемы не существует.
Path = [ (kazan, moskva), (moskva, nizhnovgorod), (nizhnovgorod, vitebsk), (vitebsk, brest), (brest, vilnus), (vilnus, kaliningrad), (kaliningrad, spb), (spb, riga), (riga, tallin)] глубину
Path = [ (kazan, moskva), (moskva, spb), (spb, riga), (riga, tallin)]. Ширина
5. Информированный поиск
1) Жадный поиск по первому наилучшему соответствию;
При жадном поиске по первому наилучшему совпадению предпринимаются попытки развертывания узла, который рассматривается как ближайший к цели на том основании, что он со всей вероятностью должен быстро привести к решению. Таким образом, при этом поиске оценка узлов производится с использованием только эвристической функции: f(n) = h(n).
Рисунок 8 - Этапы нахождения решения жадным поиском по первому наилучшему соответствию.
маршрут поиск граф
Вывод: Он не является оптимальным, к тому же он - не полный (поскольку способен отправиться по бесконечному пути, да так и не вернуться, чтобы опробовать другие возможности).
Размещено на Allbest.ru
...Подобные документы
Вид сетевой транспортной задачи. Алгоритм решения: построение начального базисного сетевого потока, поиск потенциалов, проверка оптимальности, добавление дуг, поиск цикла, построение потока, формирование множества дуг. Графическое представление задачи.
презентация [266,8 K], добавлен 07.03.2013Доставка экспортных и импортных грузов. Размещение его в кузове транспортного средства. Требования к креплению. Устройства для контроля режима труда и отдыха водителя. Определение маршрута доставки груза. Технико-эксплуатационные показатели маршрута.
курсовая работа [2,6 M], добавлен 22.12.2014Обоснование выбора поставщика, маршрута доставки. Характеристика проектной ситуации. Формирование блока исходных данных. Выбор поставщика и маршрута. Определение оптимального маршрута перевозки груза по наземному участку, типа автотранспортного средства.
курсовая работа [141,5 K], добавлен 12.02.2009Определение маршрута доставки груза. Упаковка и размещение груза в кузове транспортного средства. Расчет технико-эксплуатационных показателей маршрута. Устройства для контроля режима труда и отдыха водителя. Расчет фактических нагрузок на оси автопоезда.
курсовая работа [1,1 M], добавлен 15.01.2013Волго-Донской водный путь. Схема навигационного оборудования участка маршрута. Минимальные габариты судового хода на маршруте. Шлюзы и подмостовые габариты. Оценка возможности прохождения суднами маршрута в заданных гидрометеорологических условиях.
курсовая работа [383,5 K], добавлен 17.07.2012Создание плана полета или маршрута. Редактирование плана полета или маршрута. Подтверждение и введение местоположения самолета, даты и времени. Путевые точки по которым самолет будет лететь в действительности. Стандартная схема вылета по приборам.
учебное пособие [1,0 M], добавлен 21.08.2013Экономическое сравнение логистических схем перевозки груза различными видами транспорта по маршруту Гомель – Нижний Новгород. Определение маршрута и составляющих затрат. Основной перечень документов для прохождения пограничного и таможенного контроля.
дипломная работа [5,7 M], добавлен 26.08.2012Составление и исследование различных вариантов транспортного маршрута движения из дома на работу. Характеристика субъектов, объектов и факторов ограничения. Анализ событий и работ. Построение сетевого графика, расчет его параметров и оптимизация.
курсовая работа [818,1 K], добавлен 15.04.2014Изображение схемы автомобильного маршрута доставки грузов. Разработка маршрута доставки грузов в виде схемы маршрута на карте, перечня пунктов следования, таблицы протяженностей участков по территории стран с разбивкой на груженый и порожний пробеги.
практическая работа [721,2 K], добавлен 20.11.2014Обзор существующих методов и подходов к планированию групповых действий. Разработка модели одиночных и групповых действий беспилотного летающего аппарата. Создание программы и ее экономическая целесообразность. Модели качества процессов конструирования.
дипломная работа [2,2 M], добавлен 07.02.2013Схема и описание маршрута автобуса. Расчет скоростей по его участкам. Расстояние между остановочными пунктами и распределение пассажиропотока. Определение типов и количества автобусов. Организация мероприятий по улучшению работы городского транспорта.
курсовая работа [704,2 K], добавлен 03.03.2015Функции пассажирского автомобильного транспорта. Обеспечение удовлетворения потребностей населения в перевозках, качества обслуживания и эффективного использования подвижного состава. Снижение транспортных затрат. Разработка автобусного маршрута.
дипломная работа [354,9 K], добавлен 21.03.2012Характеристика маршрута автобуса. Нормирование скоростей движения, расчет автобусо-смен, пробега, количества рейсов и оборотов. Анализ распределения пассажиропотока по участкам маршрута. Выбор типа подвижного состава, его характеристика и экипировка.
курсовая работа [1,3 M], добавлен 23.01.2014Теоретические аспекты обоснования автобусного маршрута общественного транспорта. Особенности перевозок в городах, колебания числа перевозимых пассажиров по времени суток. Применение эффективных систем организации движения на междугородных маршрутах.
дипломная работа [1,1 M], добавлен 15.01.2016Упаковка и размещение груза в кузове транспортного средства. Технико-эксплуатационные характеристики АТС. Расчет осевых нагрузок. Устройства для контроля режима труда и отдыха водителя. Описание тахографа KIENZLE 1324. Определение маршрута доставки груза.
курсовая работа [3,3 M], добавлен 02.03.2011Подбор навигационных морских карт, руководств и пособий по "Каталогу". Порядок получения корректурных документов на судне. Выбор маршрута плавания. Гидрометеорологические особенности перехода. Расчет допустимости точности плавания по этапам маршрута.
курсовая работа [1,3 M], добавлен 13.08.2014Предварительная прокладка маршрута. Расчет безопасных высот, топлива и взлетной массы, навигационных элементов на участках маршрута. Порядок и принципы выполнения полета, предъявляемые к нему требования и процедуры. Особые случаи при совершении полета.
курсовая работа [3,2 M], добавлен 26.10.2014Анализ разработки маршрута движения между пунктами перевозки пассажиров, схемы маршрута. Определение времени оборота автобуса на маршруте, требований к подвижному составу. Расчет технико-экономических показателей работы автобусов, выручки от перевозок.
курсовая работа [592,3 K], добавлен 19.12.2011Использование математических методов линейного программирования для решения логистических задач. Алгоритм разработки оптимальных маршрутов движения транспортных перевозок. Расчет средней стоимости и методы снижения затрат доставки продукции на склады.
курсовая работа [373,1 K], добавлен 21.01.2015Параметры грузового автомобиля-тягача и полуприцепа. Расчет длины и массы автопоезда. Перевозка грузов в экспортном и импортном направлениях. Способ укрупнения грузового места. Расчет транспортных эксплуатационных показателей для автомобильного маршрута.
курсовая работа [1,6 M], добавлен 18.01.2013
