Диссертация (786272), страница 15

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 15)

Для этого опишем трисхемы движения по сетке разбиения, к которым можно свести всё множество вариантовпрокладки трасс второй подзадачи.79Исключим из рассмотрения возможность движения по диагонали сетки разбиения.Обозначим через (1 ,1 , , ) — стоимость прокладки трассы при двух возможныхнаправлениях движении по горизонтали и по вертикали. Тогда (1 ,1 , , ) =∑︁( + ),(3.17) ∈1 , ∈2 ∈3 , ∈4где 1 ∪ 2 = {1 , .

. . , }, 3 ∪ 4 = {1 , . . . , } — множества индексов, отражающих последовательность смены направлений движения прокладываемых по сетке разбиения участков; — стоимость прокладки трассы по горизонтали от точки ( , ) до точки ( + 1, ); — стоимость прокладки трассы по вертикали от точки ( , ) до точки ( , + 1).Пусть — количество участков трассы, прокладываемых в горизонтальном направлении, а — количество участков трассы с вертикальным направлением прокладки посетке разбиения, причем = − 1 , = − 1 .Используя введённые обозначения, а также минимально возможные значения стоимостей прокладки трассы по сетке разбиения по горизонтали и по вертикали (3.14) — (3.15),найдем оценку снизу для величины стоимости прокладки трассы (3.17) при двух возможныхнаправлениях движения: (1 ,1 , , ) ≥ (1 ,1 , , ) + (1 ,1 , , ),(3.18)при этом отсутствует необходимость учёта последовательности смены направлений прокладки участков трассы.Введем в рассмотрение третье направление движения — по диагонали, по направлению к конечной точке.

Тогда стоимость прокладки трассы для трёх возможных направленийдвижения по сетке разбиения определяется величиной: (1 ,1 , , ) =∑︁( + + ),(3.19) ∈1 , ∈2 , ∈3 ∈4 , ∈5 , ∈6где 1 ∪ 2 ∪ 3 = {1 , . . . , }, 4 ∪ 5 ∪ 6 = {1 , . . . , } — множества индексов, отражающих последовательность смены направлений движения по сетке разбиения прокладываемыхучастков; — стоимость прокладки трассы по горизонтали от точки ( , ) до точки ( + 1, ); — стоимость прокладки трассы по вертикали от точки ( , ) до точки ( , + 1); — стоимость прокладки трассы по диагонали от точки ( , ) до точки ( + 1, + 1).80Используя минимально возможные значения стоимостей (3.14) — (3.16), оценим снизу величину стоимости прокладки трассы по трём возможным направлениям движения посетке разбиения (1 ,1 , , ) ≥ (1 ,1 , , ) + (1 ,1 , , ) + (1 ,1 , , ),где , , — количество участков, проложенных по горизонтали, вертикали и по диагонали соответственно.Если выполняется соотношение(1 ,1 , , ) + (1 ,1 , , ) ≥ (1 ,1 , , ),то вместо последовательной прокладки участков в направлениях по горизонтали и по вертикали прокладка участков трассы осуществляется по диагонали сетки разбиения.

При этом,если ≥ , то с учётом (3.19), получаем ≥ ( − )(1 ,1 , , ) + ( + )(1 ,1 , , ),(3.20) ≥ ( − )(1 ,1 , , ) + ( + )(1 ,1 , , ).(3.21)иначеСоотношение (3.20) соответствует схеме движения по сетке разбиения по вертикали ипо диагонали, а соотношение (3.21) — по горизонтали и по диагонали. Применяя обозначенияΔΔΔΔ = − ; = + ; = − ; = + , перепишем выражения (3.20) —(3.21) в следующем виде: (1 ,1 , , ) ≥ (1 ,1 , , ) = (1 ,1 , , )+(3.22)+ (1 ,1 , , ), (1 ,1 , , ) ≥ (1 ,1 , , ) = (1 ,1 , , )+где (3.23)+ (1 ,1 , , ),— количество шагов по вертикали, — количество шагов по диагонали при двухвозможных направлениях прокладки трассы по вертикали и по диагонали; — количество шагов по горизонтали, — количество шагов по диагонали при двух возможныхнаправлениях прокладки трассы по горизонтали и по диагонали.При (1 ,1 , , ) + (1 ,1 , , ) < (1 ,1 , , ) все участки с диагональнымнаправлением прокладки трассы можно заменить на последовательную прокладку трассыпо горизонтали и по вертикали сетки разбиения, при этом (1 ,1 , , ) ≥ (1 ,1 , , ),81где (1 ,1 , , ) определено в (3.18).Соотношения (3.18), (3.22) — (3.23) показывают, что для нахождения нижней оценкистоимости прокладки трассы во второй подзадаче достаточно оценить стоимость прокладкидля трёх схем движения по сетке разбиения:1) по горизонтали и по вертикали;2) по горизонтали и по диагонали (если − 1 ≥ − 1 );3) по вертикали и по диагонали (если − 1 < − 1 ).Найдем оценку снизу стоимости прокладки трассы для трёх описанных схем движения.1.

