Материал: 2426

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

[74, 215, 219, 227]: O(b1+ëс*/ε û ) (c* – стоимость оптимального решения, ε – некоторое положительное значение). Это объясняется, во-первых, вычислительными издержками на поддержание приоритетной очереди узлов, во-вторых, тем, что долго может выполняться проверка больших деревьев, состоящих из множества дуг малой стоимости, но не содержащих оптимальных путей [74, 215, 219, 227].

Существуют также алгоритмы поиска на графах, основанные на различных модификациях волнового алгоритма, которые относятся к информированным стратегиям: A* (Aстар, направленный волновой алгоритм), RBFS и SMA* [74, 224, 232, 234, 241]. Информированные алгоритмы считаются более эффективными, чем неинформированный поиск (классический волновой алгоритм), поскольку рассматриваются не все узлы графа, а только в первую очередь наиболее перспективные (в направлении к цели). Однако при применении этих алгоритмов используется эвристическая функция h(n), для которой необходим ее правильный подбор для конкретной задачи, что представляет собой определенную сложность. Кроме того, в описанных эвристических алгоритмах также используются приоритетные очереди узлов, т.е. появляются издержки на сортировку, значительно возрастающие при увеличении размеров очереди. Причем сортировку необходимо проводить при рассмотрении каждой новой вершины графа. В случае, если время на сортировку сравнимо с временем обработки отдельной вершины графа или превышает его, данный фактор становится существенным недостатком.

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

Все перечисленные соображения обуславливают целесообразность разработки методики перемещения груза, положение которого

145

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

Описание модификации направленного волнового алгоритма перемещения груза, положение которого определяют 3 линейные и 2 угловые обобщенные координаты [60]. Предлагаемый модифицирован-

ный волновой алгоритм отличается отсутствием приоритетной очереди узлов и соответственно издержек на сортировку узлов. Кроме того, данная модификация, так же, как и A*, являясь направленным волновым алгоритмом, в то же время не использует эвристическую функцию. Эвристика предлагаемого алгоритма задана неявно и заключается в расположении оси X0 при постановке задачи (см. раздел 3.1), а также в более высоком иерархическом уровне цикла изменения координаты x груза по отношению к прочим координатам при распространении фронта волны (цикл, меняющий координату x, будет самым внешним в структуре вложенных циклов). Граф также задается неявно в виде состояний-преемников на равномерной решетке, т.е. не тратятся ресурсы на описание графа в виде матрицы смежности, проверку пересечений и т.д.

Алгоритм заключается в выполнении следующей последовательности шагов [60]:

1. Задание численных значений исходных данных: sнач=(xн0, yн0,

zн0, γн0, ωн0); sкон=(xк0, yк0, zк0, γк0, ωк0); { Rig }; imax; jmax; kmax; lmax; mmax;

[YПР]; cγω; u; δopt; lзап_г; lзап_в.

Параметры соответствуют описанным при постановке задачи в разделе 3.1.

2. По методике, изложенной в разделе 3.4, формируется массив [Ymin] гиперповерхности минимальных значений вертикальных координат условного центра груза с учетом его угловых координат:

Ymin(i,k,l,m), i [1; imax]; k [1; kmax]; l [1; lmax]; m [1; mmax].

3. Используя вложенные циклы по i, j, k, l, m, определяющие x, y, z, γ, ω соответственно, рассматривают всевозможные сочетания координат груза x, y, z, γ и ω на дискретной равномерной сетке, и для каждого сочетания указанных координат в 5-мерном массиве Vfront сохраняют информацию о наличии/отсутствии препятствия в текущем узле:

где y=j∙Δl; i [1; imax]; j [1; jmax]; k [1; kmax]; l [1; lmax]; m [1; mmax].

Значение (–1) элемента массива Vfront соответствует наличию препятствия в узле, 0 – отсутствию препятствия.

Одновременно происходит инициализация двух других 5-мерных массивов (определения узла-родителя Vrod и значений целевой функции перемещения от начальной точки Vdlin):

Элементы массива Vfront могут принимать следующие значения: (–1) – узел занят препятствием (непроходим); 0 – узел свободен, не пройден и ни разу не просматривался; 1 – узел просматривался, но еще не пройден; 2 – узел пройден (окончательно закрыт).

4. Начальная точка положения груза на равномерной решетке в массиве Vfront помечается как пройденная:

5. Запускается распространение волны из начальной точки. Ис-

