Главная Промышленная автоматика.






Рис. iO.iS. Локальный поиск минимального остовного дерева

Локальные и глобальные оптимальные решения

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

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

Задача коммивояжера

Методы локального поиска особенно хорошо подходят для решения задачи коммивояжера. Простейшим преобразованием, которым можно в этом случае воспользоваться, является так называемый "двойной выбор". Он заключается в том, что мы выбираем любые два ребра, например ребра (А, В) и (С, D), показанные на рис. 10.20, удаляем их и "перекоммутируем" соединявшиеся ими точки так, чтобы образовался новый маршрут. На рис. 10.20 этот новый маршрут начинается в точке



в, продолжается по часовой стрелке до С, проходит по ребру (С, А), затем - против часовой стрелки от А к D и наконец по ребру (D, В). Если сумма длин (А, С) и (В, D) оказывается меньше суммы длин (А, В) и (С, D), значит, нам удалось получить улучшенный маршрут/ Обратите внимание, что мы не можем соединить точки А и D, В и С, поскольку полученный результат будет являться не маршрутом, а двумя изолированными друг от друга циклами.

Начальные решения


Функция стоимости

Локально-оптимальное решение Глобально-оптимальное

решение

Рис. \0.\9. Локальный поиск в пространстве решений


Рис. 10.20. Двойной выбор

Вас не должен вводить в заблуждение рис. 10.20. Действительно, если длины ребер являются расстояниями на плоскости, тогда ребра, показанные пунктирными линиями на этом рисунке, должны быть длиннее ребер, которые мы удалили. Однако, вообще говоря, нет никаких оснований предполагать, что расстояния, показанные на рис. 10.20, обязательно должны быть евклидовыми расстояниями, но если они и являются таковыми, то пересекающимися могли бы быть ребра (А, В) и (С, D), а не (А, С) и (В, D).



Чтобы найти локально-оптимальный маршрут, мы начинаем с какого-либо произвольного маршрута и рассматриваем все пары несмежных ребер, такие как (А, В) и (С, D) на рис. 10.20. Если данный маршрут можно улучшить путем замены этих ребер на (А, С) и (В, D), это нужно сделать, а затем продолжить рассмотрение оставшихся пар ребер. Обратите внимание, что каждое из новых ребер (А, С) и (В, D) должно образовать пару со всеми другими ребрами данного маршрута, результатом чего могут явиться дополнительные улучшения.

Пример 10.12. Вернемся к рис. 10.16 и допустим, что в качестве исходного выбран маршрут, показанный на рис. 10.21,а. Ребра (а, е) и (с, <i) общей стоимостью 12 можно заменить ребрами (а, d) и (е, е) общей стоимостью 10, как показано на рис. 10.21,6. Затем ребра (а, Ь) и (с, е) можно заменить на ребра (а, с) и (Ь, е), что обеспечило бы нам оптимальный маршрут, показанный на рис. 10.21,в. Легко убедиться, что на этом рисунке нельзя удалить ни одну пару ребер, выгодно заменив ее пересекающимися ребрами с теми же конечными точками. Возьмем хотя бы один пример: ребра (Ь, с) и (d, е) вместе имеют относительно высокую стоимость - 10. Но (с, е) и (Ь, d) еще хуже, поскольку их совместная стоимость равна 14. □


Рис. 10.21. Оптимизация решения задачи коммивояжера посредством двойного выбора

Двойной выбор можно обобщить как выбор к элементов для любого постоянного ft. В этом случае мы удаляем до к ребер и "перекоммутируем" оставшиеся элементы в любом порядке, пытаясь получить какой-либо маршрут. Обратите внимание: мы не требуем, чтобы удаленные ребра вообще были несмежными, хотя в случае двойного выбора не было никакого смысла рассматривать удаление двух смежных ребер. Обратите также внимание, что при к > 2 существует несколько способов соединения частей графа. На рис. 10.22 представлен процесс тройного выбора с помощью любой из перечисленных ниже восьми совокупностей ребер.

(А F), (D, Е), (В, С)

(А, F), (С, Е), (D, В)

(А, Е), (F, D), (В, С)

(А, Е), (F, С), (В, D)

(А, D), (С, Е), (В, F)

(А, D), (С, F), (В, Е)

(А, С), (D, Е), (В, F)

(А, С), (D, F), (В, Е)

(исходный маршрут) (двойной выбор) (еще один двойной выбор)

(тройной выбор) (еще один тройной выбор) (еще один тройной выбор) (двойной выбор) (тройной выбор)





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 [97] 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0021