Рассмотрим первую схему движения по сетке разбиения в направлениях по горизонтали и по вертикали:1) число шагов по горизонтали в данной схеме движения определяется как = − 1 ,(3.24) = − 1 , = 0, , 1 = 0, ;(3.25)2) число шагов по вертикали:3) стоимость прокладки трассы между точками 1 ,1 и , оценивается снизувеличиной (3.18);4) с учётом 3), суммарная стоимость работ по прокладке трассы от 1,1 до +1, +1оценивается снизу как сумма найденных значений стоимостей в каждой из подзадач: (1,1 , +1, +1 ) = ( , , +1, +1 ) + (1 ,1 , , ) + (1,1 , 1 ,1 ).(3.26)2. Рассмотрим вторую схему движения.1) Если − 1 ≥ − 1 , то движение по сетке осуществляется в направлениях погоризонтали и по диагонали:1.1) число шагов по горизонтали в данной схеме движения определяется как = − 1 − ,(3.27)821.2) число шагов по диагонали: = − 1 , = 0, , 1 = 0, ;(3.28)1.3) стоимость прокладки трассы между точками 1 ,1 и , оценивается снизувеличиной (3.23);1.4) с учётом 1.3), суммарная стоимость работ по прокладке трассы от 1,1 до +1, +1в данной схеме движения оценивается снизу как сумма найденных значения стоимостей вкаждой из подзадач: (1,1 , +1, +1 ) = ( , , +1, +1 ) + (1 ,1 , , )+(3.29)+ (1,1 , 1 ,1 );2) Если − 1 < − 1 , то движение по сетке осуществляется в направлениях повертикали и по диагонали.2.1) число шагов по вертикали в данной схеме движения определяется как = − 1 − , = 0, , 1 = 0, ,(3.30)2.2) число шагов по диагонали: = − 1 ;(3.31)2.3) стоимость прокладки трассы между точками 1 ,1 и , оценивается снизувеличиной (3.22);2.4) с учётом 2.3), суммарная стоимость работ по прокладке трассы от 1,1 до +1, +1в данной схеме движения оценивается снизу как сумма найденных значения стоимостей вкаждой из подзадач: (1,1 , +1, +1 ) = ( , , +1, +1 ) + (1 ,1 , , )+(3.32)+ (1,1 , 1 ,1 ).Для каждой конечной точки , второй подзадачи вычисляем значений стоимостей прокладки трассы по формулам (3.18), (3.22) — (3.23), считая начальной точкой каждую83из 1 ,1 , 1 = 0, .

Среди полученных значений стоимостей выбираем наименьшее. Этозначение учитывается в (3.26), (3.32), (3.29) для определения минимально возможной суммарной стоимости работ по прокладке всей трассы от точки 1,1 до +1, +1 . Полученноезначение сравнивается со значением 0 прокладки трассы, предложенной экспертом. Если0 оказывается больше, то точка , запоминается, иначе — исключается из дальнейшегорассмотрения.Для оставшихся в рассмотрении точек необходимо осуществить уточнение траектоΔрии оптимальной трассы (процесс ветвления).

С этой целью выберем − = − 1, где = 1, − 2, вместо и перейдем вновь к первой подзадаче.Процесс ветвления продолжается до шага − = 1 + 1, = 1, − 2. При решениизадачи на этом шаге получаем оптимальную трассу.Для большей наглядности запишем описанный выше алгоритм в виде следующейпоследовательности шагов.Алгоритм 3.1.1.

Выбор трассы экспертом. Экспертом осуществляется выбор траекторий 1 , 2 , . . . , , после чего определяются значения стоимости прокладки 1 , 2 , . . . , для каждой выбранной траектории. Среди выбранных траекторий определяется траектория o снаименьшей стоимостью o = min{1 , 2 , . . . , }.2. Выбираем параметр 1 с учётом условия (3.13), после чего уменьшаем размерысетки разбиения до 1 × и определяем стоимости (1,1 , 1 ,1 ) всех трасс из точки 1,1 до1 ,1 , 1 = 0, , путём применения метода динамического программирования.3. Выбираем параметр с учётом условия (3.13), после чего уменьшаем сетку разбиения до размеров × и определяем стоимость (1 ,1 , , ) всех траcc из точки ,до +1, +1 , = 0, , путём применения метода динамического программирования.1) Рассматриваем точку , , = 0, , для которой = 0.2) Определяем количество начальных точек 1 ,1 , 1 = 0, , 1 ≤ , из которыхдостижима точка , , = 0, .

Для пары точек 1 ,1 , , рассматривается редуцированная сетка разбиения для определения параметров (3.14) — (3.16). Для каждой издвух существующих оптимальных схем движения определяется количество шагов по каждому из направлений движения по формулам (3.24) — (3.25), (3.30) — (3.31), (3.27) — (3.28).Определяется минимально возможная стоимость каждой предложенной трассы согласновыражениям (3.18), (3.22), (3.23). После чего среди полученных значений осуществляется84поиск минимального значения стоимости прокладки трассы.3) Далее определяется суммарная стоимость (1,1 , +1, +1 ) прокладки всей трассыот точки 1,1 до точки +1, +1 , проходящей через точки 1 ,1 , , согласно выражениям (3.26), (3.32), (3.29).

Характеристики

Список файлов диссертации