данный момент решений; тем не менее, обоих сыновей узда п можно исключить, поскольку их нижние границы оказываются выше стоимости наилучшего из найденных на данный момент решений.

Если ни одного из сыновей удалить невозможно, мы применяем эвристический прием, рассматривая сначала сына с меньшей нижней границей, в надежде быстрее достичь решения, которое окажется дешевле, чем найденное к настояшему времени наилучшее решение. Рассмотрев одного из сыновей, мы должны еше раз проверить, нельзя ди удалить другого сьша, поскольку вполне возможно, что мы нашли новое "наилучшее" решение. Для примера, показанного на рис. 10.16, мы получаем дерево поиска, представленное на рис. 10.17. Чтобы читатедю было легче интерпретировать узды этого дерева, обращаем их внимание на то, что прописными буквами на рисунке обозначены названия уздов дерева поиска. Числа указывают нижние границы; мы перечисляем ограничения, относящиеся к соответствующему узду, записывая ху, если ребро (х, у) нужно включить, и ху, если ребро (х, у) нужноисключить. Обратите также внимание на то, что ограничения, указанные для узда, относятся и ко всем его потомкам. Таким образом, чтобы получить все ограничения, относящиеся к данному узлу, мы должны пройти путь от этого узда до корня.

Наконец, следует отметить, что, как и в общем случае поиска с возвратом, мы строим дерево узел за узлом, сохраняя только один путь, как в рекурсивном алгоритме дистинга 10.3 иди в его нерекурсивном двойнике. Вероятно, предпочтение следует все же отдать нерекурсивной версии алгоритма - это обеспечит дополнительное удобство для хранения в стеке перечня ограничений.

17.5

рассмотрения узла /

F J8 ad ае

G 23 ad ае

bcbd be се de cd маршрут abc eda

стоимость=23 стоимость=21

/ be cd се bd de be маршрут abe cda

Отсекается

ПОСЛК

рассмотрения узла /

L 18.5 ad ае

N bccd ce bd de be маршрут acb eda стоимость=19

M 23.5 ad ae

Отсекается

be bd bece de cd маршрут ace bda стоимость=23

Рис. 10.17. Дерево поиска для задачи коммивояжера

Пример 10.10. На рис. 10.17 показано дерево поиска для задачи коммивояжера, соответствующей графу из рис. 10.16. Покажем, как строится это дерево. Принимаем за исходную точку корень А. Первым ребром в лексикографическом порядке бу-

дет ребро (а, Ь), поэтому мы рассматриваем двух его сыновей В и С, соответствующих ограничениям аЬ и аЬ соответственно. Пока еще у нас нет наилучшего на данный момент рещения, поэтому придется рассматривать как узел В, так и узел С Включение ребра (а, Ъ) в марщрут не повыщает его нижнюю границу, но исключение этого ребра повыщает ее до 18,5, поскольку два самых дещевых "законных" ребра для узлов а и Ь теперь стоят соответственно 6 и 7 (в сравнении с 5 и 6 при отсутствии ограничений). В соответствии с нащей эвристикой мы рассмотрим сначала потомков узла В.

Следующим ребром в лексикографическом порядке будет ребро (а, с). Таким образом, мы переходим к узлам D и Е, соответствующим маршрутам, где ребро (а, с) соответственно включается или исключается. Применительно к узлу D можно сделать вывод, что ни ребро (а, d), ни ребро (а, е) не могут входить в марщрут (в противном случае узел а имел бы слищком много инцидентных ребер). В соответствии с нащим эвристическим подходом мы рассматриваем сначала узел Е, а затем D и переходим к ребру (о, d). Нижние границы для узлов Е и Сравняются соответственно 18 и 23. Для каждого из этих узлов нам известны три ребра из ребер, инцидентных а, поэтому мы можем сделать определенные выводы относительно оставшегося ребра (а, е).

Рассмотрим сначала сыновей узла F. Первым оставшимся ребром в лексикографическом порядке будет ребро (Ь, с). Если мы включим в маршрут это ребро, то не сможем включить ребро (Ь, d) или (Ь, е), так как уже включили ребро (а, Ь). Поскольку мы уже исключили ребра (а, е) и (Ь, е), у нас должны быть ребра (с, е) и (d, е). Ребро (с, d) не может входить в маршрут, иначе у вершин с и d три инцидентных ребра входили бы в маршрут. Остается один маршрут (а, Ь, с, е, d, а), стоимость которого равна 23. Аналогично можно доказать, что узел I с исключенным ребром (Ь, с) представляет лишь маршрут (а, Ь, е, с, d, а), стоимость которого равняется 21. На данный момент это маршрут с наименьшей стоимостью.

Теперь возвратимся в узел Е и рассмотрим его второго сына, узел G. Но нижняя граница G равняется 23, что превосходит наилучшую на данный момент стоимость - 21. Следовательно, мы удаляем узел G. Теперь возвращаемся в узел В и исследуем его второго сына, узел D. Нижняя граница для D равняется 20.5, но, так как стоимости являются целочисленными значениями, нам известно, что ни у одного из маршрутов, включающих D, стоимость не может быть меньше 21. Поскольку у нас уже имеется столь дешевый маршрут, нам не придется рассматривать потомков D, следовательно, отсекаем узел D. Теперь возвращаемся в узел А и рассматриваем его второго сына, узел С.

