Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 73
Текст из файла (страница 73)
Таким образом, мы проверяем сумму любых двух элементов из Р одкп раз. Никогда не проверяется сумма трех элементов из Р вли любая другая комбинация Х д Г(д) со стоимостью В с(д) Е(у), Сле«ЕР «ЕР дующая лемма утверждает, что пока дело касается порождения элемента вз Т с минимальной стоимостью в Т (т. е. элемента, пометка которого после завершения шага 2 будет минимальной в Т) комбинации пар элементов из Р таь же хороши, как и все возможные комбинации элементов из Р. ') Имеются в виду множества Р в Т для рассматриваемого шага. От шага к шагу онз меняются, к Р ц т = 6" О.— Прим. реэ.
21" 4ЗС ГЛ. 19. ЛИНКИНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВА11ИК Ламма 19.4. Если существует элемент у б Т, представимый в виде д =- ~~' у 1(д) со стоимостью ~~' с(д) ° е(д), равной еЕР зЕ1' минимально возможной стоимости пометки элемента д, причем для любого д, б Т У с(ь) г(ь)(с(уе), (2) Зер то можно указать такие элементы уа и дь из Р; что Ут= ~ ь 'е(ее) = ееа, ееЬ~ С(Уа) —,С(УЬ) = ~ С(е)'С(ее). (3) ЗЕР еЕР Иными словами, есяи в Т существует групповой элемент д представимый комбинацией элементов из Р, стоимость которого минимально возмоисная для д и пе больше стоимости любого другого элемента иа Т, то д с такой же стоимостью можно представить в виде суммы только двух элементов из Р.
Заметим, что из этой леммы не следует, что элемент из Т с минимальной стоимостью всегда равен сумме двух элементов иа Р. Например, у;„=- = дт может быть наилучшим представлением для д Докхзлтельство. Прсдположим, что элемент д из Т может быть представлен в виде суммы элементов из Р, как указано в лемме. Любую сумму моя1но разбить па два слагаемых. Папример, пусть ьт = 2ееа + еее + Ут (ееа еее~ ее1 б 1 ).
(4) Разобьем правую часть (4) па два слагаемых, скажем, так: зт = (2еа) '+ (ье + Ю!) '= ееа + ееь (5) где д, —.— 2д„и дь = д, + у1 — некоторые элементы из 6. Очевидно, 2да чь 0 и де + д; чь О, так как в противном случае для ут мои1ет быть получено представление с меньшей стоимостью (напомним, что мы заменили пулевые исходные стоимости с* (д1) = 0 на ненулевые з, ) 0), что противоречит условию леммы. Покажем, что сумма с (уе) + с (дз) стоимостей постоянных пометок элементов Уе и деРавна с(дь) — стоимости постоЯнной пометки элемента дь'. С (еее) + С (еее) = С (ееЬ) С (аее ~ ее 1), (6) Действительно, если1 бы (О) было неравенством со злаком ), то стоимость с (2да) + с (де) + с (де) представления (2) элемента дт пе была бы наименьшей вопреки предполозкспию.
Допустим, что (6) — неравенство со знаком (. Так как Кь .= д, + ян то в соответствии с шагом 2 алгоритма сразу после того, как оба иьг. ллгогити гггиповоя минимиалпии 421 элемента д, и уг оказались в Р, необходимо сделать сравнения с (у,,) + с (кг) со стоиггостыо с (дь) текущей пометки элемента дь. В случае с (к„) + с (дг) ( с' (д~) пометка элемента уь изменилась бы и ее стоимость стала бы равной с (д,) + с (дг) и далее могла лигпь уменьгпиться. Следовательно, знака ( в (6) быть ве может.
Итак, равенство (6) доказано. Из (5), (6) следует с (2у, ) + с (ьг) + с (кг) — — = с (ьа) + с (дг,). (7) Ни д„пи уь пе могут принадлежать Т, поскольку в силу поло- ;кительности с (дг) из (7) и (2) следует, что с (уг), с (уь) ( 2с (д,) + с (у,) + с (д;) г=' с (д,), где д„— любой элемент из Т. Значит, д и дь принадлежат Р, откуда в силу (7) следует утверждение леммы для представления д, рассмотренного в (4). В общем случае рассуждения аналогичны. м Сейчас ыы докажем, что постояниьге пометки в алгоритме действительно являются постоянными, т, е. все постоянные пометки указывают минимальные стоимости и соответствующие комбинации групповых элементов, которые дают эти минимальные стоимости, Ткогкил '19.9.
Если групповому элементу нашим алгоритмом дана постоянная пометка, то зта пометка указывает минимальную стоимость группового элемента и указывает для него миниггальное вы равнение. Докязяткльство. Используем индукцию по числу элементов хпшжества Р. По лемме 19.3 первая постоянная пометка указывает минимальную стоимость помеченного элемента и его минимальное выражение, которое в этом случае имеет вид дг = дг . Предположим, что для ! Р ! = и все постоянные пометки указывают миниыалыгые стоимости и иипимальные выражения для всех групповых элементов из Р. Рассмотрим сначала первую компоненту следугощей постоянной пометки. Пусть д;,, дг,..., дго — элементы из Р. По предположению индукции мы не можем заменить ни один из элементов Р комбинацией злементов из 6 с меньшей стоимостью.
По лемме 19.3 мы не могкем, комбинируя элементы иа Р и Т или только элементы из Т, получить элемент со стоимостью меньшей„ чем текущая минимальная стоггмость элементов из Т. Такиыобразом, остается только проверить комбинации элементов из Р. По лемме 19.4, если такая комбинация существует, мы получим ее после завершения шага 2 алгоритма. Следовательно, после завершения шага 2 алгоритма минимальная стоимость элементов из Т вЂ” истинная минимальная стоимость, которая и является первой компонентой 432 Гл. 19. линейное и нелочислкнное ЕРОГРАммиРОВАние новой постоянной пометки.
Теперь рассмотрим вторую компоненту новой постоянной пометки. Пусть е„— (и + 1)-й групповой элемент, получивший постоянную пометку, и пусть д, = у + +»» (д„л» ~ Р). Если пометка элемента », есть((у,) = (с (а), а), то алгорит»1 заменит 1(д„) на (с(а) + с(Ь), а).
Это указывает на то, что ! (д,) )~ 1 в выражении для д„. Возвращаясь назад, имеем г„— и, = д~, а для второй компоненты пометки 1(Ь») утверждение леммы справедливо по предположению индукции. (Случай д„=- »„трнвиа»!еп.) Если е„= д, + д» и 1(д,) = (с(д,), 1), то алгоритм заменит 1(Ь',) на (с (а) + с (Ь), 1), которое указывает на то, что 1 (д1) ) 1 в выран1ении для»'„. Но из 1(д,) = (с (д,), 1) следует, что д, =— = е! +»», поскольку мы предположили, что пометка 1 (д,) корректна. Итак, д„= », + е» = е1 + (е» + »»). Выше мы показали, что первые элементы всех постоянных пометок — корректны.
Отса!да следует, что с (д,) = с (»1) + с (д» + дь) ) с (И» + Иь). Если (д» + д») с Т, то это противоречит тому, что »„ †элеме из Т, так как он становится элементом из Р. Значит,(л» + д») ч Р. Тогда из выражения 1(Ь'„) = (с (а) + с (Ь), ) ) следует, что 1 (»1) ) )» 1 в выражении для д„. Возвращаясь назад, имеем е„— д! = = (д» + д») Е Р.
Так как (д» + д») б Р, это один из и первых помеченных постоянной пометкой групповых элементов, а он по предположению имеет корректную постоянную пометку. Следовательно, 1 (д„) также корректна. Определим число операций в этом алгоритме н сравним его с числом операций алгоритма Гомори, приведенного в 5 19.2. В алгоритме Гомори, если группа имеет порядок Р и Р— простое число, необходимо произвести .0' слоясений и Р' сравнений. Если Р не является простым числом, необходимо д сложений и д сравнений, где 09 ( д ( 20'.
Итак, если Р пе является простым числом, необходимо проиавести не более 4Р' операций, а если .0 — простое число, необходимо произвести не более 2Р' операций. На шаге 1 нашего алгоритма в первый раз мы должны выбрать минимальную из Р— 1 временных пометок. Для этого необходимо Р— 1 сравнений. Во второй раз на шаге 1 необходимо Р— 2 сравнений.
Таким обрааом, общее число сравнений, необходимых на шаге 1, равно На шаге 2 число сложений и число сравнений пропорцнонально мощности множества Р. Таким образом, необходимо 19.3. АЛГОРИТМ ГРУППОВОЙ МИНИМИЗАЦИИ 423 1 + 2 +... + (Р— 2) = = — сложений и та- (0 И(п 2) н2 2 2 кое же число сравнений. В нашем алгоритме, следовательно, 222 необходимо всего Р' сравнений и — сложений. Если па шаге 1 2 мы каждый раз насчитываем Р сравнений, тогда необходимо всего 1,5 Р2 сравнений н 0,5 РЗ сложений.
Итак, в худшем случае, нам необходимо 2Р' операций независимо от того, является Р простым числом или нет.' Таким образом, предлагаемый алгоритм имеет следующие преимущества. 1. Число операций в данном алгоритме меньше числа операций в алгоритме Гомори (2Р' вместо числа, ааключениого между 2Р2 и 4Р2). 2.
Шаги одинаковы при выборе постоянных групповых элементов. Они пе зависят от порядка .группы 6 или элемента л. 3. Когда фиксированное лз в (1) принадлежит Р, то вычисления могут быть при желании прекращены. 4, Необходим пепыпий объем памяти. ГЛАВА 20 ГРАНИ ЦЕЛОЧИСЛЕННОГО МНОГОГРАННИКА 20.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
