Материал: Sb97309

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

–плоскость;

–трехмерная поверхность;

–трехмерное пространство.

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

z f x, y ,

где x, y – координаты точки пространства в декартовой плоскости; z – высота (глубина), определяемая координатами x, y.

Таким образом, математическая модель для поставленной задачи включает:

–описание неориентированного графа;

–описание среды движения;

–порядок определения весов (длин) ребер графа;

–описание графа с учетом длин.

Данная задача даже с учетом введенных упрощений может найти применение для прикладных задач разного характера. Вычисление длин ребер может быть сведено к расчету метрических расстояний только в том случае, когда среда задана однородной плоскостью без ограничений. Если, например, представить, что вершины графа соответствуют населенным пунктам на географической карте, то расчет длин сведется к вычислению криволинейных интегралов, соответствующих соединяющим пункты дорогам. Однако общая постановка задачи и методы решения от этого не изменятся.

Средством математического описания графов с взвешенными ребрами служат матрицы весов (длин), похожие по структуре на матрицы смежности, но имеющие веса в качестве элементов. Элементы матрицы длин вычисляются следующим образом:

6

где aij – элементы матрицы смежности. Для графов на рис. 1.1 матрицы имеют вид

где L1 и L2 – матрицы длин для графов на рис. 1.1, а и б соответственно.

Уточнение математической модели. Простые математические модели описывают идеализированное поведение процессов и систем. Для учета реальных факторов, влияющих на поведение объекта, модель уточняют, добавляя различные физические эффекты.

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

В данной задаче полагаем, что время подзарядки аккумуляторов одинаковое для всех пунктов и не зависит от текущего состояния аккумулятора. Можно далее уточнять модель: ввести подзарядку с учетом разрядки или задавать разное время подзарядки на разных пунктах. Правда, в последнем случае придется отказаться от метрических весов графа и рассчитывать веса ребер пропорционально затраченному времени на путь и подзарядку.

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

–скорость подвижного объекта;

–время работы аккумулятора;

7

–время подзарядки аккумулятора;

–координаты начальной и конечной точек объекта;

–координаты промежуточных точек – пунктов подзарядки.

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

2. АЛГОРИТМЫ ПОИСКА ОПТИМАЛЬНОЙ ТРАЕКТОРИИ

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

–алгоритм Форда–Беллмана;

–алгоритм Дейкстры;

–алгоритм Флойда.

Существуют и другие алгоритмы, но они, как правило, представляют собой модифицированные варианты вышеприведенных.

2.1. Алгоритм Форда–Беллмана

Алгоритм Форда–Беллмана основан на теореме, согласно которой любой участок минимального пути, соединяющий некоторые вершины графа, представляет минимальный путь между этими вершинами. Алгоритм предполагает вычисление всех минимальных путей из начальной вершины.

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

1. Определить для каждой вершины набор величин ik , означающих длину пути от 1-й до і-й вершины, состоящего не более чем из k рeбeр. Набор формируется по правилу

где k – число ребeр; n – число вершин.

Величины ik можно представить в виде квадратной матрицы . Если значение in1 отлично от , значит, оно равно длине минимального пути в вершину і, в противном случае данная вершина недостижима (граф несвязный).

8

2. Определить последовательность ребер, приводящих из 1-й в і-ю вер-

шину за путь ik . Для этого нужно определить номера i1, i2, , ik , для которых выполняются соотношения

Для графов, приведенных на рис. 1.1, по алгоритму Форда–Беллмана матрицы минимальных путей имеют вид

Для графа, приведенного на рис. 1.1, а, минимальный путь до любой вершины достигается максимум за три ребра. По формулам (1.3) легко вос-

искомый минимальный путь имеет вид 1–3–5–6. Длина минимального пути равна 9.

Минимальный путь для графа на рис. 1.1, б содержит 5 ребер. Аналогично (1.3) можно восстановить в обратном порядке искомую последовательность вершин 1–2–3–4–5–6, длина минимального пути равна 10.

2.2. Алгоритм Дейкстры

Алгоритм, предложенный в 1959 г. Дейкстрой, считается одним из наиболее эффективных алгоритмов решения задачи нахождения в графе минимальных путей от начальной вершины до всех остальных при положительных длинах дуг.

9

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

Для реализации алгоритма Дейкстры требуется итерационно сформировать два вектора: вектор минимальных путей D и вектор индексов учтенных

где index – индекс минимального элемента вектора D j , не считая элементов, индексы которых уже присутствуют в векторе Ind; n – число вершин графа.

Если в векторе D j есть несколько элементов с минимальными значениями, нужно выбрать наименьший индекс.

Элементы вектора din содержат длину минимального пути от первой вершины до i-й. Если в векторе остались элементы со значением бесконечности, значит, граф несвязный и вершины с соответствующим индексом недостижимы.

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

матрицы Λ алгоритма Форда–Беллмана идентичен вектору D n алгоритма Дейкстры.

10