3. Алгоритмы построения наилучших траекторий

Пусть замкнутые выпуклые множества, а шары в . В настоящем параграфе приведены два алгоритма: . Алгоритм А применим для решения задач (1.5), (2.5), алгоритм предназначен для решения задачи (1.5). Через будем обозначать для задачи (1.5), для задачи (2.5).

Алгоритм А. Алгоритм состоит в последовательном построении ломаных

шаг). Ломаная

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

где

шаг). Предположим, что построена ломаная укажем правило построения ломаной Будем двигаться от номера

к номеру (возможно обратное движение: от Найдем из условия

для задачи (2.5) и из условия

в случае задачи (1.5) и положим

Элементы определим последовательно из условий

в случае задачи (2.5) и

для задачи (1.5). И, наконец, находим из равенства

в случае задачи (2.5) и из равенства

для задачи (1.5), и полагаем

Алгоритм Применительно к задаче (1.5) еще рассмотрим один вариант алгоритма А — алгоритм в котором более полно учитывается специфика задачи (1.5). Алгоритм отличается от А тем, что

1) для любого жесткого звена элементы определяются по формулам (1.4), а в соответствии с условиями

где

2) на шаге при построении ломаной номера перебираются от при четном к и в обратном порядке: от при нечетном к.

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

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

а для номеров (если имеют место равенства

В случае требуется справедливость лишь второго (первого) из неравенств (3.10). Если ломаная достаточно близка к одному из решений, то, как легко видеть, условия (3.10), (3.11) позволяют выделить жесткое звено.

Отметим еще, что если шар, то условие (3.7) принимает вид

Аналогично записывается условие (3.8) в случае, когда является шаром.