A) Если исключение ребра {x,y} приводит к тому, что у вершины x или y нет двух инцидентных ребер на данном маршруте, тогда {x,y} необходимо включить

б) Если включение ребра {x,y} приводит к тому, что у вершины x или y будет более 2-х инцидентных ребер на данном маршруте или образуется цикл, не являющийся искомым маршрутом, ребро {x,y} необходимо исключить.

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

Если ни одного из сыновей отсечь нельзя, применяется эвристический прием – рассмотрение сначала сына с наименьшей нижней границей.

Пример 3: Построим дерево решений для задачи из примера 1 и найдем оптимальное решение методом ветвей и границ.

H ab,, ad,, bc,,, ce, de,

I ab,, ad,,, cd, ce,,, be

C 18,5

K,, ad, ae 21

J, ac 18,5

A 17,5

B ab 17,5

G ab,

F ab, ad,

E ab,

D ab, ac, , 20,5

M, ac, , ae 23,5

L, ac, ad, 18,5

N, ac, ad,, bc, be, de,

P, ac, ad,,, bd, be,,, ce

abceda

acebda

acbeda

abecda

Ребра для ветвлений выбираем в лексикографическом порядке: 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.

Дата добавления: 2014-01-04