Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 92
Текст из файла (страница 92)
Комментарии и ссылки в) Покажите, что если после 1=! У! этапов мы не остановились в смысле п. б), о это означает, что имеется цикл отрицательной стоимости. Используя это, до:ажите, что алгоритм требует 0((УК) времени. г) Сравните повеление этого алгоритма в худшем случае с поведением алго~итмз Флойда — Уоршелла. 1О. Предположим, что нам нужно вычислить произведение л матриц Аг, 1з, ..., А„, где А! имеет р! строк и ог столбцов Естественно, предполагается, то они совместимы, г.
е. Чг=рг+и !=1, ..., л — 1 Разработайте алгоритм динами. еского программирования с временем работы О(лэ) для нахождения порядка ум. .ожения этих ь1атрнц, при котором минимиэируется общее число скалярных уможений в предположении, что умножение А! и А!э, гребует лннге, скалярных множений. Какой объем памяти гребчется вашему алгоритму? 11. Обьясните, почему злгоритм ДП-1 иэ э 17,3 для задачи 0-1-РЮКЗАК южно рассматривать кзк алгоритм динамического программирования. 12. Сформулируйте алгоритм динамичесиого программирования для ЗК пример !8.8) как алгоритм ветвей и границ беэ верхних и нижних границ, но с тношением доминирования. (аммантарнн н ссыпмн Хорошим обзором метода ветвей и границ вплоть до 1966 г.
о указанием оответствующих более ранних источников является работа (лч( Еатч!ег Е. 1, ууооб О, Е. Вгапсй-апб.ВошМ Ме!Ьобэ: А Бпгчеу, ОК, 14 (1966), 699 — 719. ! этой работе описаны как подход Литтла и др. к ЗК: 1.МБК( ЫЕПе 3. О. С., Мцг1у К. О., Бтчеепу О. )Ч., Каге) С.
Ап А(йогй1ип 1ог йе ТгачеПпй-Ба!еыпап РгоЫегп, ОК, 11 (1963), 972 — 989, ак и подход Истмена. Еа) Еаа!тап !Ч. Е йпеаг Ргойгатт!пй !ч!!Ь РаНегп Сопэ!га|п(з, РЬ. О. ТЬю)з, Керог1 Но ВЕ 20, ТЬе Соври!аНоп 1.аЬога1огу, Нагчэгб Оп!чета!(у, 1958. тормулировка задачи ЦЛП, приведенная в 9 18.1, взята иэ работы Оз( ОаРЗп К. 3.
А Тгее-Беагсп А(йогПЬгп йг М!хеб (п!ейег Ргойгавв!пй РгоЬ1евз, Согпр., Л, 8, )(о. 3 П965), 250 — 255. 1риведенная формулировка метода ветвей и границ, так же кзк примеры конейерной обработки, следуют сгатье Колера и Стайглица в гл. 6 в :о( СоПтап Е О., 3г., ей Соври!ег зпб ЯоЬ-БЬор БсйебцПпй. Ыечг Уогй; (Чйеу(п1егзс|епсе, 1976. ней можно найти результаты некоторых вычислительных экспериментов с спсльэованием метода ветвей и границ, а также формулировку задачи о рас.
исании с помощью динамического программирования, которая окаэываегся квивзлентной методу ветвей и границ. Нижняя граница и отношение доминирования для задачи о конвейере взяты э статьи !Б) 1йпай Е., Бсйгайе Е. АррПса1юп о! йе ВгапсЬ апд Воппб ТесЬп!Опе 1о Боте Г!оеч-БЬор БсйебпПпй РгоЫетз, ОК, 13. (чо. 3 (!965), 400 — 412. 'еорему 18.1 можно найти в ММ( Сопжау К (Ч., МзхцеП (Ч. Е., М!Пег Е. )Ч.
ТЬеогу о( БсйебнПпй. Кеайпй, Мзю.. Або!эоп-)Чеэ!еу РцЫ!эЫпй Со., 1пс., 1967. (Имеется перевод: Конзей Р. В., Максвелл В. Л., Миллер Л. В, Теория расписаний.— М.: Наука, 1975. ( 466 Гл. 18. Метод ветвей и границ Теорема 18.2 опубликована в [О35) Оагеу М. К., 3оЬпзоп О. 5., 5е183 К. ТЬе Совр)ехИу о( Р)опгзйор апг$3оЬ- ьйор 5сйебн))пд, Ма(Ь. о1 ОрегаНопа $)ез., 1 (1976), 1$7 — 129.
Идеи Халда и Карпа, основанные на использонании )-деревьев, взяты из работ [НК1[ Не!д М., Кагр й М. ТЬе Тгаче)$!пд 5а)еашап РгоЬ)еш апб М)п)шнш 5рапп. !пй Тгесз, Ой, 18 (1970), !!38 — 1162. [НК2[ $)е)б М, Катр $1. М. ТЬе Тгаче!)пд 5а)ее|пап РгоЬ)еш апб М)п!шшп 5рапп1пя Тгесз. Раг1 11, МаСи Ргоб., 1 ($970, 6 — 25.
Формулировку ЗК с помощью динамического программирования, а также формулировки других комбинаторных задач можно найти в статье [НКЗ[ Не)б М., Катр й. М. А Оупаппс Ргойгаппп)пй Арргоасй !о 5ецпепс)пй Ргой)ешз, Х, ЯАМ, 10, ! (!962), 196 — 2$0. Решения залач 7 — 9 можно найти в книге [ОЦ Огеу1из 5. Е., Еаш А. М. ТЬе Аг1 апг! ТЬеогу о1 Оупаппс Ргойгашш!пй. Л)ечг Уог!и Асабеп1ш Ргеем )пс., $977. Эта книга содержит главу, в которой дано исчерпывающее изложение задачи о кратчайшем пути, вкточая некоторые (касающиеся константных множителей) улучшения для задачи с одним источником и для задачи о расстояниях между всеми парами вершин Алгоритм, описанный в задаче 9, имеет неясное происхож.
ление. В статье [0!! ОгеуЬж 5. Е. Ап Аррга)за! о1 5опге чйшг1ез1.Ра!Ь А16огйЬщз, Ом, $7 ($969), 395 †4 даются ссылки на работь1 Форда, Мура и Беллмана соответственно 1956, $957 н !958 гг. !9 Локальный поиск ~Е.1 Введенме Локальный поиск основан на старейшем, по-видимому, методе оптимизации — методе проб и ошибок. Его идея настолько проста и естественна, что очень удивительно, насколько успешным оказывается локальный поиск для многих трудных комбинаториых задач оптимизации. Оценить его силу и тонкости построения соответст. вующих алгоритмов лучше всего на примерах, поэтому мы начнем эту главу с подробного разбора ряда примеров. Затем мы разберем некоторые теоретические аспекты локального поиска, которые близки по духу симплекс-алгоритму. Мы уже касались основных компонент локального поиска в гл !.
Приведем теперь общий алгоритм. Пусть дана индивидуаль. ная задача оптимизации (г", с), где Š— допустимое множество н с — функция стоимости. Выберем систему окрестностей А(. о 2д которая будет просматриваться для улучшения решения в точке (Е Е с помощью подпрограммы любое з Е М ((), для которого с (з) < с (1), УЛУЧШЕНИЕ(1) = если такое ь существует, «нет» в противном случае. Общий алгоритм локального поиска приведен на рис. )9.), Алгоритм начинается с выбора некоторого начального допустимого рергоседпге ЛОКАЛЬНЫЙ ПОИСК Ьей!и 1;=некоторая исходная начальная точка иа Р; пЬ!!е УЛУЧШЕ!!ИЕ(1) Ф "нет" оо 1: УЛУЧШЕНИЕ(!); геьхгп 1 епп' Рнс.
!9.1. Общий алгоритм локального поиска. шения (ЕЕ и далее использует подпрограмму УЛУЧШЕНИЕ для поиска лучшего решения в окрестности этой точки. Ло тех пор пока удается найти улучшенное решение, мы запоминаем его и начинаем поиск по окрестности из этого нового решения; прн достижении локального оптимума останавливаемся. Гл. 1З.
Лопал»иый поиск Прп применении этого подхода к конкретной задаче приходится несколько раз осуществлять выбор. Во-первых, нужно решить, как получить исходное допустимое решение. На практике иногда полезно производить локальный поиск из нескольких различных начальных точек и затем выбрать наилучший результат. В таких случаях нужно также решить, сколько взять начальных точек и как их распределить. Затем нужно выбрать «хорошую» систему окрестностей для рассматриваемой задачи и метод поиска по ней. В этом выборе обычно приходится полагаться на интуицию, поскольку на этот счет теоретических обоснований нет. Однако здесь легко заметить явную конкуренцию между маленькими и большими окрестностями. Окрестность большего размера обещает дать лучший локальный оптимум, но потребует более долгого поиска, поэтому можно ожидать, что меньшее количество таких оптимумов можно будет найти за фиксированное количество машинного времени.
Порождать ли меньше «сильных» или больше «слабых» локальных оптимумов? На эти и подобные вопросы ответ обычно получают эмпирически, и разработка эффективных алгоритмов локального поиска была и остается в большой степени искусством. 19.2 Задача 1: ЗК Напомним, что в гл, 1 для ЗК следующим образом была определена окрестность относительно й-замены (lг)2) для произвольного обхода с можно получить из сс удалением из г" и заменой их снова й ребрами). В 1958 г.
появились две работы, в которых для ЗК использовался локальный поиск относительно А-замены, и в обеих этот подход применялся в комбинации с переборными методами, аналогичными методу ветвей и границ, для получения оптимальных решений, Кроес !Сг! использовал М, и назвал 2-замену «инверсией», Бок !Во) использовал М» Еще две работы, в которых локальный поиск применялся к ЗК, появились в 1965 г. Шерман и Рейтер )ЯК! исследовали много различных систем окрестностей, но только Лин !).1! первым убедительно продемонстрировал силу системы окрестностей относительно 3-замены М».
Например, Лин эмпирически нашел, что 3-оптимальный обход для задачи Хелда и Карпа !НК!! с сорока восемью городами оказывается оптимальным с вероятностью около 0.05, и, следовательно, если произвести вычисление для 100 случайных начальных точек, то при этом с вероятностью 0.99 получится оптимальное решение.
Одно из важных достоинств работы Лина состоит в том, что 1д.д. Задача се нодеосные сети мннимоеьной стоимосто 469 в ней делается упор на использование многих различных распределенных случайным образом начальных решений; в ЗК эффектив- ПЫМ ОКаэсяВаЕтея ПСНОЛЬЗОВаНИЕ СОВЕрШЕНиб СдуЧайНЫХ цаЧаЛЬИЫХ обходов. Можно подумать, что, начиная с решений, которые в среднем лучше, чем полностью случайные обходы (которые, по-видимому, очень плохи), мы улучшали бы качество получаемых локальных оптимумов. Однако похоже, что в ЗК при использовании 3-оптимальности это не так, на что указывают обширные вычислительные эксперименты, проведенные Вейнером !не опубликованы).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
