• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Розділ 3. Метод гілок і меж

Метод, відомий як метод гілок і меж, схожий на методи с відходами назад тим, що він досліджує деревоподібну модель простору рішень і застосується для широкого кола дискретних комбінаторних задач. Алгоритми с відходами націлені на те, щоб знайти одну чи всі конфігурації, що модулюються N-векторами, які задовольняють визначеним властивостям. Алгоритми гілок та меж орієнтовані в більшому ступені на оптимізацію. У задачі.що розв'язується, визначена числова функція вартості для кожної з вершин, що з'являються в дереві пошуку. Мета — знайти конфігурацію, на який функція вартості досягає максимального чи мінімального значення.

Алгоритм гілок та меж добре працює в задачі комівояжера. За допомогою алгоритмів гілок та меж можна вирішити велике коло різноманітних серйозних практичних задач , ці алгоритми рідко виявляються простими.

Задача називається симетричної, якщо сij=сji для всіх і і j, тобто якщо вартість проїзду між кожними двома містами не залежить від напрямку.

Алгоритми гілок та меж для задачі комівояжера можуть бути сформульовані різними способами. Автори алгоритму, що викладається -Литл, Мерти, Суини і Карел. Це свого роду класика.

По-перше, розглянемо розгалуження. На Рис. 3.1, а показана матриця вартості для асиметричної (несиметричної) задачі комівояжера с п'ятьма містами, представленої на Рис. 3.1, б. Зверніть увагу на те, що ми користаємося спрямованою мережею, щоб вказати вартості, тому що вартість проїзду з міста і прямо в місто j не обов'язково така ж, як вартість проїзду з міста / у місто і. Корінь нашого пошукового дерева буде відповідати множині «усіх можливих турів», ця вершина представляє множину усіх 4! Можливих турів у нашій задачі с п'ятьма містами. У загальному випадку для будь-якої асиметричної задачі с N містами корінь буде представляти повна множина R усіх (N-1)! можливих турів. Гілки, що виходять з кореня, визначаються вибором одного ребра, скажемо (i,j). Наша мета полягає в тому, щоб розділити множиниусіх турів на дві множини: одну, яка, дуже імовірно, містить оптимальний тур, і іншу, котра, імовірно, не містить. Для цього вибираємо ребро (і,1); воно, як ми сподіваємося, входить в оптимальний тур, і розділяємо R на дві множини {і, j} і {і, j}. У множині

{і, j} входять тури з R, що містять ребро (і, j), а в { і, j} — не утримуючі (і, j).

Рис.3.1. Задача комівояжера (а) матриця вартості

Рис.3.1. Задача комівояжера (б) мережа з п'яти міст

Припустимо, у нашому прикладі ми робимо розгалуження на ребрі (і, j)=(3,5), що має найменшу вартість у всій матриці. Корінь і перший рівень дерева простору рішень будуть тоді такими, як показано на Рис. 3.2.

Помітимо, що кожен тур з R

Рис.3.2. Побудова дерева пошуку по методу гілок та меж.

міститься тільки в одній множині рівня 1. Якби ми якось могли зробити висновок, що множина {3,5} не містить оптимального туру, то нам потрібно було б досліджувати тільки множину (3, 5}.

Потім розділяємо множину {3, 5} у такий же спосіб, як і множину R. Наступне дешеве ребро в матриці — це ребро (2, 1) з вартістю с₂і=5. Тому можна розділити множину {3, 5} на тури, що включають ребро (2, 1), і тури, що не включають цього ребра; це показано на рівні 2 на рис. 3.2. Шлях від кореня до будь-якої вершини дерева виділяє визначені ребра, що чи повинні не повинні бути включені в множину, представлену вершиною дерева. Наприклад, ліва вершина рівня 2 на рис. 3.2 представляє множина усіх турів, що містять ребро (3, 5) і не утримуючих ребер

(2, 1). Узагалі, якщо X — вершина дерева, а (і, j) — ребро розгалуження, то позначимо вершини, що безпосередньо випливають за X, через Y і Y. Множина У позначає підмножину турів з X с ребром (і, j), а множина Y — підмножину X без (і, j).

С кожною вершиною дерева ми зв'язуємо нижню межу вартості будь-якого туру з множиною, представленого вершиною. Обчислення цих нижніх меж — основний фактор, що дає економію зусиль у будь-якому алгоритмі типу гілок та меж. Тому особлива увага варто приділити одержанню як можна більш точних меж. Причина цього наступна. Припустимо, що ми побудували конкретний повний тур з вартістю т. Якщо нижня межа, зв'язана с множиною турів, представлених вершиною п, дорівнює М>т, то до кінця процесу пошуку оптимального туру не потрібно розглядати вершину v_k і всі наступні за нею.

Основний крок при обчисленні нижніх меж відоме як приведення. Воно асновано на наступних двох розуміннях:

