Реферати українською » Информатика » Метод гілок і національних кордонів


Реферат Метод гілок і національних кордонів

Загальне опис методу гілок і національних кордонів організації повного перебору можливостей.
Рішення завдання про коммивояжере методом гілок і національних кордонів: основна схема.
Нехай - кінцеве безліч і - вещественно-значная функція у ньому; потрібно
знайти мінімум цієї функції і елемент безлічі, у якому цього
досягається.
Коли є та чи інша додаткову інформацію про безліч, розв'язання цієї
завдання іноді доводиться робити без повного перебору елементів всього безлічі
M. Але найчастіше
всього повний перебір виробляти доводиться. І тут обов'язково виникає
завдання, як їм краще перебір організувати.
Метод гілок і національних кордонів - це з методів організації повного перебору. Він
застосуємо який завжди, лише тоді, коли виконуються специфічні
додаткові умови силою-силенною M і минимизируемую у ньому функцію. Як-от,
-
припустимо, що є вещественно-значная функція j на безлічі підмножин
безлічі M з такими двома властивостями:
для (тут - безліч, що складається з єдиного елемента );
2) як і , то .
У умовах то можна організувати перебір елементів безлічі M із єдиною метою
мінімізації функції у цьому безлічі так:
розіб'ємо безліч M на частини (у будь-який спосіб) і виберемо ту з його частин W1, на
якої функція j мінімальна; потім розіб'ємо сталася на кілька частин безліч W1 і
виберемо ту з його частин W2, де мінімальна функція j; потім розіб'ємо W2
сталася на кілька частин 17-ї та виберемо ту їх, де мінімальна j, тощо, доки
то дійдемо якомусь одноэлементному безлічі .
Це одноэлементное безліч називається рекордом.
Функція j, якої ми у своїй виборі користуємося, називається оцінної.
Вочевидь, що рекорд зобов'язаний доставляти мінімум функції f; проте, ось яка
можливість виникає скоротити перебір за сприятливих обставин.
Описаний вище процес побудови рекорду складалася з послідовних етапів, на
кожному у тому числі фіксувалося кілька множин і вибиралося потім одна з
них. Нехай - підмножини безлічі M, виниклі на передостанньому етапі
побудови рекорду, і нехай безліч виявилося обраним з допомогою оцінної
функції. Саме за розбивці і з'явилася рекорд, що зараз для
визначеності позначимо через . Відповідно до сказаного вище, , ; ще, по
визначенню оцінної функції, .
Припустимо, що ; для будь-якого елемента m безлічі M, належить
безлічі , будуть вірні нерівності; це що означає, що з повному переборі
елементів з M елементи з вже занадто зайве розглядати. Якщо ж
нерівність нічого очікувати виконано, усі елементи з треба послідовно
порівняти з знайденим рекордом і тільки знайдеться елемент, дає менше
значення оптимизируемой функції, треба їм замінити рекорд та продовжити перебір.
Остання дія називається поліпшенням рекорду.
Слова метод гілок і національних кордонів пов'язані з природною графічної інтерпретацією
всього викладеного: будується багаторівневе дерево, на нижньому поверсі якого
розташовуються елементи безлічі M, у якому галузі ведуть до рекорду та її
поліпшень і якому частина гілок залишаються “обірваними”, що їх
розвиток виявилося недоцільним.
Ми розглянемо зараз перший із двох що у цьому курсі прикладів
застосування методу гілок і національних кордонів - вирішення завдання про коммивояжере. Ось її
формулювання.
Є кілька міст, з'єднаних певним чином шляхами з відомою
довжиною; потрібно встановити, чи є шлях, рухаючись у якому можна
побувати у кожному місті лише одне разів, і у своїй повернутися до місто, звідки
шлях було розпочато (“обхід комівояжера”), і, якщо він шлях є, встановити
найкоротший з цих шляхів.
Формализуем умова в термінах теорії графів. Міста будуть вершинами графа, а
дороги між містами - орієнтованими (спрямованими) ребрами графа, на
кожному у тому числі задана вагова функція: вагу ребра - це довжина відповідної
дороги. Шлях, потрібного знайти, це - орієнтований остовный простий
цикл мінімального ваги в орграфе (нагадаємо: цикл називається остовным, коли він
відбувається за всім вершин графа; цикл називається простим, коли він відбувається за
кожну лінію своєї вершині лише одне раз; цикл називається орієнтованим, якщо
початок кожного наступного ребра збігаються з кінцем попереднього; вагу циклу -
це сума терезів його ребер; нарешті, орграф називається повним, якщо у неї є
всіх можливих ребра); такі цикли називаються також гамильтоновыми.
Вочевидь, у його орграфе цикли вищезазначеного типу є. Зауважимо, що питання
про наявність у орграфе гамильтонова циклу досить розглянути як окреме питання
завдання про коммивояжере для повних орграфов. Справді, якщо це орграф не
є повним, його можна доповнити до відсутніми ребрами і
кожному з доданих ребер приписати вагу

Схожі реферати:

  • Реферат на тему: Intel
    Знайомтеся, це Усі, хто хоч колись стоїть перед поняттям персонального комп'ютера, однак добре
  • Реферат на тему: Основи соціальної інформатики
    Тема 1 Соціальна інформатика: предмет і завдання курсу Людство неминуче входить у інформаційну
  • Реферат на тему: Віруси
    на ПК. Запровадження. 20-ті століття, безсумнівно, одна із поворотних етапів у людства. Як сказав
  • Реферат на тему: Візуальне програмування в Delphi
    Вивчення методів візуального програмування в Delphi. Завдання: Побудувати графіки функцій ; ; Текст
  • Реферат на тему: Windows
    NT - OC нової генерації ! На цей час світова комп'ютерна індустрія розвивається дуже стрімко.

Навігація