Материал: 2426

Одновременно с заменой значения элемента массива Vdlin при выполнении условия

рассчитывается Rodтек – код текущей вершины-родителя si1 для вер-

îпри Lтек ³Vdlin(i +1,j2,k2,l2,m2).

5.4.Данный пункт алгоритма выполняется, если вершина-

преемник sj1 еще ни разу не просматривалась, что формализуется условием ï

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

По (3.141) рассчитывается Rodтек – код текущей вершиныродителя si1 для вершины-преемника sj1, который заносится в элемент массива Vrod:

Vrod(i+1,j2,k2,l2,m2)=Rodтек. (3.144)

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

Vdlin:

Vdlin(i+1,j2,k2,l2,m2)=Lтек. (3.145)

В элементе массива Vfront с индексами (i+1,j2,k2,l2,m2) сохраняется информация о том, что вершина-преемник sj1 уже просматрива-

150

лась, т.е. выполняется присваивание данному элементу единичного значения по (3.137).

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

Используя вложенные циклы по j,k,l,m, где j [1; jmax]; k [1; kmax]; l [1; lmax]; m [1; mmax], для каждого сочетания индексов (i+1), j, k, l, m проверяется выполнение условия

Vfront(i+1,j,k,l,m)=1. (3.146)

При выполнении данного условия вершины следующего за текущим ряда с одинаковыми значениями координаты x [с индексом (i+1)] закрываются, т.е. соответствующая вершина помечается как пройденная и закрытая:

Vfront(i+1,j,k,l,m)=2. (3.147)

Таким образом, помечаются не все вершины ряда с индексом (i+1), а только свободные и при этом просмотренные на текущей итерации цикла i. Вершины, занятые препятствиями, а также не вошедшие в множество проверяемых вершин в массиве Vfront, остаются непомеченными как закрытые (сохраняются старые значения соответствующих элементов). Это позволяет исключить их из рассмотрения как вершины-родители на следующей итерации цикла i.

Множество проверяемых вершин на каждой итерации i формируется в пространстве состояний объекта-груза, представляющем собой равномерную решетку линейных (x, y, z) и угловых (γ, ω) координат, по принципу развертывания-свертывания дерева поиска. Дерево поиска развертывается из единственной начальной вершины sнач по принципу рассмотрения всех возможных вершин-преемников для множества вершин, рассмотренных на предыдущей итерации i [координаты x, по условиям (3.133), (3.146), (3.147)], и свертывается в единственную конечную вершину sкон по граничным условиям (3.135). Двухмерная иллюстрация развертывания-свертывания дерева поиска (движения фронта волны) приведена на рис. 3.35.

6. После завершения всех вложенных циклов по i, j, k, l, m (прохождения фронта волны) происходит восстановление найденной оп-

151

тимальной по значению целевой функции траектории по кодам вер- шин-родителей.

6.1. В качестве первой вершины-преемника назначается sкон, для которой из массива Vrod восстанавливается код вершины-родителя:

6.2. Восстанавливаются индексы вершины-родителя si1=(i,j,k,l,m)

по коду Rodтек и индексам вершины-преемника sj1=(i2,j2,k2,l2,m2). При рассмотрении конечной вершины, с которой начинается восста-

новление траектории, i2=imax; j2=jкон; k2=kкон; l2=lкон; m2=mкон. В символах программирования с использованием операции получения це-

лочисленного остатка от деления (%) зависимости выглядят следующим образом:

С использованием традиционной математической формы записи выражения (3.150) будут иметь следующий вид:

dm=(Rodтек – Rodтек/10 ∙10); Rodтек= Rodтек – dm; dl=(Rodтек – Rodтек/100 ∙100)/10; Rodтек= Rodтек – dl∙10; dk=(Rodтек – Rodтек/1000 ∙1000)/100; Rodтек= Rodтек – dk∙100;

Последовательность действий пункта 6.2 алгоритма выполняется в цикле imax раз. В результате формируется траектория S* из точек вида (3.50) с использованием зависимостей (3.100).

152

Рис. 3.36. Блок-схема модифицированного волнового алгоритма для пяти учитываемых обобщенных координат груза (продолжение)

154