1. У термінах матриці вартостей С кожен повний тур містигь тільки один елемент (ребро і відповідну вартість) з кожного стовпця і кожного рядка. Помітимо, що зворотне твердження не завжди вірне. Множина, що містить один і тільки один елемент із кожного рядка і з кожного стовпця С, не обов'язково представляє тур.

2. Якщо відняти константу h з кожного елемента якогось чи рядка стовпця матриці вартостей С, то вартість будь-якого туру при новій матриці С рівно на h менше вартості того ж туру при матриці С. Оскільки будь-який тур повинний містити ребро з даного рядка чи даного стовпця, вартість усіх турів зменшується на h. Це віднімання називається приведенням рядка (чи стовпця).

Нехай t — оптимальний тур при матриці вартості С. Тоді вартістю туру t буде

Якщо С` виходить з С приведенням рядка (чи стовпця), то t повинний залишитися оптимальним туром при С`і

z(t)=h+z'(t),

де z'(t) — вартість туру t при С`

h4=6

h₅=7

h6 h7 h8 h9 h10

=0 =0 =0 =3 =0

h=25+5+ 1+6+7+3=47

Рис. 3.3. Приведення матриці вартості, показаної на Рис. 3.1, а.

Під приведенням усієї матриці вартості С розуміється наступне. Послідовно проходимо рядка С і віднімаємо значення найменшого елемента hi кожного рядка з кожного елемента цього рядка. Потім того ж саме робимо для кожного стовпця. Якщо для деякого чи стовпця рядка hj=0, то розглянутий чи стовпець рядок уже приведеш, і тоді переходимо до наступного рядка чи стовпчика. Покладемо

h =

Отриману в результаті матрицю вартості назвемо приведеної з С. На Рис. 3.3 показане приведення матриці вартості, зображеної на Рис. 3.1, а. Значення hi дані наприкінці кожного рядка і стовпця (рядка і стовпчики послідовно перенумеровані).

Загальне приведення складає Н=47 одиниць. Отже, нижня межа вартості будь-якого туру з R також дорівнює 47,

z(t) = h+z`(t)>h=47

тому що z' (t)>0 для будь-якого туру t при приведеній матриці С`. Ця межа зазначена біля кореня дерева на Рис. 3.2.

Розглянемо нижні границі для вершин рівня 1, тобто для множин {3, 5} і {3, 5}. Будемо працювати с приведеною матрицею, зображеної на Рис 3.3., маючи на увазі, що значення 47 повинне бути додане до вартості оптимального туру t при С` для того, щоб одержати дійсну вартість t при С.

По визначенню ребро (3, 5) міститься в кожнім турі множини {3, 5}. Цей факт перешкоджає вибору ребра (5, 3), тому що ребра (3, 5) і (5, 3) утворять цикл, а це не допускається ні для якого туру.

Ребро (5, 3) виключаємо з розгляду, поклавши с₅₃=. Рядок 3 і стовпець 5 також можна виключити з подальшого розгляду стосовно множини {3,5}, тому що вже є ребро з 3 у 5. Частина приведеної матриці вартості, показаної на Рис. 3.3, що буде хоч скільки-небудь корисна для подальшого пошуку на множині турів {3, 5}, показана на Рис3.4, а. Вона може бути приведена до матриці вартості, показаної на Рис. 3.4 б з h= 15. Тепер нижня межа для будь-якого туру з множини {3, 5} дорівнює 47+15=62; вона зазначена біля вершини {3, 5} на Рис. 3.2.

Нижня межа для множини {3, 5} виходить трохи іншим способом. Ребро (3, 5) не може знаходитися в цій множині, при цьому припустимо с₃5=в матриці, зображеної на Рис. 3.3. У будь-який тур з {3, 5} буде входиш якесь ребро з міста 3 і якесь ребро до міста 5. Найдешевше ребро з міста 3, крім старого значення (3, 5), має вартість 2, а найдешевше ребро до міста 5 м вартість 0. Отже, нижня межа будь-якого туру в множині {3,5} дорівнює 47+2+0=49; це зазначено біля вершини {3, 5} на Рис. 3.2.

			3
			22

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

1. D) методу мозкового штурму.
2. H) інноваційний менеджмент – це сукупність організаційно-економічних методів управління всіма стадіями інноваційного процесу.
3. I Метод Шеннона-Фано
4. I. Метод рiвних вiдрiзкiв.
5. VII. Нахождение общего решения методом характеристик
6. А. науковий факт, b. гіпотеза, с. метод
7. Аварійно-рятувальні підрозділи Оперативно-рятувальної служби цивільного захисту, їх призначення і склад.
8. Автоматизація водорозподілу на відкритих зрошувальних системах. Методи керування водорозподілом. Вимірювання рівня води. Вимірювання витрати.
9. Агрегативна стійкість, коагуляція суспензій. Методи отримання.
10. АгротехнІЧНИЙ метод
11. Адаптовані й специфічні методи дослідження у журналістикознавстві
12. Адміністративні (прямі) методи регулювання.

Переглядів: 2970