Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 72
Текст из файла (страница 72)
Хотя у нас имеются достаточные условия (теорема 19.8) применимости асир1птотнческого алгоритма, реальные вычисления покажут, что алгоритм дает оптималытое решение и в болыпинстве случаев, когда достаточные условия не выполнены. 11а рис. 19.4 б ° и эачерпенпые точки обозначают пра- вые части Ь, для которых асиьштоти° ° ческий алгоритм дает оптимальное релрепие, а светлые кружки указы° ° вают правые части, где алгоритм нв ° ° дает решения. !З.З.
АЛГОРИТМ ГРУППОВОЙ МИНИМИЗАЦИИ 4)5 мальноы решении использоваться не будет. Заметим также, что с* (д) ' 0 для всех д 6 6, поскольку  — оптимальный базис соответствующей задачи линейного программирования г). для удобства изложения заменим с" (д!) = 0 на положительные е;, такие, что Рз; ( шш сэ (л) (с* (л) Ф 0)'). Мы предполагаем, что группа 0 является циклической группой порядка Р. Заметим,что рзявляется одним из элементов группы 6. Поэтому, реп!ение задачи ($) определяет представление группового элемента ра через другие элементы группы с наименьшей стоимостью; дз = ле со стоимостью с* (дэ) является одним из возможных представлений элемента лз.
Вместо того, чтобы рошать аадачу (1) для одного дз мы решим ее для всех возмол!ных правых частей Уз = д1,,Уз ° ° ' дн !. ДРУгими словами, кажДый элемент группы мы хотим выразить с наименьшей стоимостью через другие групповые элементы, на которых эта стоимость достигается. Эту задачу мы будем решать по этапаы. Инфорлгацпя, рассматриваемая на каждом этапе, называется текущей.
Пусть с (д„) — наименыпая (текущая) стоимость представления д„через другие элементы, известная к данному текущему моменту. Пару, образованну!о из с (д„) н числа, указывающего (кодирующего) з) представление д в виде комбинации со стоимостью с(д„), будем нааывать пометкой группового элемента д„. Пометку назовем временной, если она может быть изменена в процессе вычислений, т.
е. если может быть найдено представление для д„в виде комбинации элелгентов иэ С ', 0 со стоимостью, меньшей текущей стоимости с(д ). В противном случае пометку назовем постоянной. Вычисления начинаются с пометок (с*(д ), а). Эти пометки — временные, поскольку нет уверенности, что стоимость с* (д„) представления л„=д элемента д„наиз!еиьшая. Первую коз!Ионепту пометки будем называть ее стоимостью. Буден говорить, что пометка элемента д„меньше пометки элемента дз, если стониость пометки элемента д„меньше стоимости пометки элемента пщ Алгоритм (Ху И12)) состоит в следующем.
') ее (д) нсотрнцательно, так как оно равно компоненте вектора с" оценок небазнсных переменных относительно оптимального баззса В, Сн. задачу (5) нз п)юдыдущего параграфа.— Прим. ред. з) Нулевые стоимости заненнютсн стонностннн з! > О только дчя удобства доказательства. Нзт необходимости делать такие замены прн вычислениях. з) Кодировка предсгавленлн элемента в виде суммы с соответствующей стоимостью осущоствлнетсн специа:акын образок посргдстноп запонннаннн лишь одного слагаемого этого представ!!эннн, по которому рекуренвно ыоекно восстапсвнть остальные. Подробнее Об этом будет сказано далее.— Прим. ред.
4)б ГЛ. 19. ЛИНЕЙНОЕ И ПЕЛОЧИСЛВНПОЕ ПРОГРАММИРОВАНИЕ Ш а г 1. Сравнить стоимости всех временных пометок, объявить пометку с минимальной стоимостью постоянной и выделить ее. Если несколько пометок имеют минимальную стоимость, то В качестве постоянной выделить лагбую из них. [Паг 2. Пусть дг„а11„..., дг„— элементы группы с постояп- НЫМИ ПОМЕтиаин И ПУСТЬ Дгг — НОСЛЕДНИй ГРУППОВОЙ ЭЛЕМЕНТ, получивший постоянную намотку. Пайти суммы С (йг11) ) С (йггг), С (йгге) 1- С (йггг), ..., С (оь1г) С (йггг) и сравнить их соответственно с с(дгг+лг„), с(дгт-'.Пг„), ..., С(бг, '-Яг„).
Если с(дг ) -' с(дг ))с(дг -' яг ), то пометки не менять. Если же с(а',,).~ с(зг )(с(хг.—,'.))1 ), то заменить пометку группового элемента (а.,—;-дг ) на [с(иг ) б. С(дг )„г)[, где, г) — вторая компонента текущей намотки эле»гента дг '). (Можпо также заменить вторую '1' ЬОЗШОПЕНтУ ПОМЕТКИ (дг —,- иг ) ВтОРОй КОМПОПСНтай ПОМЕТКИ дг ). Перейти к шагу 1.
Работа алгоритма закапчиваетсн, когда все пометки стгшут постоянными. Прежде чем привести доказательство и подсчитать число операций в алгоритме, рассмотрим численный пример. Предположим, что группа 6 — циклическая порядка 10; соответствугощйе стоимости приведены ниже: са(дг) =-10, 3, 2, 7, 8, 5, 4, 9, 7 Ьггг аз Ьгв ат Ь'Ег Звг ат Ьге ае. Сначала заполним ряд из Р— 1 нар, соответствугощих,Р— 1 элементам группы.
Все пометки — временные: а1 ае йз а4 уе ае а7 ав а9 1. Сравниваем стоимости всех временных пометок и выделяем [2, 3[ как постоянную пометку посредством введения знака в анижиий правый угол» пары. ') Достаточно запо»ипать информацию лишь об одаом слагаемом рн 'У' прелстаалепия (аг + дг ), так как второе однозначно восстапавлпаается 1 г как разность элементов (аг + д,. ) п дг . Поскольку элемент дг имеет посто- 1 ° ' ' ' 1) яппую пометку, ее стоимость могкет не совпадать с исходпой с»(дг), стоимость пометка определяется представлеииом элемепта с наименьшей стоимостью, иаформацаа о котором и дается второй коюгонентой д.— Прим, ред.
1а,з. АИГОРитм ГРу!гловой минимизАнии 417 2. Поскольку [2, 31 — единственная постоянная пометка, то сравниваем с (дз) + с (дз) с с (рз), так как дз + дз = дз "). Имеем с (зез) + с(дз) = 2 + 2 =- 4( 5 =- с(ба). Заменим [5, 61, соотпетстпу!оп)ую де, иа [4,3!.
(Заметим, что вторая компонента пометки элемента уз заменяется второй компонентой пометки дз). Это показано ниже: С1 ЗЗ ЗЗ ЗЗ аа Сз Сз Сз За 1. Сравниваем стоимости всех временных пометок и выделяем [3, 2] как постоянную пометку. 2. Поскольку дз — последний групповой элемент, получивший постояпну!о пометку, сравниваел! с Ыз) -! с (за) = 2 г 3 = 5 ( 8 = с (Рз), и заменяем !8, 5] на [5, 31; с (~,) ы- с(зз) = 3 —; 3 = 6 ( 7 = — с(рз), и замепасм 17,41 на 16,2!.
В результате получается У1 УЗ КЗ Се СЗ КЕ К! 09 Уа 1. Сравниваем стоимости всех временных пометок и выделяем либо [4,31, либо [4,7] как постоянную пометку. Здесь ыы выделяем !4,31. 2. ]!оскольку дз — последний групповой элемент, получивший постоянную пометку, сравниваем с (ле) --,'— с (дз) = 4 -',- 4 =- 8 ) 3 = с (дз), замен нет. !) Воебьчес! -,— д л; —,„, сае я - 1; ! (пзое) 10), ыеатеиу с(де-гс )= — с (у;~. )=-с(я, ).— Ирам. Ред. 27 т хт с(дз) ',. с(яе) = 2+ 4 = с(дз) !-с(дз) =3+4 = 6 ( 7 = с (дз), и заменяем [7,9) па 16,31; 7 ( 9 = с (дз), и заменяем [9,81 па [7,2): 413 гл.
цс липкинок и цклочислкцпог, пгоггхммиговхпив Тогда имеем вв Зв ХЗ км вв Ив яч вв вв 10 3 2 6 6 4 4 7 6 1 2в Зв 2 3 зв 7 2 3 постояннуво пометку. постоянную пометку. с(дв) + с(4в) = 2 -[- 5 = 7 = 7 = с(дв), замен пет; с (дв) + с (лв) = 3 + 5 = 8 ) 4 = с (дт), замен нет; с(Ав) + с(лв) =4+ 5 = 9(10 = с(д), заменяем [10,1[ на [9,3[. Заметим здесь, что второй компонентой текущей пометки дв является 3.
с(И+с(й) =4+5 =9 >3 =с(дв), замен нет; с (вв) + с (в'в) = 5 + 5 = 10 ) 0 = с (0)„замен пет. Продолжая процесс, выделяем [6,2[, как постоянную пометку, повторяем шаг 1 и шаг 2. В дальнейшем замен не происходит, так что в конце концов мы получим Й вв вз зв Ив Юв Хв Лв вв Предположим, что мы хотим найти представление группового элемента дц имеющее наименьшую стоимость.
Второй компонентой пометки д, является 3. Следовательно, мы знаем, что в искомое представление Л, = 2.1 (д) д входит 1 (Ь в) ~ 1. Возвращаясь назад, полУчаем д, — 4в =- Лв и виДим, что втоРой компонентой пометки элемента лв является 2. Это означает, что 2 (дв) Ъ 1. Возвращаясь назад, полУчаем Дв — дв = 4в и вицим, что втоРой компонентой 1. Выделяем [4,7[ как 2.
Сравниваем с (дв) -',— с (лт) =- 2 с(дв) +с(47) =3 с (6'в) [- с М,) = 4 с(д,) -, 'с(лв) =4 1. Выделяем [5,3[ как 2. Сравниваем + 4 = 6 ) 0 = с (0), замен нет; + 4 = 7 ) 6 = с (дв) замен нет; + 4 = 8 ) 2 = с (дв), замен нет; +4 =8)6 = с(дв), замен нет.
19.3. АлГОРитм ггупповон мннимизлции 449 пометки элемента уе снова является 3. Это означает, что Е (уг) - 2. Возвращаясь назад, получаем у« — уг = уг н видим, что второй компонентой пометки элемента уг является 3 и, следовательно, Е (уг) «) 3. Возвращаясь назад, получаем у, — дг = О. Таким образом, искомое представление имеет вкд д1 = Зуг + ую а его стоимость, являющаяся первой компонентой пометки элемента у1, равна 9. Обозначим мнол1ество групповых элементов с постоянными пометками через Р, а мнон1ество групповых элементов с временными пометками через Т ').
Мы будем использовать выражение «комбинирование групповых элементов для получения группового элемента уо», имея в виду «нахождение различных представлений Хф (у) = до со стоимостью, равной Хс (д) г (у)». Лкммя 19.3. Комбинация групповых элементов из Т или комбинация групповых элементов из Р с однимили более элементами из Т не мелеет дать группового элемента ую такого, что С (У„) ( Ш 1П С (У) =- С (Уг). еет Докязлтвльство, Номбинация элементов из Т нли комбинация элементов из Р с одним илн более элементами из Т содержит по меньшей мере один элемент, скажем ун из Т.
По предположению с(д1) » «ш(п с(у) = с (уг). Поскольку стоимости всех эле- «ЕГ ментов положительны, стоимость указанной комбинации элементов не меньше, чем с (у1), а, следовательно, не меньше, чем с (уе). В алгоритме (шаг 2) элементы из Р складываются попарно, чтобы проверить, не будет ли сумма стоимостей двух элементов из Р меньше текущей стоимости элемента, являющегося их суммой. Всякий раз, когда новый элемент выделяется постоянной пометкой, мы складываем его с самим собой и с каждым другим элементом, уже принадленсащнм Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
