Структуры данных и алгоритмы (1021739), страница 80
Текст из файла (страница 80)
В этом случае мы удаляем до k ребер и "перекоммутируем" оставшиеся элементы влюбом порядке, пытаясь получить какой-либо маршрут. Обратите внимание: мы нетребуем, чтобы удаленные ребра вообще были несмежными, хотя в случае двойноговыбора не было никакого смысла рассматривать удаление двух смежных ребер. Обратите также внимание, что при k > 2 существует несколько способов соединениячастей графа. На рис. 10.22 представлен процесс тройного выбора с помощью любойиз перечисленных ниже восьми совокупностей ребер.1.(A. F), (D, E), (В, С)(исходный маршрут)2.(A, F), (С, Е), (D, В)(двойной выбор)3.(А, Е), (F, D), (В, С)(еще один двойной выбор)4.(А, Е), (F, С), (В, D)(тройной выбор)5.(A, D), (С, Е), (В, F)(еще один тройной выбор)6.(A, D), (С, F), (В, Е)(еще один тройной выбор)7.(А, С), (D, E), (В, F)(двойной выбор)8.(А, С), (D, F), (В, Е)(тройной выбор)10.5.
АЛГОРИТМЫ ЛОКАЛЬНОГО ПОИСКА305Легко убедиться в том, что для фиксированного k количество различных преобразований при fe-выборе, которые необходимо рассмотреть при наличии п вершин, равно O(nk). Например, при k = 2 точное количество таких преобразованийравно п(п - 3)/2. Однако время, которое требуется для получения какого-либо из локально-оптимальных маршрутов,может оказаться значительно больше этой величины, поскольку для получения этого локально-оптимального маршрута надо выполнить довольно много локальных преобразований, а каждое улучшающее преобразование связано с ввеРис. 10.22.
Выбор эле- дением новых ребер, которые могут участвовать вментовмаршрута последующих преобразованиях и еще больше улучшают данпосле удаления трех ный маршрут. В работе [68] показано, что с практическойребер 'точки зрения "выбор с переменной глубиной" (т.е. выбор сразными значениями k на разных этапах) является чрезвычайно эффективным методом и с большой вероятностью обеспечивает получение оптимального маршрута для задач коммивояжера с 40-100 городами.Размещение блоковЗадачу одномерного размещения блоков можно сформулировать следующим образом. Есть неориентированный граф, вершины которого называются "блоками".
Ребраграфа помечаются "весами", причем вес w(a, b) ребра (а, Ь) представляет собой количество "проводов" между блоками а и Ъ. Задача состоит в том, чтобы упорядочитьвершины pi, р2рп таким образом, чтобы сумма величин |i - y| w(pt, pt) по всем парам i и /' была минимальной, т.е.
надо минимизировать сумму длин проводов, необходимых для соединения всех блоков требуемым количеством проводов.У задачи размещения блоков есть ряд приложений. Например, "блоки" могутпредставлять собой логические платы в стойке; весом соединения между платами вэтом случае является количество соединяющих их проводников.
Аналогичная задачавозникает и в случае проектирования интегральных схем на основе набора стандартных модулей и взаимосвязей между ними. Более общий случай задачи одномерногоразмещения блоков допускает размещение "блоков", имеющих определенную высотуи ширину, в двумерной области с минимизацией суммы длин проводов, соединяющих эти "блоки". Эта задача, имеющая множество различных приложений, применяется и в проектировании интегральных схем.Для нахождения локальных оптимальных решений задач одномерного размещения блоков можно применять ряд локальных преобразований. Вот некоторые из них.1.Произвести взаимную перестановку смежных блоков pt и pj+1, если результирующий порядок имеет меньшую стоимость.
Пусть L(j) — сумма весов ребер,расположенных слева от блока pjt т.е. Ч"щ(п ,р.)- Аналогично обозначим черезЬ=1R(j) суммуV w^p t p j весов ребер, расположенных справа от блока р;. Улучше*=;+!ние можно выполнить, если L(i) - R(i) + R(i + 1) - L(i + 1) + 2w(pt, pi+i) являетсяотрицательным числом. Читатель может убедиться в справедливости этой формулы, вычислив соответствующие стоимости до и после взаимной перестановкии оценив разность между этими стоимостями.2.
Взять пакет pt и вставить его между pt и pi+i при некоторых значениях i и j.3. Выполнить взаимную перестановку двух блоков pt и pt.Пример 10.13. Возьмем в качестве примера размещения блоков граф, показанный на рис. 10.16. Ограничимся простой совокупностью преобразований (1).Начальное размещение блоков а. Ъ, с, d, e показано на рис.
10.23,а, его стоимостьравна 97. Обратите внимание, что функция стоимости определяет вес ребра в со306ГЛАВА 10. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВответствии с количеством промежуточных ребер между блоками в выбранномразмещении блоков, соединенных этим ребром, поэтому "вклад" ребра (а, е) вобщую стоимость составляет 4 x 7 = 28. Рассмотрим взаимную перестановкублоков d и е. Сейчас L(d) = 13, R(d) = 6, L(e) = 24 и R(e) = 0.
Таким образом,L(d) - R(d) + R(e) - L(e) + 2w(d, e) = -5, поэтому следует произвести перестановку блоков d и е, получив улучшенное размещение а, Ь, с, е, d, стоимость которого, как следует из рис.- 10.23,6, равна 92.На рис. 10.23,6 можно произвести выгодную взаимную перестановку блоков сие,получив таким образом размещение блоков, показанное на рис. 10.23,в; стоимостьэтого размещения равна 91. Размещение на рис.
10.23,в является локальнооптимальным для совокупности преобразований (1). Однако оно не является глобально-оптимальным, поскольку для размещения а, с, е, d, b стоимость равна 84. П841 3 Ь 4 'с 5 ( 1 6 о16354Э' 3 ЬI4'с'8<»6 с36['72абРис. 10.23. Локальные оптимизацииКак и в задаче коммивояжера, мы не в состоянии точно оценить время, необходимое для достижения локального оптимума. Можно лишь констатировать факт, чтодля совокупности преобразований (1) надо рассмотреть только п - 1 преобразований.Далее, после того как мы однажды вычислили L(i) и R(i), нам придется лишь заменять их при выполнении взаимной перестановки р, с pt-i или р,+1. Более того, подобный пересчет не представляет особого труда.
Если, например, выполняется взаимнаяперестановка блоков р, и pi+i, тогда новыми значениями ДО и R(i) будут соответственно величины ДН-1) - «>(р„ рм) и Д(Н-1) + w(pt, pt+i). Таким образом, времени порядка О(п) будет достаточно, чтобы проверить, является ли выполняемое преобразование улучшающим, и повторно вычислить все Щ) и Л(0- Кроме того, на начальноевычисление всех значений Щ) и R(i) также понадобится лишь О(п) времени, если мывоспользуемся рекуррентными соотношениямиД1) = 0,и аналогичными рекуррентными соотношениями для R.Для сравнения: каждая из совокупностей преобразований (2) и (3) имеет О(и2)членов. Таким образом, потребуется О(п2) времени лишь для того, чтобы убедиться втом, что мы вышли на одно из локально-оптимальных решений.
Однако, как и вслучае совокупности преобразований (1), мы не в состоянии точно оценить общеевремя, которое может потребоваться для выполнения ряда последовательных улучшений, поскольку каждое такое улучшение может создавать дополнительные возможности для дальнейших улучшений.10.5. АЛГОРИТМЫ ЛОКАЛЬНОГО ПОИСКА307Упражнения10.1.
Сколько перемещений необходимо выполнить для перестановки п дисков в задаче о "Ханойских башнях"?*10.2. Докажите, что рекурсивный алгоритм декомпозиции, используемый для решения задачи о "Ханойских башнях", и нерекурсивный алгоритм, описанныйв начале раздела 10.1, выполняют одни и те же действия.10.3. Используя алгоритм декомпозиции (листинг 10.1), выполните умножение чисел 1011 и 1101.*10.4. Обобщите составление расписания теннисного турнира (см. раздел 10.1), есликоличество его участников не выражается степенью числа 2.
Совет. Если п(количество участников турнира) нечетное, тогда каждый день один из участников должен полностью освобождаться от проведения матчей, а проведениетурнира в целом займет п, а не п — 1 дней. Если, однако, сформировать двегруппы с нечетным количеством участников, тогда игроки, освобожденные отпроведения матчей в каждой такой группе, могут провести матч друг с другом.10.5. Существует следующее рекуррентное определение числа сочетаний из п элементов по т, обозначается как С™ , для л > 1 и 0 < /п < га:С™ = 1, если т = 0 или т = п,С1сГ = п 1 + С™", , если 0 < т < п.ПП—1П—1 'а) укажите рекурсивную функцию для вычисления чисел С™ ;б) каким в наихудшем случае будет время вычисления этой функции в зависимости от га?в) на основе метода динамического программирования разработайте алгоритмдля вычисления чисел С™ .
Совет. Этот алгоритм должен составлять таблицу, известную как треугольник Паскаля;г) каким будет время выполнения этого алгоритма в зависимости от га?10.6. Один из способов вычисления количества сочетаний из п элементов по т заключается в вычислении выражения (п)(л - 1)(га - 2)...(га - т + 1)/(1)(2)...(/п).а) каким в наихудшем случае будет время вычисления этого алгоритма в зависимости от п?*б) возможно ли примерно таким же способом вычислить вероятности P(i, j)победы в турнирах (см. раздел 10.2)? Как быстро можно выполнить это вычисление?10.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
