Новини освіти і науки:

G+

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

Контрольні запитання.

А б

1 0 0 0

А б

0 0 12 0

h = 12+3=15

Рис.3.4. (а) Приведена матриця вартості після викреслювання рядка 3 і стовпчика 5 і встановлення з₅₃=оо; (б) приведення матриці вартості зображеної у частині (а).

На даній стадії нам удалося скоротити розмір матриці вартості, розглянутої у вершині {3, 5}. Крім того, якщо ми зможемо знайти тур з множини {3.5} вартістю, меншої чи рівній 62, тоді не потрібно проводити далі розгалуження й обчислення границь у вершині {3, 5}. У цьому випадку будемо говорити, що вершина {3, 5} у дереві відпрацьована. Тоді наступною метою може бути розгалуження з вершини {3, 5} у надр знайти тур з вартістю в межах 49<с<62.

Рис. З.5. Блок-схема алгоритму гілок та меж.

В основних рисах блок-схема цього алгоритму гілок та меж показана на Рис. 3.5. Незабаром ми доповнимо цю схему рядом важливих деталей. Тут використовуються наступні позначення. Буква X позначає поточну вершину на дереві пошуку, a w(X) — відповідну нижню границю. Вершини, що випливають безпосередньо за X, назвемо Y і Y; вони вибираються розгалуженням по деякому ребру (к, 1). Символ Zo позначає вартість найдешевшого туру, відомого на даний момент. У початковий момент z₀=.

Блок 1. Установлення-початкових значень перемінних, чи ініціалізація.

Блок 2. Перше приведення — це безпосередня реалізація описаної раніше процедури-,

Блок 3. Вибір наступного ребра розгалуження (к, 1) визначає множини Y і Y, що безпосередньо випливають за поточним X. Ребро (к, 1) потрібно вибирати так, щоб спробувати одержати велику по величині нижню межу на множині Y={k, І}, що полегшить проведення оцінки для множини Y. Звичайно краще провести оцінку для Y, тому що розмір цієї множини і відповідна йому матриця вартості звичайно більше, ніж у Y (з матриці для Y викреслений рядок к і стовпець /). Можна сподіватися також, що Y с більшою імовірністю містить оптимальний тур.