пользуются вложенные циклы по i, j, k, l, m, где i [1; (imax–1)]; j [1; jmax]; k [1; kmax]; l [1; lmax]; m [1; mmax].

5.1. Для каждого сочетания индексов j, k, l, m на текущей итерации i проверяется выполнение условия

Vfront(i,j,k,l,m)=2. (3.133)

При выполнении данного равенства выполняется п. 5.2, в противном случае рассматривается следующее сочетание индексов (j,k,l,m), и вновь выполняется п. 5.1. Текущее сочетание всех индексов (i, j, k, l, m) для краткости названо текущей вершиной si1. После завершения вложенных циклов по (j,k,l,m), т.е. перед началом следующей итерации цикла по i, выполняется п. 5.5 алгоритма.

Условие (3.133) позволяет алгоритму пропускать непроверяемые вершины при развертывании дерева поиска (рис. 3.35). Непроверяемые вершины возникают вследствие ограниченного количества вер- шин-преемников у каждой вершины и направлений преемственности. На каждой итерации цикла i происходит увеличение диапазонных значений индексов всех прочих координат (j,k,l,m), максимально на 2

147

единицы, до тех пор, пока диапазонные значения не достигнут преде-

лов исходной сетки j [1; jmax]; k [1; kmax]; l [1; lmax]; m [1; mmax].

i=imax

Направление

движения

фронта

волны

– свободные непроверяемые вершины;

– свободные проверяемые вершины;

– занятые препятствиями непроверяемые вершины;

– направления открытия вершин алгоритмом

Рис. 3.35. Иллюстрация развертывания-свертывания дерева поиска модифицированного волнового алгоритма (двухмерный аналог)

Обозначим диапазонные значения индексов jдmax, jдmin, kдmax, kдmin, lдmax, lдmin, mдmax, mдmin. Для сокращения времени работы волнового алгоритма целесообразно задать условия, позволяющие пропускать все

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

jдmin(i)=i–(imax–jmax); jдmax(i)=(imax+jmax)–i; kдmin(i)=i–(imax–kmax); kдmax(i)=(imax+kmax)–i;

lдmin(i)=i–(imax–lmax); lдmax(i)=(imax+lmax)–i; (3.134)

mдmin(i)=i–(imax–mmax); mдmax(i)=(imax+mmax)–i.

Происходит коррекция пределов варьирования индексов j, k, l, m:

j [max(1; jдmin); min(jдmax; jmax)]; k [max(1; kдmin); min(kдmax; kmax)]; l [max(1; lдmin); min(lдmax; lmax)]; m [max(1; mдmin).

5.2. Для каждой текущей вершины si1=(i, j, k, l, m) рассматривается ограниченная область-гиперкуб с центром в точке (j, k, l, m) и постоянным значением индекса (i+1). Для этого индексы j2, k2, l2, m2 варьируются в следующих диапазонах (область гиперкуба):

То есть просматриваются все состояния-преемники для текущего состояния груза в пространстве (см. рис. 3.18).

Значения индексов j2, k2, l2, m2, варьируемые по (3.136), проверяются на выполнение условия невыхода за границы диапазонов исходной сетки (3.135) и при необходимости корректируются по зависимостям, аналогичным (3.58).

Для каждого сочетания индексов (i+1), j2, k2, l2, m2 проверяется выполнение условия

Vfront(i+1,j2,k2,l2,m2)=1. (3.137)

При выполнении данного условия, т.е. если вершина-преемник, находящаяся впереди текущей, уже просматривалась, выполняется п. 5.3, в противном случае – п. 5.4.

5.3. Рассчитывается стоимость перемещения от начальной вершины до вершины-преемника sj1=(i+1,j2,k2,l2,m2) через текущую вершину si1=(i,j,k,l,m):

где Li1,j1 – значение целевой функции (СВД) между двумя вершинами si1 и sj1, вычисляемое по (3.18).

Если стоимость перемещения от начальной вершины до верши- ны-преемника sj1=(i+1,j2,k2,l2,m2) через текущую вершину si1=(i,j,k,l,m) меньше, чем Vdlin(i+1,j2,k2,l2,m2) – рассчитанная ранее стоимость перемещения в вершину sj1 через некоторую другую вершину, то вновь рассчитанная стоимость заносится в элемент массива Vdlin(i+1,j2,k2,l2,m2), заменяя бывшее до этого значение данного элемента: