Динамическое программирование (стр. 6 из 10)

Определим основные положения алгоритма Литтла (АЛ) построения его как метода ветвей и границ. 1) Способ расширения ОДР.

Для расширения исходной области ограничений X опускается ограничение замкнутости маршрута. В результате получим область ограничения в задаче о назначении. В качестве матрицы затрат применяется матрица рассмотренной задачи о КВ, приведенная по строкам и столбцам C⁽⁰⁾C'' . 2) Правила ветвления.

Принцип деления для каждого из подмножеств ^X_r^{( k)} , r 0, ^r_k следующий: фиксируется дуга ( ⁱ₀, ^j₀) наименьшей длины. По этой дуге исходное множество ГК разбивается на 2 подмножества: 1) ^X_i⁽₀^k_j0⁾ , составленное из ГК, содержащих дугу ( ⁱ₀, ^j₀) ; 2) ^X_i⁽₀^k_j0⁾ , составленное из ГК, не содержащих дугу ( ⁱ₀, ^j₀) . Требование включения или не включения ⁱ₀, ^j₀ в подмножество ГК реализуется путем соответствующих преобразований матрица, рассмотренной для подмножеств ^X_r^{( k)}, r 0, ^r_k .

3) Правила вычисления границ (оценок)

Оценкой снизу на X ⁽⁰⁾ является константа приведения исходной матрицы расширений C .

Действительно, не сложно показать, что длина пути на C равна длине пути на C" (матрица, приведенная по строкам и столбцам) с константой приведения.

Поэтому, отбрасывая длину пути на C" получаем нижнюю границу длин ГК на X ⁽⁰⁾ m( X ⁰ ) . В качестве оценки снизу подмножества ^X_r берется сумма оценки исходной для ^X_r^k множества – пусть это ^X_r^{k 1} и константа приведения матрицы расширений, соответствующей подмножеству ^X_r^k m ^X_r^k и трансформированной с учетом требования замкнутости мар _шрута: m ^X_r^k m ^X_r^{k 1 m}_r^k , r 1, ^r_k .

Для контроля некоторого состояния маршрута дополнительно вводятся множества ^P_r ^k , ^P_r ^k , r 1, ^r_k соответственно множество дуг входящих и не входящих в маршрут по ветви r шага k .

Учитывая факт, что АЛ использует специальный математический аппарат, приведем для него детальное описание схемы ветвей и границ с интерпретацией действий в терминах теории графов.

1.3.4 Схема алгоритма Литтла

1) Итерация K 0

А: на X ⁰ по исходной матрице расстояний ищется нижняя граница всех ГК как константа приведения n n

матрицы C: m ⁰ min C _ij min C' _ij или m v , где C' -матрица, приведенная

i 1 ^j j 1 ⁱ

по строкам.

Б: Прежде чем перейти к шагу K 1 по C" определяется дуга разбиения 1-го наша ⁱ₀, ^j₀ ¹ .

При выборе ⁱ₀ , ^j₀ ¹ логика размышлений такова: нужно стремиться к тому, чтобы множество ГК, включающее дугу Xi0 1 j0 содержало оптимальный контур, а Xi0 1 j0 не содержало. Поэтому в Xi0 j0 нужно включать дуги матрицы C" с нулевым расстоянием. Одновременно в ^X_i0¹_j0 должны оставаться дуги с наибольшим расстоянием.

Последнее требование формализуется следующим образом: по определению, ^X_i0¹_j0 не содержит дугу ⁱ₀ , ^j₀ , т.е. для любого ГК путь из ⁱ₀ приводит в любую j ^j₀ , а в ^j₀ приводит из i ⁱ₀ . При этом длина дуги пути будет не меньше, чем так называемая степень нулевого элемента: ij io j i i0 ij0 . Здесь R 0 - множество дуг матрицы C , имеющих нулевое рас min C min C , i, j

j j0

стояние.

Затем, среди ij , i, j R ⁰ выбирается дуга ⁱ₀ , ^j₀ ¹ так, чтобы расстояние i₀ j₀ было наибольшим, т.е. i0 , j0 1 argmax ij , i, j R 0 . i, j

Получив дугу разбиения формируем подмножество дуг, составляющих промежуточные маршруты по ветвям r 1, r 2 шага k 1 : i0 , j0 P11 , P21 , r 2

P11 i0 , j0 1 , P11 ,

P21 , P21 i0 , j0 1

2) Итерация K 1

А: разбиваем X ⁰ по ⁱ₀ , ^j₀ ¹ на 2 подмножества ^X_i0¹_j0, ^X_i0¹_j0 .

Подмножество ^X_i0¹_j0 получается из X ⁰ сужением области за счет введения дополнительных условий:

-

запрещается повтор перехода из ⁱ₀ в ^j₀ , переходы из ⁱ₀ в j ^j₀, переходы из ^j₀ в i ⁱ₀ , - запрещается обратный переход из ^j₀ в ⁱ₀ .

Чтобы это формализовать матрица C C" преобразуется в матрицу первого шага ^C_{i0 j0} следующим образом:

-

в C строки ⁱ₀ и столбец ^j₀ опускаются, тем самым реализуется первая группа условий; - элемент C (вторая группа).

Подмножество ^X_i0 j₀ получается из X ⁰ запретом перехода ⁱ₀ , ^j₀ ¹ , т.е. ^C_i0j₀ : . На каждом подмножестве вычисляется нижняя граница: m ^X_i0¹_j0 m ^{0 m}_i0¹_j0, m ^X_i0¹_j0 m ⁰ _i0 j₀ .

Примечание. В качестве ^m_i0^k_j0 значения i₀ j₀ значительно сокращается объем вычислений.

Полученная информация о ветвях, границах и множествах заносится на дерево ветвлений.

Б: по меньшему значению нижней границы находим перспективное для ветвления подмножество. По определению дуги разбиения 1-го шага, им является ^X_{i0 j0} , по матрице ему соответствующей приведенной по строкам и столбцам находим дугу разбиения 2-го шага ⁱ₀ , ^j₀ ² .