§11 Метод ветвей и границ
Широкий спектр задач (не только игровых), в которых нужно найти минимальную или максимальную конфигурацию того или иного типа, поддаются решению путём поиска с возвратами, применимого к дереву возможностей.
Будем считать, что узел n дерева – некоторая совокупность конфигураций, каждый сын узла n – некоторое подмножество этой совокупности. Каждый лист – отдельное решение задачи. Каждое решение можно оценить и выяснить, не является ли оно наилучшим среди уже найденных.
Пример 1. Рассмотрим задачу коммивояжёра для следующего графа
Начало дерева решений имеет вид:
( означает, что включено в маршрут, означает, что не включено)
Метод границ
Рассмотрим способ определения нижней границы стоимости для совокупности решений задачи, представленной узлом n
1) Стоимость любого маршрута n0n1…nk можно определить как половину суммы по всем узлам стоимости ребер маршрута, инцидентных с n.
Например,
n2
c2
c3
n1
n3
c1
c4
n0
2) Далее сумма стоимостей двух рёбер инцидентных узлу ni в маршруте не может быть меньше, чем сумма стоимостей двух ребер наименьшей стоимости во всем графе, инцидентных с ni
Из 1) и 2) следует, что
Правило I. ни один из маршрутов не может стоить меньше, чем половина суммы по всем узлам n стоимости 2-х ребер наименьшей стоимости, инцидентных узлу n в графе.
Пример 2: Нижняя граница стоимости для маршрута в графе из Примера 1.
Для узла a: два ребра наименьшей стоимости из всех ребер графа ab и ad стоят 2 и 3
Для узла b: ab и be стоят 3 и 3
Для узла c: ac и bc стоят 4 и 4
Для узла d: ad и cd стоят 2 и 5
Для узла e: be и de стоят 3 и 6
Ни один из маршрутов в графе не может стоить меньше, чем
3) Получим нижнюю границу стоимости не всего множества маршрутов, а некоторого их подмножества, определяемого узлом дерева из Примера 1.
Например, узлом – маршруты, содержащие ac и не содержащие ab.
Для этого в правиле I при выборе двух ребер наименьшей стоимости, инцидентных какому-нибудь узлу никогда не выбирается ab и обязательно включается ac, если оно инцидентно данному узлу.
Пример 3: Нижняя граница стоимости маршрутов узла J дерева решений из Примера 1.
Для узла a: два ребра наименьшей стоимости ad и ac стоят 2 и 4 (ab брать нельзя, ac - включать обязательно).
Для узла b: be и bc стоят 3 и4 (ab брать нельзя).
Для узла c: ac и bc стоят 4 и 4 (ac включать обязательно).
Для узла d: ad и cd стоят 2 и 5.
Для узла e: be и de стоят 3 и 6.
Таким образом, нижняя граница стоимости любого маршрута, содержащего ac и не содержащего ab равна
Метод ветвей. При построении дерева решений при каждом разветвлении (определении 2-х сыновей данного узла) принимается решение о том, какие ребра необходимо включить или исключить из маршрутов представленных этими сыновьями используются правила:
Правило II.
a) Если исключение ребра {x,y} приводит к тому, что у вершины x или y нет двух инцидентных ребер на данном маршруте, тогда {x,y} необходимо включить
б) Если включение ребра {x,y} приводит к тому, что у вершины x или y будет более 2-х инцидентных ребер на данном маршруте или образуется цикл, не являющийся искомым маршрутом, ребро {x,y} необходимо исключить.
Комбинированный метод ветвей и границ. При разветвлении с учетом правил II вычисляется нижняя граница каждого сына данного узла n. Если нижняя граница какого-нибудь из них (или обоих) окажется не ниже, чем найденное на данный момент наилучшее решение с min стоимостью, этот сын отсекается.
Если ни одного из сыновей отсечь нельзя, применяется эвристический прием – рассмотрение сначала сына с наименьшей нижней границей.
Пример 3: Построим дерево решений для задачи из примера 1 и найдем оптимальное решение методом ветвей и границ.
Ребра для ветвлений выбираем в лексикографическом порядке: ab, ac, ad, ae, bc, bd, be, cd, ce, de, …
Узел А: Все маршруты графа. Нижняя грань стоимости 17,5 (см. пример 2).
Узел В: Маршруты, включающие ab. Два ребра наименьшей стоимости
для узла a: ab, ad стоят 3 и 2;
для узла b: ab, be стоят 3 и 3;
для узла c: bc, ac стоят 4 и 4;
для узла d: ad, cd стоят 2 и 5;
для узла e: be, de стоят 3 и 6.
Нижняя граница стоимости любого маршрута узла В: .
Узел С: маршруты не включающие ab Два ребра наименьшей стоимости
для a: ad, ac стоят 2 и 4 (ab брать нельзя);
для b: be, bc стоят 3 и 4;
для c: bc, ac стоят 4 и 4;
для d: ad, cd стоят 2 и 5;
для e: be, de стоят 3 и 6.
Нижняя граница для узла С: 18.5.
Так как пока полностью не найдено ни одно решение, чтобы в сравнении с ним отсечь В или С, рассмотрим сыновей обоих узлов, причем вначале В, так как его граница меньше.
Узел D: маршруты, включающие ab и включающие ac. Согласно правилу II, в них нельзя включать ad и ae, иначе d(a)>2. Значит, для данного узла необходимо также и . Два ребра наименьшей стоимости
для a: ab, ac стоят 3 и 4 (ab, ac обязательны);
для b: ab,be стоят 3 и 3 (ab обязательно);
для c: ac, bc стоят 4 и 4 (ac обязательно);
для d: bd, cd стоят 6 и 5 (ad брать нельзя);
для e: be, de стоят 3 и 6 (ae брать нельзя).
Нижняя граница для узла D: 20.5.
Узел E: маршруты, включающие ab, но не включающие ас. Два ребра наименьшей стоимости
для а: аb и ad стоят 3 и 2 (аb обязательно, ас включать нельзя);
для в: аb и bе стоят 3 и 3;
для с: bс и сd стоят 4 и 5 ( ас включать нельзя);
для d: ad и cd стоят 2 и 5;
для е: bс и de стоят 3 и 6.
Нижняя граница для узла Е: 18.
Пока ни одно из решений не найдено, нельзя в сравнении с ним отсечь ни D ни Е. Начнем рассматривать сыновей узла наименьшей стоимости из них: Е.
Узел F: маршруты, включающие ab, но не включающие и включающие ad. Согласно правилу II, не может включаться ае, иначе d(а)>2. Следовательно, для данного узла также требуется . Два ребра наименьшей стоимости
для а: ab и аd стоят 3 и 2
для b: аb и bе стоят 3 и 3
для с: сb и сd стоят 4 и 5
для d: ad и сd стоят 2 и 5
для e: be и de стоят 3 и 6
Нижняя границ для F: 18.
Узел G: маршруты, для которых аb , . Тогда необходимо ае включить, иначе d(a)=1.
для а: ab и ae стоят 3 и 7;
для b: ab и be стоят 3 и 3;
для c: bc и cd стоят 4 и 5;
для d: cd и bd стоят 5 и 6;
для e: ae и be стоят 7 и 3.
Нижняя граница для G: 23.
Так как не найдено ни одного из окончательных решений, в сравнении с которым можно отсечь F или G, рассмотрим сыновей обоих узлов, начнем с F.
Узел H: маршруты, для которых ab, , ad, , bc. Применим правило II. Необходимо также иначе d(b)>2.
Необходимо ce и de, иначе d(e)<2 .
Так как включены bc и ce, требуется , иначе d(c)>2.
Таким образом, все условия для узла H: ab, , ad, , bc, , , ce, de, . Они определяют единственный маршрут ab, bc, ce, ed, da. Стоимость этого маршрута 3+4+8+6+2=23 – одно из окончательных решений.
Узел I: маршруты, для которых ab, , ad, , . Применим правило II. Необходимо cd и ce, иначе d(c)<2.
Так как есть ad и cd, значит, требуется и , иначе d(d)>2.
Учитывая , ce включаем be, иначе d(е)<2.
Таким образом, все условия для узла I: ab, , ad, , , cd, ce, , , be. Они определяют единственный маршрут ab, be, ec, cd, da. Стоимость этого маршрута 3+3+8+5+2=21 – окончательное решение.
После рассмотрения I со стоимостью 21 отсекается узел H (стоимость 23), отсекается узел G все его потомки, так как их наименьшая стоимость равна 23, отсекается узел D и все его потомки, так как их нижняя граница стоимости 20.5, а с учетом того, что стоимость – целое число, она равна 21. Это эквивалентно уже найденному решению I. Наилучшее решение на этом этапе I со стоимостью 21.
Правая ветвь дерева строится аналогично (см. рис.3).
Оценивается
С – нижняя граница = 18,5.
J – нижняя граница = 18,5 (см. пример 3).
К – нижняя граница =21 (отсекается, так как это эквивалентно I).
L - нижняя граница =18,5.
М - нижняя граница =23,5 (отсекается, так как стоимость больше, чем у I).
N – стоимость окончательного маршрута acbeda =19.
Р - стоимость окончательного маршрута acbeda =23 – отсекается, так как стоимость больше, чем у N.
После нахождения N (стоимость 19), отвергается маршрут I (стоимость 21).
Ответ: маршрут наименьшей стоимости acbeda, стоимости 19.