Структуры данных и алгоритмы (1021739), страница 79
Текст из файла (страница 79)
Но нижняяграница G равняется 23, что превосходит наилучшую на данный момент стоимость — 21. Следовательно, мы удаляем узел G. Теперь возвращаемся в узел В и исследуем его второго сына, узел D. Нижняя граница для D равняется 20.5, но, таккак стоимости являются целочисленными значениями, нам известно, что ни у одногоиз маршрутов, включающих D, стоимость не может быть меньше 21. Поскольку унас уже имеется столь дешевый маршрут, нам не придется рассматривать потомковD, следовательно, отсекаем узел D. Теперь возвращаемся в узел А и рассматриваемего второго сына, узел С.На уровне узла С мы рассмотрели только одно ребро (а, Ь).
Узлы J и К являютсясыновьями узла С. Узел J соответствует тем маршрутам, которые содержат ребро(а, с), но не содержат ребро (а, Ь), его нижняя граница равняется 18,5. Узел К соответствует тем маршрутам, которые не содержат ни ребро (а, с), ни ребро (а, Ь), отсюда следует вывод, что эти маршруты содержат ребра (a, d) и (а, е). Нижняя границадля узла К равна 21, поэтому можем отсечь узел К, поскольку уже известен маршрутс такой стоимостью.Далее рассматриваем сыновей узла J, которыми являются узлы L и М; мы отсекаем узел М, поскольку его нижняя граница превосходит стоимость наилучшего изнайденных на данный момент маршрутов.
Сыновьями узла L являются узлы N и Р,соответствующие маршрутам, которые содержат ребро (Ь, с) и исключают ребро(Ъ, с). Учитывая степень вершин Ь и с и помня о том, что отброшенные ребра не могут образовывать цикл из менее чем всех пяти вершин, можем сделать вывод, чтоузлы N и Р (каждый из них) представляют отдельные маршруты.
Один из них (а, с,Ь, е, d, а) имеет наименьшую среди всех маршрутов стоимость — 19. Таким образом,мы проверили все дерево и частично сократили его. D1Мы могли бы взять за исходную точку какое-либо решение, найденное эвристическимспособом (например, с помощью "жадного" алгоритма), хотя для нашего примера это не имеетзначения. Стоимость "жадного" решения для графа из рис. 10.16 равняется 21.10.4. ПОИСК С ВОЗВРАТОМ30110.5. Алгоритмы локального поискаОписанная ниже стратегия нередко приводит к оптимальному решению задачи.1.2.Начните с произвольного решения.Для улучшения текущего решения примените к нему какое-либо преобразованиеиз некоторой заданной совокупности преобразований. Это улучшенное решениестановится новым "текущим" решением.3. Повторяйте указанную процедуру до тех пор, пока ни одно из преобразований взаданной их совокупности не позволит улучшить текущее решение.Результирующее решение может, хотя и необязательно, оказаться оптимальным.В принципе, если "заданная совокупность преобразований" включает все преобразования, которые берут в качестве исходного одно решение и заменяют его каким-либодругим, процесс "улучшений" не закончится до тех пор, пока мы не получим оптимальное решение.
Но в таком случае время выполнения пункта (2) окажется такимже, как и время, требующееся для анализа всех решений, поэтому описываемыйподход в целом окажется достаточно бессмысленным.Этот метод имеет смысл лишь в том случае, когда мы можем ограничить нашусовокупность преобразований небольшим ее подмножеством, что дает возможностьвыполнить все преобразования за относительно короткое время: если "размер" за23дачи равняется га, то мы можем допустить О(п ) или О(п ) преобразований. Еслисовокупность преобразований невелика, естественно рассматривать решения, которые можно преобразовывать одно в другое за один шаг, как "близкие".
Такие преобразования называются "локальными", а соответствующий метод называется локальным поиском.Пример 10.11. Одной из задач, которую можно решить именно методом локального поиска, является задача нахождения минимального остовного дерева. Локальными преобразованиями являются такие преобразования, в ходе которых мы берем тоили иное ребро, не относящееся к текущему остовному дереву, добавляем его в этодерево (в результате мы должны получить цикл), а затем убираем из этого цикла вточности одно ребро (предположительно, ребро 'с наивысшей стоимостью), чтобы образовать новое дерево.Рассмотрим, например, граф на рис.
10.16. Мы можем начать с дерева, показанного на рис. 10.18,а. Одно из преобразований, которые можно было бы выполнить,заключается в добавлении ребра (d, e) и устранении из образовавшегося цикла (е, а,с, d, e) какого-либо другого ребра. Если мы удалим ребро (а, е), то уменьшим стоимость дерева с 20 до 19. Это преобразование можно выполнить, получив в результатедерево (рис. 10.18,6), к которому мы опять попытаемся применить улучшающее преобразование. Одно из таких преобразований сводится к вставке ребра (a, d) и удалению из образовавшегося цикла ребра (с, d).
Результат этого преобразования показанна рис. 10.18,в. Затем можно вставить ребро (а, Ь) и убрать ребро (Ь, с), как показанона рис. 10.18,г, а потом — вставить ребро (Ь, е) вместо ребра (d, e). Результирующеедерево (рис. 10.18,д) является минимальным. Мы можем убедиться в том, что каждое ребро, не входящее в состав этого дерева, имеет наивысшую стоимость среди всехребер в цикле, который они с этим ребром составляют. Таким образом, к дереву нарис. 10.18,г преобразования уже неприменимы. DВремя, которое занимает выполнение алгоритма в примере 10.11 на графе из пузлов и е ребер, зависит от количества требующихся улучшений решения. Одналишь проверка того факта, что преобразования уже неприменимы, может занятьО(пе) времени, поскольку для этого необходимо перебрать е ребер, а каждое из нихможет образовать цикл длиной примерно п.
Таким образом, этот алгоритм несколькохуже, чем алгоритмы Прима и Крускала, однако он может служить примером получения оптимального решения на основе локального поиска.302ГЛАВА 10. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВгдРис. 10.iS. Локальный поиск минимального вставного дереваЛокальные и глобальные оптимальные решенияАлгоритмы локального поиска проявляют себя с наилучшей стороны как эвристические алгоритмы для решения задач, точные решения которых требуют экспоненциальных затрат времени.
Общепринятый метод поиска состоит в следующем.Начать следует с ряда произвольных решений, применяя к каждому из них локальные преобразования до тех пор, пока не будет получено локально-оптимальноерешение, т.е. такое, которое не сможет улучшить ни одно преобразование. Как показано на рис. 10.19, на основе большинства (или даже всех) произвольных начальных решений мы нередко будем получать разные локально-оптимальные решения.
Если нам повезет, одно из них окажется глобально-оптимальным, т.е.лучше любого другого решения.На практике мы можем и не найти глобально-оптимального решения, показанного на рис. 10.19, поскольку количество локально-оптимальных решений можетоказаться колоссальным. Однако мы можем по крайней мере выбрать локальнооптимальное решение, имеющее минимальную стоимость среди всех найденныхнами решений. Поскольку количество видов локальных преобразований, использующихся для решения различных задач, очень велико, мы завершим этот разделописанием двух примеров: задачи коммивояжера и простой задачи размещения(коммутации) блоков.Задача коммивояжера•Методы локального поиска особенно хорошо подходят для решения задачи коммивояжера.
Простейшим преобразованием, которым можно в этом случае воспользоваться, является так называемый "двойной выбор". Он заключается в том, что мывыбираем любые два ребра, например ребра (А, В) и (С, D), показанные нарис. 10.20, удаляем их и "перекоммутируем" соединявшиеся ими точки так, чтобыобразовался новый маршрут. На рис. 10.20 этот новый маршрут начинается в точке10.5.
АЛГОРИТМЫ ЛОКАЛЬНОГО ПОИСКА303В, продолжается по часовой стрелке до С, проходит по ребру (С, А), затем — противчасовой стрелки от А к D и наконец по ребру (D, В). Если сумма длин (А, С) и (В, D)оказывается меньше суммы длин (А, В) и (С, D), значит, нам удалось получитьулучшенный маршрут.1 Обратите внимание, что мы не можем соединить точки А иD, В и С, поскольку полученный результат будет являться не маршрутом, а двумяизолированными друг от друга циклами.Начальные решенияФункциястоимостиЛокально-оптимальноерешениеГлобально-оптимальноерешениеРис.
iG.iS. Локальный поиск в пространстве решенийDРис. 10.20. Двойной выборСВас не должен вводить в заблуждение рис. 10.20. Действительно, если длины ребер являются расстояниями на плоскости, тогда ребра, показанные пунктирными линиями на этом рисунке, должны быть длиннее ребер, которые мы удалили. Однако, вообще говоря, нет никакихоснований предполагать, что расстояния, показанные на рис. 10.20, обязательно должны бытьевклидовыми расстояниями, но если они и являются таковыми, то пересекающимися могли быбыть ребра (А, В) и (С, D), а не (А, С) и (В, D).304ГЛАВА 10. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВЧтобы найти локально-оптимальный маршрут, мы начинаем с какого-либо произвольного маршрута и рассматриваем все пары несмежных ребер, такие как (А, В) и(С, D) на рис.
10.20. Если данный маршрут можно улучшить путем замены этих ребер на (А, С) и (В, D), это нужно сделать, а затем продолжить рассмотрение оставшихся пар ребер. Обратите внимание, что каждое из новых ребер (А, С) и (В, D)должно образовать пару со всеми другими ребрами данного маршрута, результатомчего могут явиться дополнительные улучшения.Пример 10.12. Вернемся к рис.
10.16 и допустим, что в качестве исходноговыбран маршрут, показанный на рис. 10.21,а. Ребра (а, е) и (с, d) общей стоимостью 12 можно заменить ребрами (a, d) и (е, е) общей стоимостью 10, какпоказано на рис. 10.21,6. Затем ребра (а, Ь) и (с, е) можно заменить на ребра(а, с) и (Ь, е), что обеспечило бы нам оптимальный маршрут, показанный нарис.
10.21,в. Легко убедиться, что на этом рисунке нельзя удалить ни одну паруребер, выгодно заменив ее пересекающимися ребрами с теми же конечными точками. Возьмем хотя бы один пример: ребра (Ь, с) и (d, е) вместе имеют относительно высокую стоимость — 10. Но (с, е) и (b, d) еще хуже, поскольку их совместная стоимость равна 14. ПРис. 10.21. Оптимизация решения задачи коммивояжера посредствомдвойного выбораДвойной выбор можно обобщить как выбор k элементов для любого постоянногоft.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