На уровне узла С мы рассмотрели только одно ребро (а, Ь). Узлы J п К являются сыновьями узла С. Узел J соответствует тем маршрутам, которые содержат ребро (а, с), но не содержат ребро (а, Ь), его нижняя граница равняется 18,5. Узел К соответствует тем маршрутам, которые не содержат ни ребро (а, с), ни ребро (а, Ь), отсюда следует вывод, что эти маршруты содержат ребра (а, d) и (а, е). Нижняя граница для узла Аравна 21, поэтому можем отсечь узел К, поскольку уже известен маршрут с такой стоимостью.

Далее рассматриваем сыновей узла У, которыми являются узлы L и М; мы отсекаем узел М, поскольку его нижняя граница превосходит стоимость наилучшего из найденных на данный момент маршрутов. Сыновьями узла L являются узлы N и Р, соответствующие маршрутам, которые содержат ребро (Ь, с) и исключают ребро (Ъ, с). Учитывая степень вершин и с и помня о том, что отброшенные ребра не могут образовывать цикл из менее чем всех пяти вершин, можем сделать вывод, что узлы N и Р (каждый из них) представляют отдельные маршруты. Один из них (а, с, Ь, е, d, а) имеет наименьшую среди всех маршрутов стоимость - 19. Таким образом, мы проверили все дерево и частично сократили его. D

Мы могли бы взять за исходную точку какое-либо решение, найденное эвристическим способом (например, с помощью "жадного" алгоритма), хотя для нашего примера это не имеет значения. Стоимость "жадного" решения для графа из рис. 10.16 равняется 21.

10.5. Алгоритмы локального поиска

Описанная ниже стратегия нередко приводит к оптимальному решению задачи.

1. Начните с произвольного решения.

2. Для улучшения текушего решения примените к нему какое-либо преобразование из некоторой заданной совокупности преобразований. Это улучшенное решение становится новым "текушим" решением.

3. Повторяйте указанную процедуру до тех пор, пока ни одно из преобразований в заданной их совокупности не позволит улучшить текушее решение.

Результирующее решение может, хотя и необязательно, оказаться оптимальным. В принципе, если "заданная совокупность преобразований" включает все преобразования, которые берут в качестве исходного одно решение и заменяют его каким-либо другим, процесс "улучшений" не закончится до тех пор, пока мы не получим оптимальное решение. Но в таком случае время выполнения пункта (2) окажется таким же, как и время, требующееся для анализа всех решений, поэтому описываемый подход в целом окажется достаточно бессмысленным.

Этот метод имеет смысл лишь в том случае, когда мы можем ограничить нашу совокупность преобразований небольшим ее подмножеством, что дает возможность выполнить все преобразования за относительно короткое время: если "размер" задачи равняется га, то мы можем допустить О(га) или О(га) преобразований. Если совокупность преобразований невелика, естественно рассматривать решения, которые можно преобразовывать одно в другое за один шаг, как "близкие". Такие преобразования называются "локальными", а соответствующий метод называется локальным поиском.

Пример 10.11. Одной из задач, которую можно решить именно методом локального поиска, является задача нахождения минимального остовного дерева. Локальными преобразованиями являются такие преобразования, в ходе которых мы берем то или иное ребро, не относящееся к текущему остовному дереву, добавляем его в это дерево (в результате мы должны получить цикл), а затем убираем из этого цикла в точности одно ребро (предположительно, ребро с наивысшей стоимостью), чтобы образовать новое дерево.

Рассмотрим, например, граф на рис. 10.16. Мы можем начать с дерева, показанного на рис. 10.18,а. Одно из преобразований, которые можно было бы выполнить, заключается в добавлении ребра (d, с) и устранении из образовавшегося цикла (с, а, с, d, с) какого-либо другого ребра. Если мы удалим ребро (а, с), то уменьшим стоимость дерева с 20 до 19. Это преобразование можно выполнить, получив в результате дерево (рис. 10.18,6), к которому мы опять попытаемся применить улучшающее преобразование. Одно из таких преобразований сводится к вставке ребра (а, d) и удалению из образовавшегося цикла ребра (с, d). Результат этого преобразования показан на рис. 10.18,в. Затем можно вставить ребро (а, Ь) и убрать ребро (Ь, с), как показано на рис. 10.18,г, а потом - вставить ребро (р, с) вместо ребра (d, с). Результирующее дерево (рис. 10.18,д) является минимальным. Мы можем убедиться в том, что каждое ребро, не входящее в состав этого дерева, имеет наивысшую стоимость среди всех ребер в цикле, который они с этим ребром составляют. Таким образом, к дереву на рис. 10.18,гпреобразованияуженеприменимы. D

Время, которое занимает выполнение алгоритма в примере 10.11 на графе из п узлов и с ребер, зависит от количества требующихся улучшений решения. Одна лишь проверка того факта, что преобразования уже неприменимы, может занять 0(пе) времени, поскольку для этого необходимо перебрать с ребер, а каждое из них может образовать цикл длиной примерно п. Таким образом, этот алгоритм несколько хуже, чем алгоритмы Прима и Крускала, однако он может служить примером получения оптимального решения на основе локального поиска.