Як застосувати ці ідеї до вибору конкретного ребра розгалуження (к, /)? У приведеній матриці вартості С`, зв'язаної с Х, кожен рядок і стовпець мають хоча б по одному нульовому елементі (якщо ні, те С` не цілком приведена). Можна припустити, що ребра, що відповідають цим нульової вартостям, будуть с більшою імовірністю входити в оптимальний тур, чим ребра с великими вартостями. Тому ми виберемо одне з них. Нехай ребро (і, j) має Cij==0 у С`. Ми хочемо, щоб у Y={i, j} була як можливо велика нижня межа. Згадуючи метод обчислення нижньої межі для {3, 5} у нашому прикладі, ми бачимо, що для 7 ця межа задається у вигляді

w(Y) = w(X)+(найменша вартість у рядку і, не включаючи

Сц) +(иайменша вартість у стовпчику], не включаючи cj).

Отже, із усіх ребер (і, j) с с_г;=0 у поточній матриці С ми вибираємо те, що дає найбільше значення для w(Y). Нехай це буде ребро (к, 1).

Тому більш докладний опис вибору, представленого блоком 3, має насту іший вид:

Крок 1. Нехай S — множина ребер (i,j), таких, що сij=0 у поточній матриці вартості С.

Крок 2. Покладемо Dj рівним найменшої вартості в рядку і, крім cij, плюс найменша вартість у стовпчику j, крім с_ч. Обчислюємо Dij для усіх (і, /)єS.

Крок 3. Вибираємо наступне ребро розгалуження (к, 1) з умови

Розглянемо знову задачу с п'ятьма містами, зображену на Рис. 17. З приведеної матриці С видно, що перше значення X, корінь R, має w(X)-47. Застосовуючи підалгоритм, описаний вище, знаходимо наше перше ребро розгалуження в такий спосіб:

Крок 1. S={(1, 2), (2,1), (3, 5), (4, 5), (5, 3), (5, 4)}

Крок 2. D₁₂=2+l=3 D_2]=12+3=15 D₃₃=2+0=2 D₄₅=3+0=3 D_e=0+12=12 D₆₄=0+2=2

Крок 3. Вибираємо ребро (k, 1)= (2, 1), тому що D₂i — це максимальний елемент множини {Dц}.

Блок 4. Визначаємо вершину Y, що випливає заХ, точно так само, як ми робили раніш.

У розглянутому прикладі Х=R і Y={2, 1}, таким чином це множина усіх турів, що не містять ребро (2,1). Обчислюємо нижню границю w(Y) так само, як у блоці 3,

w(Y} = w(X) +D'u i w({2, 1}) = 47 + 15 = 62.

Блок 5. Вершині Y, що випливає заХ, відповідає підмножині турів з Х, що містять те ребро (к, /), що обрана в блоці 3. У розглянутому прикладі Y={2, 1}. При обчисленні w(Y) необхідна відома обережність. Докладний підалгоритм має наступний вид:

Крок 1.3С виключаємо рядок k і стовпець /.

Крок 2. Усі тури множини, представленого вершиною Y, містять декілька (може бути, жодного) з раніше обраних ребер, крім ребра (к, l). Ребро (к, l) чи буде ізольовано від цих інших ребер, чи буде частиною шляху, що включає деякі чи всі ці ребра. Нехай р і q — початкове і кінцеве міста цього шляху. Можливо, що р=к і (чи) q=l. Покладемо Cqp=oo. Ця міра охороняє від вибору ребра (q, p) у якості наступного для Y, а тим самим охороняє від формування замкнутого циклу довжини менше N. Такі цикли, звичайно, не дозволені при побудові туру. Є чи якісь випадки, у яких ми не думаємо Cqp= oo ?

Крок 3. Приводимо розглянуту матрицю С. Нехай h буде дорівнює сумі констант приведення.

Крок 4. Обчислюємо w(Y) по формулі w(Y)=w(X)+h.

Повертаючись до прикладу, викреслюємо рядок 2 і стовпець 1 з матриці С, показаної на Рис. 3.3. Тому що ребро (2, 1) — єдине обране ребро, маємо р=2, g=l і С₁₂=оо. Після цих кроків, що відповідають крокам 1 і 2 описаного вище підалгоритму, що поточна матриця показана на Рис. 3.6, а. Після приведення одержуємо матрицю, зображену на Рис. 3.6, б, з h =3 і w [(2, 1)] = =w(X)+ft=47+3=50. Поточний стан показаний на рівнях 0 і 1 на Рис. 3.7.

2 3 4 5 2 3 4 5

h = 2+1=3

Рис 3.6. (а) Приведена матриця вартості після викреслювання рядка 2 і стовпчика 1 і встановлення з_І2=оо; (б) приведення матриці вартості, зображеної у частині (а),

Рис. 3.7. Дерево пошуку.

Блок 6. Зрештою ми повинні прийти до множин, які мають так мало турів, що ми можемо розглянути кожний з них і провести оцінку для цієї вершини без подальшого розгалуження. Блок 6 перевіряє, чи не прийшли ми вже до таких множин. Кожне ребро, про яке ми знаємо, що воно міститься у всіх турах з F, скорочує розмір С на один рядок і один стовпчик. Якщо у вихідній задачі було N міст, а поточна матриця С має розмір 2x2, то обрано уже N—2 ребер кожного туру Y. Тому множина Y містить якнайбільше два тури Таким чином, блок б перевіряє, чи є С матрицею розміру 2x2. Помітимо, що це, власне кажучи, дає відповідь на питання, поставлений наприкінці кроку 2 під час обговорення блоку 5.

Блоки 7 і 8. Блок 7 працює, тільки якщо С — матриця розмірів 2x2. У цьому блоці відшукується найдешевший тур у Y і його вага позначається через w(Y). У блоці 8 перевіряється, чи краще даний тур, чим поточний кращий з відомих турів. Якщо ні, то новий тур відкидається. Якщо так, то поточним кращим туром буде новий тур, і ми маємо z=w(Y).

Блок 9. Тепер потрібно вибрати наступну вершину X, від якої проводити розгалуження. Цей вибір досить очевидний. Вибираємо вершину, з якої в даний момент не виходять гілкиі і яка має найменшу нижню границю. Отже, даний блок складається з наступного подалгоритма:

Крок 1. Шукаємо множину S кінцевих вершин поточного дерева пошуку.

Крок 2. Нехай вершина X буде обрана так, що

w(X) = minw(v).

У розглянутому прикладі:

Крок 1. S={{2,1},{2,1}}

Крок2. w({2,1})=62, w({2,1))=50. Тому Х={2,1}.

Блок 10.Блок 10 показує, чи повинні ми зупинитися. Якщо поточна межа дію нашого кращого туру Zo менше чи дорівнює w(X) — найменшої з недосліджених нижніх меж,— тоді ніяка з вершин, що випливають за X, не може містити кращого туру. Завдяки способу вибору X у блоці 9 кращий тур не може також міститися ні в який іншій з неоцінених кінцевих вершин. Тепер усе дерево пошуку оцінене, і ми зупиняємося. Якщо w(X)<Zo, пошук повинний бути продовжений. У нашому прикладі z₀=, тому пошук не припиняється.

Блок 11. Уцій частиш алгоритму виходить відкоректована матриця вартості С для поточної вершини X. Процедура коректування наступна: Крок 1. Чи дорівнює множина X множині Y, що останній раз утворена в блоці 5? Якщо так, то поточна матриця С — це те, що нам потрібно, і ми повертаємося в блок 3. Саме це звичайно відбувається на рівні 2 дерева пошуку.

Крок 2. Установлюємо С вихідна матриця вартості.

Крок 3. Установлюємо S множина усіх пар (і, l), що повинні бути

ребрами в X}.

Крок4. Обчислюємо g=Z(i,j)_esCij.

Крок 5. Для кожної (і, j) є S викреслюємо рядок i і стовпчик j у С. Для кожного шляху, що проходить через (і, j), знаходимо початкове і кінцеве міста р і q і маємо с_чр=<х. У кожного ребра (к, /), забороненого для турів у X, маємо Сkl=оо.

Крок 6. Приводимо матрицю С. Маємо h рівним сумі констант приведення.

Крок 7. Обчислюємо w(X)=g+h. Kpoк 5 вносить незручність, тому що він зводиться до повторення того, що ми робили раніш. Очевидна альтернатива, здійснення якої зажадає великого обсягу пам'яті,— запам'ятовувати матриці С для кожної кінцевої вершини дерева. Як правило, це непрактично. У розглянутому прикладі ми просто виходимо з подалгоритма на кроці 1.

Продовжимо приклад. Зараз ми знаходимося в блоці 3, Х={2, 1}, W(X)=50, і дерево містить только рівні 0 і 1 (Рис. 3.7). Для визначення множин, що випливають за X, потрібно ребро (к, І). Придатна матриця С показана на Рис. 3.6, б. Використовуючи подалгоритм, описаний у блоці 3, маємо

Крок 1 S=((l, 5), (3, 5), (4, 5), (5, 2), (5, 3), (5, 4)}

D₁₅=1+0=1

D₃₅=2+0=2

D₄₅-l 8+0=18

D₅₂-13+0=13

D₅3=13+0=I3

D'₅₄=0+1 = 1

Крок 3. D₄₅=18 (у випадку декількох рівних вибираємо довільно). Таким чином, (к, /)⁼(4, 5).

Тепер установлюємо Y, використовуючи блок 4:

Y = {43} і W({43}) = W{2, 1}) + D₄₅ = 50+ 18 = 68.

Далі розглядаємо вершину Y={4, 5}. По-перше, викреслюємо з С рядок 4 і стовпчик 5. Тому що ребро (4, 5) не перетинається с ребром (2, 1), р=4 і q=5. Маємо С54=°с і приводимо С. Знаходимо, що h=3 і W(y)=50+h=53. Приведена матрица С показана на Рис.3.8,а. Нижня межа не зменшується при проходженні вглиб дерева.

Тепер ми знаходимося в блоці 6. Чи є поточна матриця С матрицею 2x2? Так як С — матриця-3x3, переходимо в блок 9. Підалгоритм блоку 9 виконується в такий спосіб:

Крок 1. S={{2,1},{4,5},{4,5}}

Крок 2 w({2,l})=62

w({4,5})=68

w({4,5})=53

Отже, Х=(4,5}.

2 3 4 1 2 3 4 5

0 0 0

2 3

h= 2+1=3

h= 62

h= 11

0 0

а б в

Рис. 3.8. Додаткові приведені матриці вартостей для задачі на Рис. 3.1

У блоці 10 zo=, тому йдемо далі. У блоці 11 нам повезло, і ми виходимо на кроці 1. Знову переходимо в блок 3 з Х={4, 5}, w(X) =53, і матриця С редставлена на Рис. 3.8, а.

Ще один раз, і мета може бути досягнута! Підалгоритм блоку 3 дає наступне:
Крок 1. S=((l, 4), (3,4), (5, 2), (5, 3)}.

Крок 2. D=12+0=12 d

D₃₄=l1+0=11

D₅₂= 11+0=11

D₅₃=12+0=12

Крок 3. D_kl=D₁₄=D₅₃=l 2. Ми довільно вибираємо (k, /)=(1, 4).

Тепер Y= {1,4} і w(y)= w({4,5}) +D`₁₄ = 53 + 12 = 65

