Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 178

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

 

19.3. АЛГОРИТМ ГРУППОВОЙ

МИНИМИЗАЦИИ

 

 

419

пометки элемента g6

снова является 3. Это означает, что t (g3)

2.

Возвращаясь назад,

получаем g6 —

= ft и видим, что второй

компонейтой пометки элемента

g3 является 3 и, следовательно,

* (# з)^ '3 .

Возвращаясь

назад,

получаем

g3 — g3 =

0-

Таким

образом, искомое представление

имеет

вид

gt — 3g 3 +

g2,

а

его

стоимость,

являющаяся

первой

компонентой пометки

элемента

g1 , равна 9.

Обозначил! множество групповых элементов с постоянными пометками через Р, а множество групповых элементов с временныл!и пометками через Т 1). Мы будем использовать выражение «кол1бинирование групповых элементов для получения группового

элелюнта g0», имея в виду «нахождение различных представлений Hgt (g) — go со стоимостью, равной 2с (g) t (g)».

Л емма 19.3. Комбинация групповых элементов из Т или ком­ бинация групповых элементов из Р с однимили более элементами из Т не может дать группового элемента gr, такого, что

с(gr) < min c(g) — c (gs).

Доказательство. Комбинация элементов из Т или комбина­

ция элементов из Р с одним или более элементами из Т содержит по меныпей мере один элемент, скажем gt, из Т. По предположе­ нию с (gt) ^ min с (g) = с (gs). Поскольку стоимости всех эле-

g £ T

ментов положительны, стоимость указанной комбинации эле­ ментов не меньше, чем с (gt), а, следовательно, не меньше, чем

с(gs)-

Валгоритме (шаг 2) элементы из Р складываются попарно, чтобы проверить, не будет ли сумма стоимостей двух элементов

из Р меньше текущей стоимости элемента, являющегосяих сум­ мой. Всякий раз, когда новый элемент выделяется постоянной пометкой, мы складываем его с самим собой и с каждым другим элементом, уже принадлежащим Р. Таким образом, лш проверяем сумму любых двух элементов из Р один раз.

Никогда не проверяется сумма трех элелюнтов из Р или любая

другая комбинация 2 g-t(g) со стоимостью

2 c(g)-t(g). Сле­

жек

g£P

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

