трусики женские украина

На головну

Метод гілок і меж - Інформатика

Загальний опис методу гілок і меж організації повного перебору можливостей.

Рішення задачі про комівояжера методом гілок і меж: основна схема.

Нехай - кінцеве безліч і - матеріально-значна функція на ньому; вимагається

знайти мінімум цієї функції і елемент множини, на якому цей мінімум

досягається.

Коли є та чи інша додаткова інформація про безлічі, вирішення цієї

завдання іноді вдається здійснити без повного перебору елементів всієї множини

M. Але частіше

всього повний перебір виробляти доводиться . У цьому випадку обов'язково виникає

задача, як краще організувати перебір.

Метод гілок і меж - це один з методів організації повного перебору. Він

застосуємо не завжди, а тільки тоді, коли виконуються специфічні

додаткові умови на безліч M і мінімізіруемую на ньому функцію. А саме,

-

припустимо, що є матеріально-значна функція j на безлічі підмножин

безлічі M з наступними двома властивостями:

для (тут - безліч, що складається з єдиного елемента);

2) якщо і, то.

У цих умовах можна організувати перебір елементів множини M з метою

мінімізації функції на цій безлічі так:

розіб'ємо безліч M на частини (будь-яким способом) і виберемо ту з його частин W1, на

якої функція j мінімальна; потім розіб'ємо на кілька частин безліч W1 і

виберемо ту з його частин W2, на якій мінімальна функція j; потім розіб'ємо W2

на кілька частин і виберемо ту з них, де мінімальна j, і так далі, поки не

прийдемо до якогось одноелементна безлічі.

Це одноелементні безліч називається рекордом.

Функція j, якої ми при цьому виборі користуємося, називається оціночної.

Очевидно, що рекорд не зобов'язаний доставляти мінімум функції f; проте, ось яка

можливість виникає скоротити перебір за сприятливих обставин.

Описаний вище процес побудови рекорду складався з послідовних етапів, на

кожному з яких фіксувалося кілька множин і вибиралося потім одне з

них. Нехай - підмножини множини M, що виникли на передостанньому етапі

побудови рекорду, і нехай безліч виявилося обраним за допомогою оціночної

функції. Саме при розбитті і виник рекорд, який зараз для

визначеності позначимо через. Відповідно до сказаного вище,,; крім того, по

визначення оціночної функції,.

Припустимо, що; тоді для будь-якого елементу m безлічі M, що належить

безлічі, будуть вірні нерівності; це означає, що при повному переборі

елементів з M елементи з вже взагалі не треба розглядати. Якщо ж

нерівність не буде виконана, то всі елементи з треба послідовно

порівняти з знайденим рекордом і як тільки відшукається елемент, що дає меншу

значення оптимизируемой функції, треба їм замінити рекорд і продовжити перебір.

Остання дія називається поліпшенням рекорду.

Слова метод гілок і меж пов'язані з природною графічної інтерпретацією

всього викладеного: будується багаторівневе дерево, на нижньому поверсі якого

розташовуються елементи множини M, на якому гілки ведуть до рекорду і його

поліпшень і на якому частина гілок залишаються "обірваними", тому що їх

розвиток виявилося недоцільним.

Ми розглянемо зараз перший з двох запланованих у цьому курсі прикладів

застосування методу гілок і меж - рішення задачі про комівояжера. Ось її

формулювання.

Є декілька міст, з'єднаних деяким чином дорогами з відомою

довжиною; потрібно встановити, чи є шлях, рухаючись по якому можна

побувати в кожному місті тільки один раз і при цьому повернутися в місто, звідки

шлях був початий ("обхід комівояжера "), і, якщо такий шлях є, встановити

найкоротший з таких шляхів.

Формалізуємо умова в термінах теорії графів. Міста будуть вершинами графа, а

дороги між містами - орієнтованими (спрямованими) ребрами графа, на

кожному з яких задана вагова функція: вага ребра - це довжина відповідної

дороги. Шлях, який потрібно знайти, це - орієнтований остовно простий

цикл мінімальної ваги в орграфе (нагадаємо: цикл називається остовне, якщо він

проходить по всіх вершин графа; цикл називається простим, якщо він проходить по

кожній своїй вершині тільки один раз; цикл називається орієнтованим, якщо

початок кожного наступного ребра збігається з кінцем попереднього; вага циклу -

це сума ваг його ребер; нарешті, орграф називається повним, якщо в ньому є

всі можливі ребра); такі цикли називаються також гамильтоновой.

Очевидно, в повному Орграф цикли зазначеного вище типу є. Зауважимо, що питання

про наявність в орграфе Гамільтона циклу досить розглянути як окремий випадок

задачі про комівояжера для повних орграфов. Дійсно, якщо даний орграф не «*******> є повним, то його можна доповнити до повного відсутніми ребрами і

кожному з доданих ребер приписати вага ?, вважаючи, що ? - це "комп'ютерна

нескінченність", тобто максимальне з усіх можливих у розглядах чисел. Якщо

у новозбудованому повному Орграф знайти тепер найлегший гамильтонов цикл, то

за наявності у нього ребер з вагою ? можна буде говорити, що в даному, початковому

