Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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





Помощь в написании учебных работ
1500+ квалифицированных специалистов готовы вам помочь

б) Если включение ребра {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 и стоят 3 и 3;

для с: и сd стоят 4 и 5 ( ас включать нельзя);

для d: ad и cd стоят 2 и 5;

для е: и de стоят 3 и 6.

Нижняя граница для узла Е: 18.

Пока ни одно из решений не найдено, нельзя в сравнении с ним отсечь ни D ни Е. Начнем рассматривать сыновей узла наименьшей стоимости из них: Е.

Узел F: маршруты, включающие ab, но не включающие и включающие ad. Согласно правилу II, не может включаться ае, иначе d(а)>2. Следовательно, для данного узла также требуется . Два ребра наименьшей стоимости

для а: ab и аd стоят 3 и 2

для 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; Просмотров: 413; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:

  1. Cущность и необходимость межбанковского кредита.
  2. Аминокислота глицин — основной ингибирующий нейромедиатор спинного мозга. В тканях мозга его немного, но это небольшое количество совершенно необходимо.
  3. Биологическое значение митоза- этот тип деления приводит к распределению наследственного материала, по дочерним клеткам поровну.
  4. Будова ребра.
  5. В течение всей истории планеты ее заселение было максимально возможным для живого вещества, которое тогда существовало.
  6. Возникла необходимость в создании в стране специальной службы, способной успешно решать задачи медико-санитарного обеспечения населения мирного времени.
  7. Выделим важные отличительные особенности, которые необходимо учитывать при создании имиджа политического лидера.
  8. Высота с вершины прямого угла
  9. Давлением на данном участке поверхности называют отношение величины силы , оказывающей давление на данном участке к площади этого участка .
  10. Даже после появления устойчивого желаемого поведения необходимо его последующее регулярное подкрепление.
  11. Деление отрезка в заданном отношении

studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.034 сек.