*) Имеются в виду множества Р и Т для рассматриваемого шага. От шага к шагу они меняются, и Р (J Т — G \ 0 . — Прим. ред.

2 7 *

420 гл. 19. ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

Лемма f 19.4. Если существует элемент

gm£T, представи­

мый в виде gm= 2 g'Hg) с0 стоимостью

2 c (g)'t(g)> равной

g £ P

g £ P

минимально возможной стоимости пометки элемента gm, при­ чем для любого gs £ T .

2 c(g) . t(g)^c(gs),

 

(2)

то можно указать такие элементы ga u g b

из Р, что

 

gm= 2 g-t(g) = ga + gb, C(ga) + C{gb) =

2 c(g)-t(g).

(3)

g t P

g £ P

 

Иными словами, если в Т существует групповой элемент gm,

представимый комбинацией элементов из Р,

стоимость которого

минимально возможная для g и не больше стоимости любого дру­ гого элемента из Т, то gm с такой же стоимостью можно предста­ вить в виде суммы только двух элементов из Р. Заметим, что из этой леммы не следует, что элемент из Т с минимальной стоимо­

стью всегда равен сумме двух элементов из Р.

Например, gm =

= g m может быть наилучшим представлением

для gm ■

Д оказательство.

Предположим, что элемент gm из

Т может

быть представлен в

виде суммы элементов из

Р, как

указано

в лемме. Любую сумму можно разбить на два слагаемых. Напри­ мер, пусть

gm = 2g a + ge + g f

(ga, ge, gf € P ) .

(4)

Разобьем правую часть (4) на два слагаемых, скажем, так:

 

gm

=

(2ga) + (ge +

g f) = g a + gb,

(5)

где ga = 2ga и gb

=

ge + gf — некоторые элементы из G.

Оче­

видно, 2ga ф 0 и ge +

gf ф 0, так как в противном случае для gm

может быть получено представление с меньшей стоимостью (напом­

ним, что мы заменили

нулевые исходные стоимости с* (gt) = 0

на

ненулевые ег > 0),

что противоречит условию леммы.

 

Покажем, что сумма с (ge) + с (gf) стоимостей постоянных

пометок элементов ge

и gf равна с (gb)

— стоимости

постоянной

пометки элемента gb'

 

 

 

 

 

с (ge) +

С (gf) =

С(gb) =

C.(ge + gf).

(6)

 

Действительно, если бы (6)

было неравенством со знаком > ,

то

стоимость с (2ga) +

с (ge) +

с (gf) представления

(2) элемента

gm не была бы наименьшей вопреки предположению. Допустим,

что (6) — неравенство со

знаком < .

Так как gb = ge + gf,

то

в соответствии с шагом 2

алгоритма

сразу после того, как

оба

19.3.

АЛГОРИТМ

ГРУППОВОЙ

МИНИМИЗАЦИИ

421

элемента ge и

gj

оказались

в

Р, необходимо сделать сравнения

с (ge) + с {gj)

со стоимостью с'

(gb) текущей пометки элемента gb.

В случае с (ge) +

с (gj) •< с'

(gj) пометка элемента

gb изменилась

бы и ее стоимость стала бы равной с (ge) +

с {gf)

и далее

могла

лишь уменьшиться. Следовательно, знака <

в (6)

быть не может.

Итак, равенство (6) доказано.

Из (5),

(6) следует

 

 

с (2ga) + с (ge) +

с {gf) =

с (ga) + с (gb).

(7)

Ни ga, ни gb не могут принадлежать Т, поскольку в силу поло­

жительности с {gi) из

(7)

и (2)

следует,

что

с {ga), С {g b) <

2 с

(ga) +

с (ge) +

С {gf) < С {g s),

где gs — любой элемент из Т. Значит, ga и gb принадлежат Р, откуда в силу (7) следует утверждение леммы для представления gm, рассмотренного в (4). В общем случае рассуждения анало­ гичны. я

Сейчас мы докажем, что постоянные пометки в алгоритме действительно являются постоянными, т. е. все постоянные помет­ ки указывают минимальные стоимости и соответствующие комби­ нации групповых элементов, которые дают эти минимальные стоимости.

Теорема 19.9. Если групповому элементу нашим алгоритмом дана постоянная пометка, то эта пометка указывает минималь­ ную стоимость группового элемента и указывает для него мини­ мальное выражение.

Д о к а з а т е л ь с т в о . Используем индукцию по числу элементов множества Р. По лемме 19.3 первая постоянная пометка указывает минимальную стоимость помеченного элемента и его минимальное

выражение, которое

в этом случае имеет вид

= gt . Предполо­

жим, что для | Р |

=

п все постоянные пометки указывают мини­

мальные стоимости

и минимальные выражения для всех группо­

вых элементов из Р. Рассмотрим сначала первую компоненту следующей постоянной пометки.

Пусть gti, g;2, . . ., gin — элементы из Р. По предположению

индукции мы не можем заменить ни один из элементов Р комбина­ цией элементов из G с меньшей стоимостью. По лемме 19.3 мы не можем, комбинируя элементы из Р и Т или только элементы из Т, получить элемент со стоимостью меньшей, чем текущая минимальная стоимость элементов из Т. Таким образом, остается только проверить комбинации элементов из Р. По лемме 19.4, если такая комбинация существует, мы получим ее после завер­ шения шага 2 алгоритма. Следовательно, после завершения шага 2 алгоритма минимальная стоимость элементов из Г — истинная минимальная стоимость, которая и является первой компонентой

422 ГЛ. 19. ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

новой постоянной пометки. Теперь рассмотрим вторую компонен­

ту

новой

постоянной

пометки. Пусть gr — (п + 1)-й

групповой

элемент,

получивший

постоянную пометку, и пусть

gr =

ga +

+

gb (ga>§ь 6 ?)• Если пометка элемента ga есть l (ga) =

{с (a), a),

то

алгоритм

заменит

l (gr) на {с (a) +

c (b), а}. Это

указывает

на

то, что t (ga) > 1

 

в выражении для

gr.

 

 

 

Возвращаясь назад, имеем gT— ga =

gb, а для второй компо­

ненты пометки I (gb)

утверждение леммы справедливо по предпо­

ложению индукции.

(Случай gT =

gT тривиален.)

 

 

 

Если gT =

ga + gb и

l (ga) =

{c (ga),

]}, то алгоритм заменит

I (gT) на

{с (а)

+ с (Ъ),

/},

которое указывает на то, что t (g}) ^ 1

в выражении для gr. Но

из I (ga)

= {с (ga), /} следует, что ga =

=

gj + gft, поскольку мы предположили, что пометка

I (ga)

корректна.

ga +

gb =

gj + (gk + gb)- Выше мы показали, что

 

Итак, gr =

первые элементы всех постоянных пометок — корректны. Отсюда следует, что

с (g r ) = с (gj) + c (g k + gb) > c ( g h + gb).

Если (gh + gb) 6 T, то это противоречит тому, что gr—элемент из Т , так как он становится элементом из Р. Значит, (gh + gb) 6 Р.

Тогда из выражения l(g r) = {с (а) 4- с (Ь), /} следует, что t ( g j )

^

^ 1 в выражении для gr. Возвращаясь

назад, имеем gr — gj

=

= (gk 4- gb) 6 P. Таккак (gh + gb) 6 P,

это один из n первых

помеченных постоянной пометкой групповых элементов, а

он

по предположению имеет корректную постоянную пометку. Сле­

довательно, I (gr) также корректна.

Определим число

операций в этом алгоритме и сравним его

с числом операций

алгоритма Гомори, приведенного в § 19.2.

В алгоритме Гомори, если группа имеет порядок D и D — простое

число, необходимо

произвести D 2 сложений и D 2 сравнений.

Если D не является простым числом, необходимо q сложений и q

сравнений, где D 2 < q < 2D2. Итак,

если D не

является простым

числом, необходимо произвести не

более 4D2

операций, а если

D — простое число, необходимо произвести не более 2D2 операций.

На шаге 1 нашего алгоритма в первый раз мы должны выбрать

минимальную из D — 1 временных

пометок. Для этого необхо­

димо D — 1 сравнений. Во второй раз на шаге 1 необходимо D — 2 сравнений. Таким образом, общее число сравнений, необходимых на шаге 1, равно

( D - l ) + ( D - 2 ) + . . . + 1 =

D (D —1) • Д2

 

2

— 2 ’

На шаге 2 число сложений и число сравнений пропорциональ­ но мощности множества Р. Таким образом, необходимо

Смотрите также файлы