Задача о прокладке экономичного пути (задача о самолете)

↑

⇐ ПредыдущаяСтр 22 из 28Следующая ⇒

Задача о прокладке пути.

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

При этом могут быть рассчитаны затраты на прокладку пути в зависимости от местности на 1 км. В этой задаче отсутствует естественная разбивка на m этапов. Один из способов разбивки:

АВ делим на m равных частей. Проводим перпендикулярную линию к отрезку AB. В качестве управления берем угол - направление движения трассы, между параллельными линиями по сравнению с отрезком АВ. .

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

Для решения методом динамического программирования на плоскости вводим решетку. Для этого каждый отрезок [0,a] и [0,b] разбиваем на некоторое количество равных отрезков и строим сеть. Каждый план будет представлять из себя некоторую ломаную. Для каждой горизонтали или вертикали отрезка этой решетки заданы положительные числа – стоимость прокладки пути по заданному отрезку. Требуется найти такой путь, чтобы суммарные затраты были минимальными. Расчет пути может быть произведен либо от А к В либо наоборот.

Будем прокладывать путь от В к А. Метод динамического программирования включает в себя инвариантное погружение:

1) сведением функции Беллмана;

2) составление и расчет значения для функции Беллмана;

3) решение уравнения Беллмана и построение О.П.

Для нашей задачи инвариантное погружение – это задача прокладки пути из любого узла решетки в В.

1 этап. Функция Беллмана – эта стоимость (мин.) прокладки пути из любого узла в В.

2 этап. Для расчета функции Беллмана мы из каждого узла решетки перебором находим наиболее экономичный путь (условно – оптимальный путь) и его минимальную стоимость. Движение производится от В по всем узлам решетки пока не попадем в А.

3 этап. Значением функции для точки А будет оптимальные расходы на прокладку пути.   

Познавательные статьи:



Алгоритмические операторы Matlab

Конструирование и порядок расчёта дорожной одежды

Исследования учёных: почему помогают молитвы?

Почему терпят неудачу многие предприниматели?