Зміст
Введення
1. Дискретні оптимізаційні завдання
1.1 Постановка задач дискретного програмування
1.2 Алгоритм методу гілок і граніц6
2. Постановка задачі комівояжера
3. Завдання комівояжера методом динамічного програмування
4. Завдання комівояжера методом гілок і меж
Висновок
Список використаних джерел
Необхідність прийняття найкращих рішень так само стара, як саме людство. Споконвіку люди, приступаючи до здійснення своїх заходів, роздумували над їх можливими наслідками і приймали рішення, вибираючи тим чи іншим чином залежать від них параметри - способи організації заходів. Але до пори, до часу рішення могли прийматися без спеціального математичного аналізу, просто на основі досвіду і здорового глузду.
Візьмемо приклад: людина вийшла вранці з дому, щоб їхати на роботу. По ходу справи йому доводиться прийняти цілу низку рішень: чи брати з собою парасольку? В якому місці перейти вулицю? Яким видом транспорту скористатися? І так далі. Зрозуміло, всі ці рішення людина приймає без спеціальних розрахунків, просто спираючись на наявний у нього досвід і на здоровий глузд. Для обгрунтування таких рішень ніяка наука не потрібна, та навряд чи знадобиться і в подальшому.
Проте візьмемо інший приклад. Допусти, організовується робота міського транспорту. У нашому розпорядженні є якась кількість транспортних засобів. Необхідно прийняти ряд рішень, наприклад: яку кількість і яких транспортних засобів направити по тому чи іншому маршруті? Як змінювати частоту проходження машин в залежності від часу доби? Де помістити зупинки? І так далі.
Ці рішення є набагато більш відповідальними, ніж рішення попереднього прикладу. З огляду на складності явища наслідки кожного з них не настільки ясні; для того, щоб уявити собі ці наслідки, потрібно провести розрахунки. А головне, від цих рішень набагато більше залежить. У першому прикладі неправильний вибір рішення торкнеться інтересів однієї людини, у другому - може відбитися на ділове життя цілого міста.
Найбільш складно йде справа з прийняттям рішень, коли мова йде про заходи, досвіду, в проведенні яких ще не існує і, отже, здоровому глузду нема на що спертися, а інтуїція може обдурити. Нехай, наприклад, складається перспективний план розвитку озброєння на кілька років вперед. Зразки озброєння, про які може йти мова, ще не існують, ніякого досвіду їх застосування немає. При плануванні доводиться спиратися на велику кількість даних, що відносяться не стільки до минулого досвіду, скільки до що передбачається майбутнього. Вибране рішення повинне по можливості гарантувати нас від помилок, пов'язаних з неточним прогнозуванням, і бути досить ефективним для широкого кола умов. Для обгрунтування такого рішення наводиться в дію складна система математичних розрахунків.
Взагалі, чим складніше организуемое захід, чим більше вкладається в нього матеріальних засобів, чим ширше спектр його можливих наслідків, тим менш допустимі так звані "вольові" рішення, що не спираються на науковий розрахунок, і тим більше значення отримує сукупність наукових методів, що дозволяють заздалегідь оцінити наслідки кожного рішення, заздалегідь відкинути неприпустимі варіанти і рекомендувати ті, які представляються найбільш вдалими.
Дискретні оптимізаційні завдання можна вирішувати двома методами: метод дискретного програмування і метод гілок і меж. Вони будуть розглянуті на прикладі задачі комівояжера.
F (x0) = min f (x), x є G,
безліч допустимих рішень якої звичайно, тобто Про ≤ | G | = N <∞, де | G | - число елементів множини G. У силу кінцівки G всі допустимі рішення можна пронумерувати: x1, x2,. . . . ., XN, обчислити f (xi), i = 1,2 ,..., N, і знайти найменше значення.
У багатьох завданнях умови дискретності відокремлені від інших умов, тобто якщо х = (х1, х2, ..., хn), то xj є Gj = (х j 1, хj2, ..., хjki), kj> 2. Тому N = =
f (x0) = min f (x), x є G, | G | = N <∞.
Алгоритм гілок і меж заснований на наступних побудовах, що дозволяють зменшити обсяг перебору.
1. Обчислення оцінки. Нехай G '
2. Галуження (розбиття множини G на підмножини). Покладемо
G0 = G і розіб'ємо безліч G0 на r1 непересічних підмножин
Цей крок алгоритму вважаємо початковим, що мають номер 0. Розглянемо крок алгоритму з номером k. Нехай
Виконаємо модифікацію списку множин, ще не піддавалися розбиття. Замінимо безліч
Ці множини утворюють список завдань для розгалуження. Виберемо одне з них і знову повторимо процедуру розбиття.
Описану процедуру розбивки можна представити у вигляді дерева (рис. 1)
Рис. 1
3. Перерахунок оцінок. Якщо G1
Тому, розбиваючи в процесі розгалуження підмножина G '
4. Обчислення планів (допустимих рішень). Якщо на кроці розгалуження з номером k відомий план Xk, на кроці з номером (k + 1) - план хk +1 і якщо f (xk +1) <f (xk), то план хk забувається і замість нього зберігається план хk + 1. Найкраще з отриманих припустимих рішень прийнято називати рекордом.
5. Ознака оптимальності. Нехай G =
f (
6. Оцінка точності наближених рішень. Нехай G =
φ0 =
φ0 ≤ f (x0) ≤ f (xk).
Різниця Δ = f (xk) - φ0 є оцінкою гарантованого відхилення рекорду хk від оптимуму х0. З наведеного нерівності випливає, що для розгалуження необхідно вибрати безліч з мінімальним значенням нижньої оцінки.
7. Правило відсіву. Нехай знову G =
Правило φ (Gr)> f (xk) гарантує, що в процесі роботи алгоритму жодне з підмножин Gr, в яких міститься точне рішення x0, не буде відсіяно. Більш сильне правило φ (Gr) ≥ f (xk) гарантує, що хоча б одне оптимальне рішення буде знайдено, воно і застосовується при практичному вирішенні завдань.
8. Кінцівка алгоритму. Кінцівка алгоритму випливає з кінцівки безлічі G.
Під методом гілок і меж розуміється алгоритм вирішення задачі, що має деревоподібну структуру пошуку оптимального рішення і використовує результати вирішення оціночних завдань. Деревоподібна структура називається зазвичай деревом розгалуження.
Ефективність алгоритму гілок і меж визначається числом вирішених завдань. Рішення задачі складається з двох основних етапів. На першому етапі знаходиться оптимальне рішення (або близьке до нього). На другому етапі проводиться доказ оптимальності отриманого рішення. Другий етап, як правило, виявляється більш трудомістким, ніж перший. Це означає, що число підзадач, розв'язуваних до отримання оптимуму, може виявитися істотно менше числа підзадач, що вирішуються для доказу оптимальності.
Вихідну інформацію по ЗК вважаємо представленої у вигляді матриці розміру nxn. S = {sij}, де sij - вага дуги (i, j) графа G, i =
У типовій інтерпретації вершини 1, 2, ..., n графа G - це міста. Дуги відображають можливі елементарні переходи. Комівояжеру, спочатку знаходиться в місті 1, необхідно обійти всі інші міста, побувавши у кожному з них рівно по одному разу, і потім повернутися в місто 1. Ваги дуг графа трактуються як довжини відповідних елементарних переходів. Потрібно знайти що має мінімальну довжину допустимий (тобто задовольняє накладеним вимогам) маршрут комівояжера. З урахуванням інших можливих інтерпретацій, на матрицю S вимога симетричності не накладається, не вважається обов'язковим і виконання нерівності трикутника.
Один з основних алгоритмів розв'язання ЗК заснований на принципі динамічного програмування. При викладі цього алгоритму будемо дотримуватися термінології, відповідної наведеної типової інтерпретації завдання.
Нехай i - довільний місто (i Î N), а V - будь-яка підмножина міст, що не містить міста 1 і міста i. Через М (i, V) позначимо сукупність шляхів, кожен з яких починається в місті i, завершується у місті 1 і проходить в якості проміжних тільки через міста безлічі V, заходячи в кожен з них рівно по одному разу. Через В (i, V) позначимо довжину найкоротшого шляху безлічі М (i, V). Для розв'язуваної задачі В (i, V) - функція Белмана. Як очевидно, В (1, {2, 3, ..., n}) - шукана мінімальна довжина простого (без самоперетинів) замкнутого шляху, що проходить через усі міста.
Якщо V - одноелементні безліч, V = {j}, де j ≠ 1 і j ≠ i, то сукупність М (i, V) складається з єдиного шляху μ = (i, j, 1). Тому
Припустимо, що значення функції В (i, V) для всіх i ÎN \ {1} і всіх можливих k-елементних (k <n - 1) множин V вже враховано. Тоді значення В (i, V '), де V' - довільне (k + 1)-елементне підмножина сукупності N \ {1, i}, обчислюється за формулою
Рівняння (1.1) - (1.12) - рекурентні співвідношення динамічного програмування для розв'язання задачі комівояжера, вони забезпечують реалізацію зворотного методу Беллмана. Обчислювальна складність задачі дорівнює
Приклад 1.1 Вирішити задачу комівояжера, яка визначається матрицею:
Спочатку, користуючись формулою (1.1), визначаємо значення В (i, {j}):
В (2, {3}) = 5 + 6 = 11; В (3, {2}) = 2 + 2 = 4; В (4, {2}) = 5 + 2 = 7;
В (2, {4}) = 2 + 1 = 3; В (3, {4}) = 1 + 1 = 2; В (4, {3}) = 4 + 6 = 10.
Далі за формулою (1.2) послідовно отримуємо (у лівій частині кожного з нижче записаних рівностей виділені ті значення параметра j, на яких під час підрахунку реалізується зазначений у правій частині (1.2) мінімум):
В (2, {3, 4}) = min [s23 + B (3, {4}); s24 + B (4, {3})] = min (5 + 2 2 + 10) = 7;
В (3, {2, 4}) = min [s32 + B (2, {4}); s34 + B (4, {2})] = min (2 + 3; 1 + 7) = 5;
В (4, {2, 3}) = min [s42 + B (2, {3}); s43 + B (3, {2})] = min (5 + 11; 4 +4) = 8;
В (1, {2, 3, 4}) = min [s12 + B (2, {3,4}) s13 + B (3, {2,4}) s14 + B (4, {2,3} )] =
= Min (4 +7; 3 +5; 4 + 8) = 8.
Отже, оптимальне значення критерію в розглянутому прикладі дорівнює 8.
Виконані виділення дозволяють визначити оптимальний маршрут. Він наступний:
1 SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 1.
Для запису співвідношень, за якими реалізується прямий метод Белмана, введемо нові позначення. Нехай М '(V, i) - сукупність шляхів, кожен з яких починається в місті 1, проходить в якості проміжних тільки через міста підмножини V, заходячи в кожен з них рівно по одному разу, і завершується в місті i; тут, як і раніше, i - довільний місто (i Î N), а V - будь-яка підмножина N, що не містить міст 1 і i. Довжину найкоротшого шляху безлічі М '(V, i) позначимо В * (V, i). Як очевидно, В * ({2, 3, ..., n}, 1) - шукана мінімальна довжина простого (без самоперетинів) замкнутого шляху, що проходить через усі міста. Якщо V - одноелементні безліч, V = {j}, де j ≠ 1 і j ≠ i, то сукупність М '(V, i) складається з єдиного шляху μ = (1, j, i). Тому
Припустимо, що значення функції У * (V, i) для всіх i Î N і всіх можливих k-елементних (k <n - 1) множин V вже враховано. Тоді значення В * (V ', i), де V' - довільне (k + 1) - елементний підмножина сукупності N \ {1, i}, обчислюється за формулою
Рівняння (1.3) - (1.4) - рекурентні співвідношення динамічного програмування для вирішення класичної задачі комівояжера, вони забезпечують реалізацію прямого методу Беллмана.
Приклад 1.2 Методом прямого рахунку вирішити завдання комівояжера, яка визначається матрицею:
(Зауважимо, що матриця S в даному прикладі та ж, що і в попередньому).
Спочатку, користуючись формулою (1.3), визначаємо значення В * ({j}, i):
В * ({2}, 3) = 4 + 5 = 9; В * ({3}, 2) = 3 + 2 = 5; В * ({4}, 2) = 4 + 5 = 9;
В * ({2}, 4) = 4 + 2 = 6; В * ({3}, 4) = 3 + 1 = 4; В * ({4}, 3) = 4 + 4 = 8.
Далі за формулою (1.4) послідовно отримуємо (у лівій частині кожного з нижче записаних рівностей виділені ті значення параметра j, на яких під час підрахунку реалізується зазначений у правій частині (1.4) мінімум):
Введення
1. Дискретні оптимізаційні завдання
1.1 Постановка задач дискретного програмування
1.2 Алгоритм методу гілок і граніц6
2. Постановка задачі комівояжера
3. Завдання комівояжера методом динамічного програмування
4. Завдання комівояжера методом гілок і меж
Висновок
Список використаних джерел
Введення
Дискретна оптимізація як розділ математики існує досить давно. Оптимізація - це вибір, тобто те, чим постійно доводиться займатися в повсякденному житті. Терміном "оптимізація" в літературі позначають процес або послідовність операцій, що дозволяють отримати уточнене рішення. Хоча кінцевою метою оптимізації є відшукання найкращого або "оптимального" рішення, звичайно доводиться задовольнятися поліпшенням відомих рішень, а не доведенням їх до досконалості. Тому під оптимізацією розуміють скоріше прагнення до досконалості, яке, можливо, і не буде досягнуто.Необхідність прийняття найкращих рішень так само стара, як саме людство. Споконвіку люди, приступаючи до здійснення своїх заходів, роздумували над їх можливими наслідками і приймали рішення, вибираючи тим чи іншим чином залежать від них параметри - способи організації заходів. Але до пори, до часу рішення могли прийматися без спеціального математичного аналізу, просто на основі досвіду і здорового глузду.
Візьмемо приклад: людина вийшла вранці з дому, щоб їхати на роботу. По ходу справи йому доводиться прийняти цілу низку рішень: чи брати з собою парасольку? В якому місці перейти вулицю? Яким видом транспорту скористатися? І так далі. Зрозуміло, всі ці рішення людина приймає без спеціальних розрахунків, просто спираючись на наявний у нього досвід і на здоровий глузд. Для обгрунтування таких рішень ніяка наука не потрібна, та навряд чи знадобиться і в подальшому.
Проте візьмемо інший приклад. Допусти, організовується робота міського транспорту. У нашому розпорядженні є якась кількість транспортних засобів. Необхідно прийняти ряд рішень, наприклад: яку кількість і яких транспортних засобів направити по тому чи іншому маршруті? Як змінювати частоту проходження машин в залежності від часу доби? Де помістити зупинки? І так далі.
Ці рішення є набагато більш відповідальними, ніж рішення попереднього прикладу. З огляду на складності явища наслідки кожного з них не настільки ясні; для того, щоб уявити собі ці наслідки, потрібно провести розрахунки. А головне, від цих рішень набагато більше залежить. У першому прикладі неправильний вибір рішення торкнеться інтересів однієї людини, у другому - може відбитися на ділове життя цілого міста.
Найбільш складно йде справа з прийняттям рішень, коли мова йде про заходи, досвіду, в проведенні яких ще не існує і, отже, здоровому глузду нема на що спертися, а інтуїція може обдурити. Нехай, наприклад, складається перспективний план розвитку озброєння на кілька років вперед. Зразки озброєння, про які може йти мова, ще не існують, ніякого досвіду їх застосування немає. При плануванні доводиться спиратися на велику кількість даних, що відносяться не стільки до минулого досвіду, скільки до що передбачається майбутнього. Вибране рішення повинне по можливості гарантувати нас від помилок, пов'язаних з неточним прогнозуванням, і бути досить ефективним для широкого кола умов. Для обгрунтування такого рішення наводиться в дію складна система математичних розрахунків.
Взагалі, чим складніше организуемое захід, чим більше вкладається в нього матеріальних засобів, чим ширше спектр його можливих наслідків, тим менш допустимі так звані "вольові" рішення, що не спираються на науковий розрахунок, і тим більше значення отримує сукупність наукових методів, що дозволяють заздалегідь оцінити наслідки кожного рішення, заздалегідь відкинути неприпустимі варіанти і рекомендувати ті, які представляються найбільш вдалими.
1. Дискретні оптимізаційні завдання
Дискретні оптимізаційні задачі знаходять широке застосування в різних областях, де використовуються математичні методи для аналізу відбуваються там процесів. Необхідність вирішення таких завдань призводить до того, що дискретна оптимізація стає важливим елементом освіти фахівців, пов'язаних з її застосуванням при вирішенні завдань, що виникають у додатках. Тому нам видається, що технологія вирішення задач дискретного програмування повинна стати однією з важливих складових частин сучасного математичної освіти для фахівців з прикладної математики.Дискретні оптимізаційні завдання можна вирішувати двома методами: метод дискретного програмування і метод гілок і меж. Вони будуть розглянуті на прикладі задачі комівояжера.
1.1 Постановка задач дискретного програмування
Під завданням дискретного програмування (дискретної оптимізації) розуміється завдання математичного програмуванняF (x0) = min f (x), x є G,
безліч допустимих рішень якої звичайно, тобто Про ≤ | G | = N <∞, де | G | - число елементів множини G. У силу кінцівки G всі допустимі рішення можна пронумерувати: x1, x2,. . . . ., XN, обчислити f (xi), i = 1,2 ,..., N, і знайти найменше значення.
У багатьох завданнях умови дискретності відокремлені від інших умов, тобто якщо х = (х1, х2, ..., хn), то xj є Gj = (х j 1, хj2, ..., хjki), kj> 2. Тому N = =
1.2 Алгоритм методу гілок і меж
Розглянемо завдання у вигляді:f (x0) = min f (x), x є G, | G | = N <∞.
Алгоритм гілок і меж заснований на наступних побудовах, що дозволяють зменшити обсяг перебору.
1. Обчислення оцінки. Нехай G '
2. Галуження (розбиття множини G на підмножини). Покладемо
G0 = G і розіб'ємо безліч G0 на r1 непересічних підмножин
Цей крок алгоритму вважаємо початковим, що мають номер 0. Розглянемо крок алгоритму з номером k. Нехай
Виконаємо модифікацію списку множин, ще не піддавалися розбиття. Замінимо безліч
Ці множини утворюють список завдань для розгалуження. Виберемо одне з них і знову повторимо процедуру розбиття.
Описану процедуру розбивки можна представити у вигляді дерева (рис. 1)
Рис. 1
3. Перерахунок оцінок. Якщо G1
Тому, розбиваючи в процесі розгалуження підмножина G '
4. Обчислення планів (допустимих рішень). Якщо на кроці розгалуження з номером k відомий план Xk, на кроці з номером (k + 1) - план хk +1 і якщо f (xk +1) <f (xk), то план хk забувається і замість нього зберігається план хk + 1. Найкраще з отриманих припустимих рішень прийнято називати рекордом.
5. Ознака оптимальності. Нехай G =
f (
6. Оцінка точності наближених рішень. Нехай G =
φ0 =
φ0 ≤ f (x0) ≤ f (xk).
Різниця Δ = f (xk) - φ0 є оцінкою гарантованого відхилення рекорду хk від оптимуму х0. З наведеного нерівності випливає, що для розгалуження необхідно вибрати безліч з мінімальним значенням нижньої оцінки.
7. Правило відсіву. Нехай знову G =
Правило φ (Gr)> f (xk) гарантує, що в процесі роботи алгоритму жодне з підмножин Gr, в яких міститься точне рішення x0, не буде відсіяно. Більш сильне правило φ (Gr) ≥ f (xk) гарантує, що хоча б одне оптимальне рішення буде знайдено, воно і застосовується при практичному вирішенні завдань.
8. Кінцівка алгоритму. Кінцівка алгоритму випливає з кінцівки безлічі G.
Під методом гілок і меж розуміється алгоритм вирішення задачі, що має деревоподібну структуру пошуку оптимального рішення і використовує результати вирішення оціночних завдань. Деревоподібна структура називається зазвичай деревом розгалуження.
Ефективність алгоритму гілок і меж визначається числом вирішених завдань. Рішення задачі складається з двох основних етапів. На першому етапі знаходиться оптимальне рішення (або близьке до нього). На другому етапі проводиться доказ оптимальності отриманого рішення. Другий етап, як правило, виявляється більш трудомістким, ніж перший. Це означає, що число підзадач, розв'язуваних до отримання оптимуму, може виявитися істотно менше числа підзадач, що вирішуються для доказу оптимальності.
2. Постановка задачі комівояжера
Класична задача комівояжера (ЗК) формулюється таким чином: є повний зважений орієнтований граф без петель G з безліччю вершин N = {1, 2, ..., n}; ваги всіх дуг ненегативні; в цьому графі потрібно знайти гамільтонів цикл мінімальної ваги.Вихідну інформацію по ЗК вважаємо представленої у вигляді матриці розміру nxn. S = {sij}, де sij - вага дуги (i, j) графа G, i =
У типовій інтерпретації вершини 1, 2, ..., n графа G - це міста. Дуги відображають можливі елементарні переходи. Комівояжеру, спочатку знаходиться в місті 1, необхідно обійти всі інші міста, побувавши у кожному з них рівно по одному разу, і потім повернутися в місто 1. Ваги дуг графа трактуються як довжини відповідних елементарних переходів. Потрібно знайти що має мінімальну довжину допустимий (тобто задовольняє накладеним вимогам) маршрут комівояжера. З урахуванням інших можливих інтерпретацій, на матрицю S вимога симетричності не накладається, не вважається обов'язковим і виконання нерівності трикутника.
3. Завдання комівояжера методом динамічного
програмування
Під методом гілок і меж розуміється алгоритм вирішення задачі, що має деревоподібну структуру пошуку оптимального рішення і використовує результати вирішення оціночних завдань. Деревоподібна структура називається зазвичай деревом розгалуження.Один з основних алгоритмів розв'язання ЗК заснований на принципі динамічного програмування. При викладі цього алгоритму будемо дотримуватися термінології, відповідної наведеної типової інтерпретації завдання.
Нехай i - довільний місто (i Î N), а V - будь-яка підмножина міст, що не містить міста 1 і міста i. Через М (i, V) позначимо сукупність шляхів, кожен з яких починається в місті i, завершується у місті 1 і проходить в якості проміжних тільки через міста безлічі V, заходячи в кожен з них рівно по одному разу. Через В (i, V) позначимо довжину найкоротшого шляху безлічі М (i, V). Для розв'язуваної задачі В (i, V) - функція Белмана. Як очевидно, В (1, {2, 3, ..., n}) - шукана мінімальна довжина простого (без самоперетинів) замкнутого шляху, що проходить через усі міста.
Якщо V - одноелементні безліч, V = {j}, де j ≠ 1 і j ≠ i, то сукупність М (i, V) складається з єдиного шляху μ = (i, j, 1). Тому
Припустимо, що значення функції В (i, V) для всіх i ÎN \ {1} і всіх можливих k-елементних (k <n - 1) множин V вже враховано. Тоді значення В (i, V '), де V' - довільне (k + 1)-елементне підмножина сукупності N \ {1, i}, обчислюється за формулою
Рівняння (1.1) - (1.12) - рекурентні співвідношення динамічного програмування для розв'язання задачі комівояжера, вони забезпечують реалізацію зворотного методу Беллмана. Обчислювальна складність задачі дорівнює
Приклад 1.1 Вирішити задачу комівояжера, яка визначається матрицею:
Спочатку, користуючись формулою (1.1), визначаємо значення В (i, {j}):
В (2, {3}) = 5 + 6 = 11; В (3, {2}) = 2 + 2 = 4; В (4, {2}) = 5 + 2 = 7;
В (2, {4}) = 2 + 1 = 3; В (3, {4}) = 1 + 1 = 2; В (4, {3}) = 4 + 6 = 10.
Далі за формулою (1.2) послідовно отримуємо (у лівій частині кожного з нижче записаних рівностей виділені ті значення параметра j, на яких під час підрахунку реалізується зазначений у правій частині (1.2) мінімум):
В (2, {3, 4}) = min [s23 + B (3, {4}); s24 + B (4, {3})] = min (5 + 2 2 + 10) = 7;
В (3, {2, 4}) = min [s32 + B (2, {4}); s34 + B (4, {2})] = min (2 + 3; 1 + 7) = 5;
В (4, {2, 3}) = min [s42 + B (2, {3}); s43 + B (3, {2})] = min (5 + 11; 4 +4) = 8;
В (1, {2, 3, 4}) = min [s12 + B (2, {3,4}) s13 + B (3, {2,4}) s14 + B (4, {2,3} )] =
= Min (4 +7; 3 +5; 4 + 8) = 8.
Отже, оптимальне значення критерію в розглянутому прикладі дорівнює 8.
Виконані виділення дозволяють визначити оптимальний маршрут. Він наступний:
1 SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 1.
Для запису співвідношень, за якими реалізується прямий метод Белмана, введемо нові позначення. Нехай М '(V, i) - сукупність шляхів, кожен з яких починається в місті 1, проходить в якості проміжних тільки через міста підмножини V, заходячи в кожен з них рівно по одному разу, і завершується в місті i; тут, як і раніше, i - довільний місто (i Î N), а V - будь-яка підмножина N, що не містить міст 1 і i. Довжину найкоротшого шляху безлічі М '(V, i) позначимо В * (V, i). Як очевидно, В * ({2, 3, ..., n}, 1) - шукана мінімальна довжина простого (без самоперетинів) замкнутого шляху, що проходить через усі міста. Якщо V - одноелементні безліч, V = {j}, де j ≠ 1 і j ≠ i, то сукупність М '(V, i) складається з єдиного шляху μ = (1, j, i). Тому
Припустимо, що значення функції У * (V, i) для всіх i Î N і всіх можливих k-елементних (k <n - 1) множин V вже враховано. Тоді значення В * (V ', i), де V' - довільне (k + 1) - елементний підмножина сукупності N \ {1, i}, обчислюється за формулою
Рівняння (1.3) - (1.4) - рекурентні співвідношення динамічного програмування для вирішення класичної задачі комівояжера, вони забезпечують реалізацію прямого методу Беллмана.
Приклад 1.2 Методом прямого рахунку вирішити завдання комівояжера, яка визначається матрицею:
(Зауважимо, що матриця S в даному прикладі та ж, що і в попередньому).
Спочатку, користуючись формулою (1.3), визначаємо значення В * ({j}, i):
В * ({2}, 3) = 4 + 5 = 9; В * ({3}, 2) = 3 + 2 = 5; В * ({4}, 2) = 4 + 5 = 9;
В * ({2}, 4) = 4 + 2 = 6; В * ({3}, 4) = 3 + 1 = 4; В * ({4}, 3) = 4 + 4 = 8.
Далі за формулою (1.4) послідовно отримуємо (у лівій частині кожного з нижче записаних рівностей виділені ті значення параметра j, на яких під час підрахунку реалізується зазначений у правій частині (1.4) мінімум):
В * ({2, 3}, 4) = min [B * ({2}, 3) + s34; B * ({3}, 2) + s24] = min (9 + 1; 5 + 2) = 7;
В * ({2, 4}, 3) = min [B * ({2}, 4) + s43; B * ({4}, 2) + s23] = min (6 + 4; 9 + 5) = 10;
В * ({3, 4}, 2}) = min [B * ({3}, 4) + s42; B * ({4}, 3) + s32] = min (4 + 5; 8 + 2) = 9;
В * ({2, 3, 4}, 1) = min [B * ({2, 3}, 4) + s41; B * ({2, 4}, 3) + s31; B * ({3, 4}, 2) + s21;] = min (7 + 1; 10 +6; 9 + 2) = 8.
Отже, оптимальне значення критерію в розглянутому прикладі дорівнює 8.
Виконані виділення дозволяють визначити оптимальний маршрут. Він наступний:
1 SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 1.
Формально будується дерево варіантів, починаючи від кореня. У корені необхідно дати верхню і нижню оцінки. Далі галузиться. Чим менший фрагмент дерева доведеться побудувати, тим успішніше спрацював метод гілок і меж.
Мають місце наступні визначення:
Поточний рекорд - найбільша з отриманих в процесі реалізації методу нижніх оцінок.
Вершина іменується мертвою, якщо верхня оцінка в ній не перевищує поточного рекорду. Виконувати в ній подальше розгалуження марно.
Термінальній називається вершина, в якій верхня і нижня оцінки збігаються.
Вершина, розгалуження в якій вже виконано, називається закритою.
Вершини, які не є мертвими, термінальними або закритими, називаються відкритими. Подальше розгалуження робимо в них.
Рішення закінчується тоді, коли в нашому дереві варіантів немає відкритих вершин. Оптимальним рішенням буде поточний рекорд.
Верхня оцінка визначається за допомогою «жадібного» алгоритму.
Жадібний алгоритм - алгоритм знаходження найкоротшого відстані методом вибору найкоротшого, ще не обраного ребра, за умови, що воно не утворює циклу з вже обраними ребрами. "Жодний" цей алгоритм названий тому, що на останніх кроках доводиться жорстоко розплачуватися за жадібність (останнє ребро, як правило, найбільше або близько до нього по довжині).
Стратегія: «йди до найближчого (до якого ще не входив) місто». Розглянемо для прикладу мережу на рис. 2, що представляє вузький ромб. Нехай комівояжер стартує з міста 1. Алгоритм «Іди ви найближче місто» виведе його в місто 2, потім 3, потім 4; на останньому кроці доведеться платити за жадібність, повертаючись по довгій діагоналі ромба. У результаті вийде не найкоротший, а довжелезний тур.
Щоб обчислити нижню оцінку, спочатку підсумовуємо мінімальні елементи по рядках і по стовпцях, а потім з отриманих сум вибираємо найбільшу, але треба враховувати конфлікт.
Приклад 2.1 Вирішити методом гілок і меж завдання комівояжера, яка визначається матрицею:
1. Обчислюємо верхню і нижню оцінки в корені:
Верхню оцінку підраховуємо, користуючись, так званим, «жадібним» алгоритмом: кожен перехід робимо з поточного в найближче місто. Отримуємо маршрут:
1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f "Symbol" \ s 13 ® 1
Сумарна вартість даного маршруту дорівнює 12, вона визначає верхню оцінку в корені.
Щоб обчислити нижню оцінку, спочатку підсумовуємо мінімальні елементи по рядках і по стовпцях, а потім з отриманих сум вибираємо найбільшу:
За рядками: 2 + 1 + 2 + 2 + 2 = 9
За стовпцях: 2 + 2 + 3 + 1 + 2 = 10
Вибираємо максимум із значень і вибираємо 10.
Проаналізуємо стовпці: можемо зрушитися на 2 (конфлікт). Звідси нижня межа дорівнює 10 + 2 = 12.
●
Далі з кореневої вершини починаємо розгалуження по містах, в які можемо йти з першого:
●
Далі підраховуємо верхні і нижні оцінки для нових вершин:
1 - 2: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною
вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f "Symbol" \ s 13 ® 1 дорівнює 13. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що йдемо з 1го міста у 2й. Вона співпадає з нижньою оцінкою в корені і дорівнює 12.
1 - 3: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f "Symbol" \ s 13 ® 4SYMBOL 174 \ f "Symbol" \ s 13 ® 1, дорівнює 16. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що з 1го міста йдемо в 3й. Вона дорівнює 2 +2 +4 + 1 +2 = 11 і плюс 2 з урахуванням конфлікту. Разом отримуємо 13.
1 - 4: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 5SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 1 дорівнює 24. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що йдемо з 1го міста в 4й. Вона дорівнює 18.
1 - 5: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 2SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 1 дорівнює 23. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що йдемо з 1го міста в 5й. І вона дорівнює 16
●
Проаналізуємо отримані результати. Поточний рекорд дорівнює 12.
Перехід у вершини 3, 4 і 5 дає погіршення критерію, тому дані вершини іменуються мертвими й розгалуження з них далі безглуздо. Далі будемо гілкуватися в 2 і 3 вершинах.
1 - 2 - 3: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f " Symbol "\ s 13 ® 4 SYMBOL 174 \ f" Symbol "\ s 13 ® 5 SYMBOL 174 \ f" Symbol "\ s 13 ® 1 дорівнює 19. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що йдемо з 1го міста у 2й, з 2го в 3й. Вона дорівнює 14.
1 - 2 - 4: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f " Symbol "\ s 13 ® 3 SYMBOL 174 \ f" Symbol "\ s 13 ® 5SYMBOL 174 \ f" Symbol "\ s 13 ® 1, дорівнює 13. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що з 1го міста йдемо в 2й, з 2го в 4й. Вона дорівнює 13.
1 - 2 - 5: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f " Symbol "\ s 13 ® 4 SYMBOL 174 \ f" Symbol "\ s 13 ® 3SYMBOL 174 \ f" Symbol "\ s 13 ® 1, дорівнює 16. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що з 1го міста йдемо в 2й, з 2го в 5й. Вона дорівнює 12.
●
Проаналізуємо отримані результати. Перехід у вершини 3 та 4 дає погіршення критерію, тому дані вершини іменуються мертвими й розгалуження з них далі безглуздо. Далі будемо гілкуватися в 5й вершині.
1 - 2 - 5-3: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 4SYMBOL 174 \ f "Symbol" \ s 13 ® 1, дорівнює 17. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що з 1го міста йдемо в 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 5SYMBOL 174 \ f "Symbol" \ s 13 ® 3. Вона дорівнює 15.
1 - 2 - 5-4: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 3SYMBOL 174 \ f "Symbol" \ s 13 ® 1, дорівнює 16. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що з 1го міста йдемо в 2й, з 2го в 5й. Вона дорівнює 13.
13/12
●
В результаті рішення задачі, далі гілкуватися нам не куди. Запишемо оптимальний маршрут комівояжера:
1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 3SYMBOL 174 \ f "Symbol" \ s 13 ® 1
Таким чином, задача вирішена.
Реальні прикладні задачі дискретної оптимізації дуже складні. Сучасні методи оптимізації далеко не завжди справляються з вирішенням реальних завдань без допомоги людини. Ні, поки такої теорії, яка врахувала б будь-які особливості функцій, що описують постановку задачі. Слід віддавати перевагу таким методам, якими простіше управляти в процесі виконання завдання.
2. Беллмана, Р. Прикладні задачі динамічного програмування - М.: Наука, 1965. - 457 с.
3. Сігал І.Х., Іванова А.П. Введення в прикладне дискретне програмування: моделі та обчислювальні алгоритми. М.: Фізматліт, 2003. - 240 с.
4. Р. Беллмана, С. Дрейфус Прикладні задачі динамічного програмування - М., 1965 р., 460 стор
В * ({2, 4}, 3) = min [B * ({2}, 4) + s43; B * ({4}, 2) + s23] = min (6 + 4; 9 + 5) = 10;
В * ({3, 4}, 2}) = min [B * ({3}, 4) + s42; B * ({4}, 3) + s32] = min (4 + 5; 8 + 2) = 9;
В * ({2, 3, 4}, 1) = min [B * ({2, 3}, 4) + s41; B * ({2, 4}, 3) + s31; B * ({3, 4}, 2) + s21;] = min (7 + 1; 10 +6; 9 + 2) = 8.
Отже, оптимальне значення критерію в розглянутому прикладі дорівнює 8.
Виконані виділення дозволяють визначити оптимальний маршрут. Він наступний:
1 SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 1.
4. Завдання комівояжера методом гілок і меж
Іншим алгоритмом розв'язання задачі комівояжера є метод гілок і меж. По суті, це деяка модифікація повного перебору рішень, оптимізується за рахунок того, що за певними ознаками відсікаються неоптимальні безлічі перебору.Формально будується дерево варіантів, починаючи від кореня. У корені необхідно дати верхню і нижню оцінки. Далі галузиться. Чим менший фрагмент дерева доведеться побудувати, тим успішніше спрацював метод гілок і меж.
Мають місце наступні визначення:
Поточний рекорд - найбільша з отриманих в процесі реалізації методу нижніх оцінок.
Вершина іменується мертвою, якщо верхня оцінка в ній не перевищує поточного рекорду. Виконувати в ній подальше розгалуження марно.
Термінальній називається вершина, в якій верхня і нижня оцінки збігаються.
Вершина, розгалуження в якій вже виконано, називається закритою.
Вершини, які не є мертвими, термінальними або закритими, називаються відкритими. Подальше розгалуження робимо в них.
Рішення закінчується тоді, коли в нашому дереві варіантів немає відкритих вершин. Оптимальним рішенням буде поточний рекорд.
Верхня оцінка визначається за допомогою «жадібного» алгоритму.
Жадібний алгоритм - алгоритм знаходження найкоротшого відстані методом вибору найкоротшого, ще не обраного ребра, за умови, що воно не утворює циклу з вже обраними ребрами. "Жодний" цей алгоритм названий тому, що на останніх кроках доводиться жорстоко розплачуватися за жадібність (останнє ребро, як правило, найбільше або близько до нього по довжині).
Стратегія: «йди до найближчого (до якого ще не входив) місто». Розглянемо для прикладу мережу на рис. 2, що представляє вузький ромб. Нехай комівояжер стартує з міста 1. Алгоритм «Іди ви найближче місто» виведе його в місто 2, потім 3, потім 4; на останньому кроці доведеться платити за жадібність, повертаючись по довгій діагоналі ромба. У результаті вийде не найкоротший, а довжелезний тур.
Щоб обчислити нижню оцінку, спочатку підсумовуємо мінімальні елементи по рядках і по стовпцях, а потім з отриманих сум вибираємо найбільшу, але треба враховувати конфлікт.
Приклад 2.1 Вирішити методом гілок і меж завдання комівояжера, яка визначається матрицею:
1. Обчислюємо верхню і нижню оцінки в корені:
Верхню оцінку підраховуємо, користуючись, так званим, «жадібним» алгоритмом: кожен перехід робимо з поточного в найближче місто. Отримуємо маршрут:
1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f "Symbol" \ s 13 ® 1
Сумарна вартість даного маршруту дорівнює 12, вона визначає верхню оцінку в корені.
Щоб обчислити нижню оцінку, спочатку підсумовуємо мінімальні елементи по рядках і по стовпцях, а потім з отриманих сум вибираємо найбільшу:
За рядками: 2 + 1 + 2 + 2 + 2 = 9
За стовпцях: 2 + 2 + 3 + 1 + 2 = 10
Вибираємо максимум із значень і вибираємо 10.
Проаналізуємо стовпці: можемо зрушитися на 2 (конфлікт). Звідси нижня межа дорівнює 10 + 2 = 12.
●
|
|
| ||||
| ||||
Далі підраховуємо верхні і нижні оцінки для нових вершин:
1 - 2: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною
вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f "Symbol" \ s 13 ® 1 дорівнює 13. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що йдемо з 1го міста у 2й. Вона співпадає з нижньою оцінкою в корені і дорівнює 12.
1 - 3: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f "Symbol" \ s 13 ® 4SYMBOL 174 \ f "Symbol" \ s 13 ® 1, дорівнює 16. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що з 1го міста йдемо в 3й. Вона дорівнює 2 +2 +4 + 1 +2 = 11 і плюс 2 з урахуванням конфлікту. Разом отримуємо 13.
1 - 4: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 5SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 1 дорівнює 24. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що йдемо з 1го міста в 4й. Вона дорівнює 18.
1 - 5: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 2SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 1 дорівнює 23. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що йдемо з 1го міста в 5й. І вона дорівнює 16
|
|
|
16/13 |
| |||||||||||||||
|
| ||||||||||||||
| |||||||||||||||
| |||||||||||||||
Проаналізуємо отримані результати. Поточний рекорд дорівнює 12.
Перехід у вершини 3, 4 і 5 дає погіршення критерію, тому дані вершини іменуються мертвими й розгалуження з них далі безглуздо. Далі будемо гілкуватися в 2 і 3 вершинах.
1 - 2 - 3: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f " Symbol "\ s 13 ® 4 SYMBOL 174 \ f" Symbol "\ s 13 ® 5 SYMBOL 174 \ f" Symbol "\ s 13 ® 1 дорівнює 19. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що йдемо з 1го міста у 2й, з 2го в 3й. Вона дорівнює 14.
1 - 2 - 4: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f " Symbol "\ s 13 ® 3 SYMBOL 174 \ f" Symbol "\ s 13 ® 5SYMBOL 174 \ f" Symbol "\ s 13 ® 1, дорівнює 13. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що з 1го міста йдемо в 2й, з 2го в 4й. Вона дорівнює 13.
1 - 2 - 5: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f " Symbol "\ s 13 ® 4 SYMBOL 174 \ f" Symbol "\ s 13 ® 3SYMBOL 174 \ f" Symbol "\ s 13 ® 1, дорівнює 16. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що з 1го міста йдемо в 2й, з 2го в 5й. Вона дорівнює 12.
| |||
| |||
|
|
|
|
|
24/18 |
19/14 |
1-2-3 |
1-2-4 |
1-2-3 |
1-2-5 |
| |||||||||
| |||||||||
|
| |||||
Проаналізуємо отримані результати. Перехід у вершини 3 та 4 дає погіршення критерію, тому дані вершини іменуються мертвими й розгалуження з них далі безглуздо. Далі будемо гілкуватися в 5й вершині.
1 - 2 - 5-3: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f "Symbol" \ s 13 ® 3 SYMBOL 174 \ f "Symbol" \ s 13 ® 4SYMBOL 174 \ f "Symbol" \ s 13 ® 1, дорівнює 17. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що з 1го міста йдемо в 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 5SYMBOL 174 \ f "Symbol" \ s 13 ® 3. Вона дорівнює 15.
1 - 2 - 5-4: Верхня оцінка («жадібний алгоритм»), яка визначається сумарною вартістю даного маршруту 1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 3SYMBOL 174 \ f "Symbol" \ s 13 ® 1, дорівнює 16. Нижня оцінка визначається сумою мінімальних елементів рядків з урахуванням того, що з 1го міста йдемо в 2й, з 2го в 5й. Вона дорівнює 13.
13/12
|
|
|
24/18 |
1 - 3 |
16/13 |
1-2-3 |
1-2-4 |
1-2-3 |
1-2-3 |
1-2-5 |
19/14 |
16/12 |
|
1-2-5-4 |
16/13 |
| ||||||||
| ||||||||
В результаті рішення задачі, далі гілкуватися нам не куди. Запишемо оптимальний маршрут комівояжера:
1 SYMBOL 174 \ f "Symbol" \ s 13 ® 2 SYMBOL 174 \ f "Symbol" \ s 13 ® 5 SYMBOL 174 \ f "Symbol" \ s 13 ® 4 SYMBOL 174 \ f "Symbol" \ s 13 ® 3SYMBOL 174 \ f "Symbol" \ s 13 ® 1
Таким чином, задача вирішена.
Висновок
Практика породжує все нові й нові завдання оптимізації, причому їх складність зростає. Потрібні нові математичні моделі і методи, які враховують наявність багатьох критеріїв, проводять глобальний пошук оптимуму. Іншими словами, життя змушує розвивати математичний апарат оптимізації.Реальні прикладні задачі дискретної оптимізації дуже складні. Сучасні методи оптимізації далеко не завжди справляються з вирішенням реальних завдань без допомоги людини. Ні, поки такої теорії, яка врахувала б будь-які особливості функцій, що описують постановку задачі. Слід віддавати перевагу таким методам, якими простіше управляти в процесі виконання завдання.
Список використаних джерел
1. Беллмана, Р. Динамічне програмування - М.: ІЛ, 1960 .- 400 с.2. Беллмана, Р. Прикладні задачі динамічного програмування - М.: Наука, 1965. - 457 с.
3. Сігал І.Х., Іванова А.П. Введення в прикладне дискретне програмування: моделі та обчислювальні алгоритми. М.: Фізматліт, 2003. - 240 с.
4. Р. Беллмана, С. Дрейфус Прикладні задачі динамічного програмування - М., 1965 р., 460 стор