Аналитический обзор существующих методов и подходов к планированию групповых действий

Информация » Разработка алгоритмов поиска оптимального маршрута для БЛА при наблюдении им подвижных наземных объектов » Аналитический обзор существующих методов и подходов к планированию групповых действий

Страница 3

При решении задач с помощью динамического программирования необходимо проделать три шага:

Разбиение задачи на подзадачи меньшего размера.

Нахождение решения подзадач рекурсивно, проделывая этот же алгоритм.

Использование полученного решения подзадач для конструирования решения глобальной задачи.

При этом каждая подзадача, в отличие, например, от метода полного перебора, решается только один раз и запоминается в специальной таблице. Значения из этой таблицы в дальнейшем используются при решении задач более высокого уровня.

При решении задачи поиска оптимального маршрута методом динамического программирования довольно часто используется алгоритм Дейкстры. Принцип работы этого алгоритма заключается в том, что каждый пункт маршрута ассоциируется с вершиной графа. Каждой вершине этого графа сопоставляется метка, значением которой является минимальное известное расстояние от начальной вершины до текущей. [2]

Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. Пусть требуется найти расстояния от 1-й вершины до всех остальных.

Рисунок 1.1.7 Представление задачи в виде графа

Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» – длина пути. Рядом с каждой вершиной красным обозначена метка – длина кратчайшего пути в эту вершину из вершины 1.

Рисунок 1.1.8 Введение меток для каждой вершины

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Первый по очереди сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7.

Рисунок 1.1.9

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины – 3-й и 6-й.

Рисунок 1.1.10

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.

Первый (по порядку) сосед вершины 2 – вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 – вершина 3. Если идти в неё через 2, то длина такого пути будет = 7 + 10 = 17. Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

Рисунок 1.1.11

Ещё один сосед вершины 2 – вершина 4. Если идти в неё через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = 7 + 15 = 22. Поскольку 22<\infty, устанавливаем метку вершины 4 равной 22.

Рисунок 1.1.12

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.

Рисунок 1.1.13

Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

Рисунок 1.1.14

Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин (Это будут по порядку 6, 4 и 5).

Страницы: 1 2 3 4 5 6

Похожие статьи:

Анализ развития железных дорог России 1990-2005 гг
Анализ работы железных дорог России Из графиков видно начиная с 1990 г тепловозная и электрические виды тяги имеют примерно равный % показатель (порядка 40-50%) вплоть до сегодняшнего дня. На протяжении последних 15 лет он очень стабилен. Что касается грузооборота, то начиная с1990 г (2500 млрд ткм ...

Передаточное число главной передачи автомобиля
Скорость движения автомобиля выражаем через число оборотов в минуту двигателя n: , м/с (6) где – диаметр качения колеса, м; – передаточное число главной передачи; – передаточное число коробки передач. Значение определяем из условия движения автомобиля с заданной максимальной скоростью на прямой пер ...

Основные неисправности и способы их устранения
Отцепку пассажирского вагона и постановку его на ТО–3 и текущий отцепочный ремонт (ТР) производят после составления уведомления формы ВУ–23 осмотрщиком вагонов ПТО станции Пенза–1. Уведомление составляется в трёх экземплярах, выдаётся ДСП станции Пенза–1, и бригадиру (мастеру) ЦОРПВ. На каждый ваго ...

Навигация

Copyright © 2019 - All Rights Reserved - www.localtransport.ru