Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






Розділ 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) з вартістю с2і=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).

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

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

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

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

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

 

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

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

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

hi=25

h2=5

h3=l

h4=6

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

1 2 3 4 1 2 3 4

3

22

       
   



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

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




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

<== попередня сторінка | наступна сторінка ==>
Контрольні запитання. | Контрольні запитання.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.008 сек.