Оскільки Y={1, 4}, з С викреслюємо рядок 1 і стовпець 4. Ребро (1, 4) разом с ребрами (2, 1) і (4, 5) утворить шлях. Тому р=2 і q=5. Занесемо с₅₂= i приводимо поточну матрицю С. Знаходимо, що А=11 і w(Y)=53+h=64. На Рис. 23, 6 показана приведена матриця С.

Тепер ми знаходимося в блоці 6 с матрицею С розмірів 2x2. Блок видає тур знаступним порядком міст:
321453

і вартістю z=64. У блоці 8 маємо zo=64; тепер це поточний кращий тур. Чи всі ми зробили? Нам не треба розглядати вершини, що випливають за вершинами {4,5} і {ї^}, тому що їхні нижні межі більше ніж 64. Однак у блоці 10 ми бачимо, що в кінцевій вершині {2,1} нижня межа дорівнює 62<64. Отже, можливо, що тур з цієї підмножини може бути трохи краще, ніж той, який ми одержали. Таким чином, треба ще дещо зробити.

Ми знаходимо, що Х={2, 1}, z(X)=62, а матриця С, відкоректована р допомогою шдалгоритма блоку 11, має вид, як на Рис. 23, в. Далі у блоці З вибирається ребро

(4, 1) з D*, = 12 як наступне ребро розгалуження. У блоках 4 і 5 обчислюються w({4,l})=62+12=74 і w({4,1))=62. Необхідна ще одна
ітерація.

