Структуры данных и алгоритмы (1021739), страница 78
Текст из файла (страница 78)
Обсудим один из способов определения нижней границы для определенных совокупностей решений задачи коммивояжера, причем эти совокупностипредставлены узлами на дереве решений в соответствии с рис. 10.15. Прежде всего,допустим, что требуется определить нижнюю границу для всех решений данной задачи коммивояжера. Примем во внимание, что стоимость любого маршрута можновычислить как половину суммы по всем узлам га стоимости пар ребер этого маршрута, инцидентных с узлом га. Из этого замечания можно вывести следующее правило.Сумма стоимости двух ребер, инцидентных узлу га и входящих в маршрут, не можетбыть меньше суммы двух ребер наименьшей стоимости, инцидентных узлу п. Такимобразом, ни один из маршрутов не может стоить меньше, чем половина суммы повсем узлам п стоимости двух ребер наименьшей стоимости, инцидентных узлу га.Рассмотрим, например, задачу коммивояжера, граф для которой представленна рис.
10.16. В отличие от примера, показанного на рис. 10.11, здесь мера расстояний между вершинами не является евклидовой, т.е. она никоим образом несвязана с расстоянием на плоскости между городами, соединенными ребром. Такой мерой стоимости может служить, например, время в пути или плата за проезд.
В данном случае ребрами с наименьшей стоимостью, инцидентными узлу а,являются (а, d) и (а, Ь) с суммарной стоимостью 5. Для узла Ь такими ребрами являются (а, Ъ) и (Ь, е) с суммарной стоимостью, равной 6. Аналогично, суммарнаястоимость двух ребер с наименьшей стоимостью, инцидентных узлам с, d и е, равняется соответственно 8, 7 и 9. Нижняя граница стоимости маршрута составит,таким образом, (5+6+8+7+9)/2=17.5.Допустим теперь, что нужно получить нижнюю границу стоимости для некоторого подмножества маршрутов, определяемого некоторым узлом на дереве поиска.
Еслиэто дерево поиска выглядит так, как в примере 10.8, то каждый узел представляетмаршруты, определяемые совокупностью ребер, которые должны входить в этотмаршрут, и совокупностью ребер, которые могут не входить в этот маршрут. Эти ограничения сказываются на том, какие два ребра с наименьшей стоимостью мы выбираем в каждом узле. Очевидно, что ребро, на которое накладывается ограничение,298ГЛАВА 10. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВобусловливающее наличие этого ребра в каком-либо маршруте, необходимо включитьмежду двумя выбранными ребрами независимо от того, имеют ли они наименьшую1стоимость или стоимость, ближайшую к наименьшей.
Аналогично, ребро, на которое накладывается ограничение, исключающее его из маршрута, выбрать нельзя,даже если у него наименьшая стоимость.Рис. 10.16. Граф для задачи коммивояжераТаким образом, если ограничения обязывают включить в маршрут ребро (а, е) иисключить ребро (Ь, с), то двумя ребрами для узла а будут (а, а) и (а, е), общаястоимость которых равна 9. Для узла Ь мы выбираем ребра (а, Ь) и (6, е), общаястоимость которых, как и раньше, равняется 6. Для узла с мы не можем выбратьребро (Ь, с) и поэтому выбираем ребра (а, с) и (с, d), общая стоимость которых равна9.
Для узла d мы, как и раньше, выбираем ребра (a, d) и (с, d), тогда как для узла емы должны выбрать ребро (а, е) и еще выбираем ребро (Ь, е). Таким образом, нижняя граница при ограничениях равняется (9+6+9+7+10)/2 = 20.5. ППостроим дерево поиска вдоль путей, предложенных в примере 10.8. Как и впримере, будем рассматривать ребра в лексикографическом порядке. Каждый раз,когда есть разветвление для двух сыновей какого-либо узла, мы пытаемся принятьдополнительные решения относительно того, какие ребра необходимо включить илиисключить из маршрутов, представленных соответствующими узлами.
Ниже перечислены правила, которые будем использовать для принятия этих решений.1.Если исключение ребра (ж, у) приводит к тому, что у вершины х или у нет других инцидентных ребер на данном маршруте, тогда ребро (х, у) необходимовключить.2. Если включение ребра (я, у) приводит к тому, что у вершины х или у будет болеедвух ребер на данном маршруте или образуется цикл (не совпадающий с маршрутом) с ранее включенными ребрами, тогда ребро (х, у) необходимо исключить.При разветвлении вычисляем нижние границы для обоих сыновей.
Если нижняяграница для какого-нибудь из сыновей оказывается не ниже, чем у найденного наданный момент маршрута с наименьшей стоимостью, мы можем отсечь этого сына ине рассматривать его потомков. Интересно отметить, что бывают ситуации, когданижняя граница для узла п оказывается ниже, чем наилучшее из найденных на1Правила построения дерева поиска предусматривают исключение любой совокупности ограничений, которая не позволяет получить какой-либо маршрут (например, по той причине,что этому маршруту должны принадлежать три ребра, инцидентных одному узлу).10.4. ПОИСК С ВОЗВРАТОМ299данный момент решений; тем не менее, обоих сыновей узла п можно исключить, поскольку их нижние границы оказываются выше стоимости наилучшего из найденных на данный момент решений.Если ни одного из сыновей удалить невозможно, мы применяем эвристическийприем, рассматривая сначала сына с меньшей нижней границей, в надежде быстреедостичь решения, которое окажется дешевле, чем найденное к настоящему временинаилучшее решение.
Рассмотрев одного из сыновей, мы должны еще раз проверить,нельзя ли удалить другого сына, поскольку вполне возможно, что мы нашли новое"наилучшее" решение. Для примера, показанного на рис. 10.16, мы получаем деревопоиска, представленное на рис. 10.17. Чтобы читателю было легче интерпретироватьузлы этого дерева, обращаем их внимание на то, что прописными буквами на рисунке обозначены названия узлов дерева поиска. Числа указывают нижние границы; мыперечисляем ограничения, относящиеся к соответствующему узлу, записывая ху, если ребро (х, у) нужно включить, и ху, если ребро (х, у) нужно'исключить. Обратитетакже внимание на то, что ограничения, указанные для узла, относятся и ко всемего потомкам. Таким образом, чтобы получить все ограничения, относящиеся к данному узлу, мы должны пройти путь от этого узла до корня.Наконец, следует отметить, что, как и в общем случае поиска с возвратом, мыстроим дерево узел за узлом, сохраняя только один путь, как в рекурсивном алгоритме листинга 10.3 или в его нерекурсивном двойнике.
Вероятно, предпочтениеследует все же отдать нерекурсивной версии алгоритма — это обеспечит дополнительное удобство для хранения в стеке перечня ограничений.AI3/20.5ас adаеdeedмаршрутabc eda\lX/\18.5К21ас ad аеE^Нbe сеi/В 17.£abОтсекается послер18рассмотренияасу ^узла /.^\bcbd17.5bccdcebdGac\С 18.5ab18J/23LadaeОтсекаетсяпоел крассмотренияузла /18.5ad ae/\\M 23.5adae>v>^^v>^ Отсекаетсярbccdcebddebeмаршрутмаршрутстоимость=1 9стоимость=23debeмаршрутabe cdaстоимость=23 стоимость=21ac.acb edabcbdbe cede cdace bdaРис. 10.17. Дерево поиска для задачи коммивояжераПример 10.10. На рис. 10.17 показано дерево поиска для задачи коммивояжера,соответствующей графу из рис.
10.16. Покажем, как строится это дерево. Принимаем за исходную точку корень А. Первым ребром в лексикографическом порядке бу300ГЛАВА 10. МЕТОДЫ РАЗРАБОТКИ АЛГОРИТМОВдет ребро (а, Ь), поэтому мы рассматриваем двух его сыновей В и 'С, соответствующих ограничениям аЪ и аЬ соответственно. Пока еще у нас нет наилучшего на дан1ный момент решения, поэтому придется рассматривать как узел В, так и узел С.Включение ребра (а, Ъ) в маршрут не повышает его нижнюю границу, но исключениеэтого ребра повышает ее до 18,5, поскольку два самых дешевых "законных" ребрадля узлов а и Ь теперь стоят соответственно 6 и 7 (в сравнении с 5 и 6 при отсутствии ограничений). В соответствии с нашей эвристикой мы рассмотрим сначала потомков узла В.Следующим ребром в лексикографическом порядке будет ребро (а, с).
Таким образом, мы переходим к узлам D и Е, соответствующим маршрутам, где ребро (а, с) соответственно включается или исключается. Применительно к узлу D можно сделать вывод, что ни ребро (a, d), ни ребро (а, е) не могут входить в маршрут (в противном случае узел а имел бы слишком много инцидентных ребер).
В соответствии с нашимэвристическим подходом мы рассматриваем сначала узел Е, а затем D и переходим кребру (о, d). Нижние границы для узлов F и G равняются соответственно 18 и 23. Длякаждого из этих узлов нам известны три ребра из ребер, инцидентных а, поэтому мыможем сделать определенные выводы относительно оставшегося ребра (а, е).Рассмотрим сначала сыновей узла F. Первым оставшимся ребром в лексикографическом порядке будет ребро (Ь, с). Если мы включим в маршрут это ребро, то несможем включить ребро (b, d) или (Ь, е), так как уже включили ребро (а, Ь). Поскольку мы уже исключили ребра (а, е) и (Ь, е), у нас должны быть ребра (с, е) и(d, е).
Ребро (с, d) не может входить в маршрут, иначе у вершин end три инцидентных ребра входили бы в маршрут. Остается один маршрут (а, Ь, с, е, d, а), стоимостькоторого равна 23. Аналогично можно доказать, что узел / с исключенным ребром(Ь, с) представляет лишь маршрут (а, Ь, е, с, d, а), стоимость которого равняется 21.На данный момент это маршрут с наименьшей стоимостью.Теперь возвратимся в узел Е и рассмотрим его второго сына, узел G.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
