Лекции по обчислювальної математике

Обчислювальна математика.

Спеціальність ПО.

5-ї семестр

Конспект лекций.

Лекція 1.

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

Нехай [pic]- кінцеве безліч і [pic] - ве-щественно-значная функція у ньому; потрібно знайти мінімум цієї функції і елемент безлічі, у якому цього достигается.

Коли є та чи інша додаткову інформацію про безліч, що завдання іноді доводиться робити без повного перебору елементів всього безлічі M. Але найчастіше всього повний перебір виробляти доводиться. І тут обов’язково виникає завдання, як їм краще перебір организовать.

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

1) для [pic] (тут [pic] - безліч, яка полягає з єдиного елемента [pic]);

2) якщо [pic] і [pic], то [pic].

У умовах то можна організувати перебір елементів безлічі M з метою мінімізації функції у цьому безлічі так: розіб'ємо безліч M на частини (у будь-який спосіб) і выберем ту з його частин (1, де функція (мінімальна; за-тем розіб'ємо сталася на кілька частин безліч (1 і виберемо ту з його частин (2, де мінімальна функція (; потім разо-бьем (2 сталася на кілька частин 17-ї та виберемо ту їх, де минималь-на (, тощо, доки то дійдемо якомусь одноэлементно-му безлічі [pic].

Це одноэлементное безліч [pic]называется рекордом. Функція (, якої ми у своїй виборі користуємося, називається оцінної. Вочевидь, що рекорд зобов’язаний доставляти мінімум функції f; проте, ось яка можливість виникає скоротити перебір за сприятливих обстоятельствах.

Описаний вище процес побудови рекорду складалася з послідовних етапів, кожному у тому числі фіксувалося кілька множин і вибиралося потім одне з яких. Нехай [pic] [pic] - підмножини безлічі M, виниклі на предпослед-нем етапі побудови рекорду, і нехай безліч [pic] виявилося обраним з допомогою оцінної функції. Саме за разбие-нии [pic] і з’явилася рекорд, що зараз для визначеності позначимо через [pic]. Відповідно до сказаного вище, [pic], [pic]; ще, з визначення оцінної функції, [pic].

Припустимо, що [pic]; для будь-якого елемента m безлічі M, належить безлічі [pic], будуть вірні неравенства[pic][pic]; це що означає, що з повному переборі елементів з M елементи з [pic] вже занадто зайве рассматривать. Якщо ж нерівність [pic] нічого очікувати выполнеале, усі елементи з [pic] треба послідовно порівняти з найденным рекордом і тільки знайдеться елемент, дає меньшиї значення оптимизируемой функції, треба їм замінити ре-корд та продовжити перебір. Остання дія називається поліпшенням рекорда.

Слова метод гілок і національних кордонів пов’язані з природною графической інтерпретацією всього викладеного: будується багатоуровневое дерево, на нижньому поверсі якого розташовуються елементи безлічі M, у якому галузі ведуть до рекорду та її поліпшень і якому частина гілок залишаються «обірваними», що їх розвиток виявилося нецелесообразным.

Ми розглянемо зараз перший із двох що у цьому курсі прикладів застосування методу гілок і національних кордонів — ре-шение завдання про коммивояжере. Ось її формулировка.

Є кілька міст, соединеных деяким обра-зом шляхами з відомої довжиною; потрібно встановити, маєся чи шлях, впродовж якому можна побувати у кожному городе лише одне разів, і у своїй повернутися до місто, звідки шлях було розпочато («обхід комівояжера»), і, якщо він шлях маєся, встановити найкоротший з цих путей.

Формализуем умова в термінах теорії графів. Міста будуть вершинами графа, а дороги між містами — ориентиро-ванными (спрямованими) ребрами графа, кожному з кото-рых задана вагова функція: вагу ребра — це довжина соответствующей дороги. Шлях, потрібного знайти, це — ориентиро-ванный остовный простий цикл мінімального ваги в орграфе (нагадаємо: цикл називається остовным, коли він відбувається за всім вершин графа; цикл називається простим, коли він проходит з кожної своєї вершині лише одне раз; цикл називається орієнтованим, якщо початок кожного наступного ребра збігаються з кінцем попереднього; вагу циклу — це сума терезів його ребер; нарешті, орграф називається повним, якщо у неї име-ются всіх можливих ребра); такі цикли називаються також гамильтоновыми.

Вочевидь, у його орграфе цикли вищезазначеного типу є. Зауважимо, що запитання про наявність в орграфе гамильтонова циклу досить розглянути як окреме питання завдання про ком-мивояжере для повних орграфов. Справді, якщо це орграф перестав бути повним, його можна доповнити до відсутніми ребрами і кожному з доданих ребер при-писать вагу (, вважаючи, що (- це «комп'ютерна нескінченність», тобто. максимальне з усіх можливих в розглядах чисел. Якщо на знову побудованому повному орграфе знайти тепер лег-чайший гамільтонів цикл, то, при у нього ребер із (можна буде говорити, що в, вихідному графі «циклу комівояжера» немає. Якщо ж у повному орграфе найлегший гамильтонов цикл виявиться кінцевим на вагу, те він і буде иско-мым циклом в вихідному графе.

Отсюла слід, що завдання про коммивояжере досить ре-шити для повних орграфов з ваговій функцією. Сформулюємо тепер це у остаточному вигляді: нехай [pic] - повний орієнтований граф і [pic] - вагова функція; знайти простий остовный орієнтований цикл («цикл комівояжера») мінімального веса.

Нехай [pic] конкретний склад безлічі вершин і [pic] - вагова матриця даного орграфа, т. е.

[pic], причому нічого для будь-якого [pic].

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

Введемо деякі терміни. Нехай є деяка числовая матриця. Привести рядок цієї матриці означає выде-лить в рядку мінімальний елемент (її називають константою приведення) і відняти його з всіх елементів цього рядка. Оче-видно, врешті на цієї рядку дома мінімального эле-мента виявиться нуль, проте інші елементи будуть неотрица-тельными. Аналогічний сенс мають слова привести стовпець матрицы.

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

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

Вагою елемента матриці називають суму констант приведения матриці, що утворюється з цієї матриці заміною обговорюваного елемента на (. Отже, слова найважчий нуль в матриці означають, що у матриці підраховано вагу кожного нуля, та був фіксований нуль з максимальним весом.

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

Перший крок. Фіксуємо безліч всіх обходів коммивояжера (тобто. всіх простих орієнтованих остовных циклів). Поскільки граф — повний, це безліч явно непусто. Сопо-ставим йому число, що відіграватиме роль значення у цьому безлічі оцінної функції: їх кількість дорівнює сумі допомоги констант приведення даної матриці терезів ребер графа. Якщо множест-во всіх обходів комівояжера позначити через (, то суму констант приведення матриці терезів позначимо через (((). При-веденную матрицю терезів даного графа слід запам’ятати; обо-значим її через M1; в такий спосіб, підсумок перший крок: безлічі (всіх обходів комівояжера зіставлять чис-ло ((() і матриця M1.

Другий крок. Виберемо в матриці M1 найважчий нуль; нехай він стоїть у клітині [pic]; фіксуємо ребро графа [pic] і самеділимо безліч (на частини: на частина [pic], що складається з обходів, які відбуваються через ребро [pic], і частина [pic], що складається з обходів, які проходять через ребро [pic]. Порівняємо безлічі [pic] таку матрицю M1,1: в матриці M1 замінимо на (число у клітині [pic]. Потім у получен-ной матриці викреслимо рядок номер і і стовпець номер j, причому у рядків і шпальт збережемо їхні початкові номери. Нарешті, наведемо останню матрицю та й запам’ятаймо суму констант приведення. Отримана наведена матриця і буде матрицею M1,1; хіба що запомненную суму констант приведення додамо до ((() і результати, обозначаемый в даль-нейшем через (([pic]), можна порівняти безлічі [pic].

Тепер безлічі [pic] теж можна порівняти якусь матрицю M1,2. І тому в матриці M1 замінимо на (число у клітині [pic] і одержаний прибуток у результаті матрицю наведемо. Суму констант приведення запам’ятаємо, а отриману матрицю позначимо через M1,2. Додамо запомненную суму констант приведення до числу ((() й отримане число, позначуване надалі чогорез (([pic]), можна порівняти безлічі [pic].

Тепер виберемо між множинами [pic] і [pic] то, на якому мінімальна функція ((тобто. те з множин, якому відповідає менше з чисел (([pic]) і (([pic]).

Зауважимо тепер, що у проведених міркуваннях исполь-зовался в ролі вихідного лише одне фактичний об'єкт — наведена матриця терезів даного орграфа. Нею було вы-делено певне ребро графа і було побудовано нові матриці, яких, звісно, цілком можливо усе той самий застосувати. При кожному такому повторному застосуванні фіксуватиметься чергове ребро графа. Домовимося ось що дії: пе-ред тим, як і черговий матриці викреслити рядок і стовпець, у ній треба замінити на (числа в усіх отих клітинах, які со-ответвуют ребрах, явно не що належить тим гамильто-новым циклам, які проходять через відібрані раніше ребра; досить важку фразу ми ще неодноразово розглянемо в наступній лекції на конкретному примере.

До обраному безлічі з зіставленими йому матрицею і кількістю (повторимо усе ж і таке інше, це тільки воз-можно.

Доводиться, у результаті вийде безліч, со-стоящее з єдиного обходу комівояжера, вагу якого дорівнює черговому значенням функції (; в такий спосіб, оказы-ваются виконаними всі умови, обговорювані при описа-нии методу гілок і національних кордонів. Після цього здійснюється поліпшення рекорду до отримання остаточного ответа.