графі "циклу комівояжера" немає. Якщо ж в повному Орграф найлегший гамильтонов

цикл виявиться кінцевим за вагою, то він і буде шуканим циклом у вихідному графі.

Звідси випливає, що задачу про комівояжера досить вирішити для повних орграфов

з ваговою функцією. Сформулюємо тепер це в остаточному вигляді:

нехай - повний орієнтований граф і -

вагова функція; знайти простий остовнийоріентірованний цикл ("цикл

комівояжера") мінімальної ваги.

Нехай конкретний склад безлічі вершин і

- вагова матриця даного орграфа, т.е.

причому для будь-кого.

,

Розгляд методу гілок і меж для вирішення задачі про комівояжера зручніше

всього проводити на тлі конкретного прикладу. Користуючись введеними тут

позначеннями, ми проводимо цей опис в наступній лекції.

Введемо деякі терміни. Нехай є деяка числова матриця. Привести

рядок цієї матриці означає виділити в рядку мінімальний елемент (його називають

константою приведення) і відняти його з усіх елементів цього рядка. Очевидно, в

результаті в цьому рядку на місці мінімального елемента виявиться нуль, а всі

інші елементи будуть невід'ємними. Аналогічний сенс мають слова

привести стовпець матриці.

Слова привести матрицю по рядках означають, що всі рядки матриці наводяться.

Аналогічний сенс мають слова привести матрицю по стовпцях.

Нарешті, слова привести матрицю означають, що матриця спочатку наводиться по

рядкам, а потім наводиться за стовпцями.

Вагою елемента матриці називають суму констант приведення матриці, яка

виходить з даної матриці заміною обговорюваного елемента на ?. Отже,

слова найважчий нуль в матриці означають, що в матриці підрахований вага кожного

нуля, а потім фіксований нуль з максимальною вагою.

Приступимо тепер до опису методу гілок і меж для вирішення задачі про

коммивояжере.

Перший крок. Фіксуємо безліч всіх обходів комівояжера (тобто всіх простих

орієнтованих остовних циклів). Оскільки граф - повний, це безліч

завідомо не порожньо. Зіставимо йому число, яке буде грати роль значення на

цій множині оціночної функції: це число дорівнює сумі константприведення

даної матриці ваг ребер графа. Якщо безліч всіх обходів комівояжера

позначити через G, то суму констант приведення матриці ваг позначимо через

j (G). Наведену матрицю ваг даного графа слід запам'ятати; позначимо її

через M1; таким чином, підсумок першого кроку:

безлічі G всіх обходів комівояжера зіставлене чис-ло j (G) і матриця M1.

Другий крок. Виберемо в матриці M1 найважчий нуль; нехай він стоїть в клітці;

фіксуємо ребро графа і розділимо безліч G на дві частини: на частину, що складається

з обходів, які проходять через ребро, і на частину , що складається з обходів,

які не проходять через ребро.

Зіставимо безлічі наступну матрицю M1,1: в матриці M1 замінимо на ? число в

клітці. Потім в отриманій матриці викреслимо рядок номер i і стовпець номер j,

причому у залишилися рядків і стовпців збережемо їх вихідні номери. Нарешті,

приведемо цю останню матрицю і запам'ятаємо суму констант приведення. Отримана

наведена матриця і буде матрицею M1,1; щойно запомненную суму констант

приведення додамо до j (G) і результат, що позначається надалі через j (),

порівняти безлічі.

Тепер безлічі теж зіставимо якусь матрицю M1,2. Для цього в матриці M1

замінимо на ? число в клітці і отриману в результаті матрицю наведемо. Суму

константприведення запам'ятаємо, а отриману матрицю позначимо через M1,2.

Додамо запомненную суму констант приведення до числа j (G) і отримане число,

що у подальшому буде через j (), порівняти безлічі.

Тепер виберемо між множинами і те, на якому мінімальна функція j (т.е.

то з множин, якому відповідає менше з чисел j () і j ().

Зауважимо тепер, що в проведених міркуваннях використовувався як

вихідного тільки один фактичний об'єкт - наведена матриця ваг даного

орграфа.По ній було виділено певний ребро графа і були побудовані нові

матриці, до яких, звичайно, можна все те ж саме застосувати.

При кожному такому повторному застосуванні буде фіксуватися чергове ребро графа.

Домовимося про наступній дії: перед тим, як в черговий матриці викреслити

рядок і стовпець, в ній треба замінити на ? числа у всіх тих клітинах, які

відповідають ребрам, завідомо не належить тим гамільтоновим циклам,

які проходять через вже відібрані раніше ребра.

До обраному безлічі з зіставленими йому матрицею і числом j повторимо все те

ж саме і так далі, поки це можливо.

Доводиться, що в результаті вийде безліч, що складається з єдиного

обходу комівояжера, вага якого дорівнює чергового значенню функції j; таким

чином, виявляються виконаними всі умови, що обговорювалися при описі методу

гілок і меж.

Після цього здійснюється поліпшення рекорду аж до отримання остаточного

відповіді.

(999 999)

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

8ref.com

© 8ref.com - українські реферати


енциклопедія  бефстроганов  рагу  оселедець  солянка