Хоча здається, що тільки що побудований алгоритм працює дуже довго на нашему маленькому прикладі с п'ятьма містами, насправді це досить могутній інструмент. Ретельно виконана програма звичайно вирішує задачу комівояжера с 20—30 містами істотно швидше ніж за одну хвилину. Задачі с 40—50 містами часто можуть бути вирішені за цілком доступний час (менше 10 хв часу роботи центрального процесора).

Існують різні евристичні прийоми, що можуть прискорити цей основний алгоритм гілок та меж. Алгоритм "Жадібний комівояжер2" можна використовувати як початковий етап для алгоритму гілок та меж з даного розділу. Як ми бачили при побудові цього останнього алгоритму, може знадобитися якийсь час, перш ніж буде знайдені перший повний тур і ш₀стане реалістичною оцінкою вартості оптимального туру. Якщо на початку роботи алгоритму відомий досить гарний тур, скажемо отриманий алгоритмом 12, тоді z₀ c самого початку встановлюється на досить низький

рівень. У цьому випадку будь-яка вершина на дереві пошуку, нижня межа якої виявляється чи більше рівної z, відразу може вважатися дослідженою. Таким чином, можна значною мірою уникнути марного пошуку при роботі точного алгоритму.

Цей алгоритм вважався одним із кращих для задачі комівояжера майже до 1970 p. C тих пір з'явилися більш швидкі алгоритми. Про усіх більш-менш ефективних алгоритмах гілок та меж відомо, що їхня трудомісткість у гіршому випадку є експонентної.

1.Що означає гілка для методу меж та гілок?

2. Що є межею для методу меж та гілок?

3. Яку структуру даних використовують для методу меж та гілок?

4. Що означає приведення матриці в методі меж та гілок для задачі про комівояжера?

5. Сформулюйте алгоритм методом меж та гілок для задачі про комівояжера.

6. Розв'яжіть задачу про комівояжера методом меж та гілок для несиметричної матриці 4x4.

7. Яка робоча функція методу меж та гілок.

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

<== попередня сторінка	\|	наступна сторінка ==>
Розділ 3. Метод гілок і меж	\|	Перестановка

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

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