Задача коммивояжера и её реализация

 

     Знайдемо нижню межу φ(Z) = 15+1+0+16+5+5+5 = 47.

     Для знаходження претендентів на включення  до множини ребр, по яким буде проводитись  розгалуження, знайдемо степіні Θ_ij нульових елементів матриці (423) (суми мінімумів по рядкам і стовпчикам):

Θ₁₄ = 10 + 0, Θ₂₄ = 1 + 0, Θ₃₆ = 5+0, Θ₄₁ = 0 + 1, Θ₄₂ = 0 + 0, Θ₅₆ = 2 + 0, Θ₆₂= 0 + 0, Θ₆₃ = 0 + 9, Θ₆₅ = 0 + 2.

     Найбільша степінь Θ₁₄ = 10. Розгалуження проводимо по ребру (1,4).

     Нижня межа для множини залишається рівною 47. Для всіх маршрутів множини з міста A ми не переміщаємося в місто D. У матриці це позначається виставлянням в клітинку (1, 4) знака ∞. В результаті вихід із міста A додає до оцінки нижньої межі принаймні найменший елемент першого рядка. φ ( ) = 47 + 10.

     В матриці, яка відповідає , c₁₄= ∞ (табл. 1.4) 

«Таблиця 1.4. Платіжна Матриця»

	1	2	3	4	5	6
1	∞	11	27	∞	14	10
2	1	∞	15	0	29	24
3	15	13	∞	35	5	0
4	0	0	9	∞	2	2
5	2	41	22	43	∞	0
6	13	0	0	4	0	∞

 

     У матриці, що відповідає , викреслюємо перший рядок і четвертий стовпчик і покладемо c₄₁= ∞, щоб запобігти появи циклу 1→4→1. Одержимо нову платіжну матрицю(табл. 1.5): 
 
 
 

«Таблиця 1.5. Платіжна Матриця»

	1	2	3	5	6
2	1	∞	15	29	24
3	15	13	∞	5	0
4	∞	0	9	2	2
5	2	41	22	∞	0
6	13	0	0	0	∞

 

     Для зведеня треба відняти мінімуми по першому рядку: h₁=1. При цьому, нижня межа стане рівною 47+1 = 48. Порівнюючи нижні межі

φ ( ) = 67 та φ ( ) = 48 < 67 виділяємо підмножину маршрутів , який с великою ймовірністю включає маршрут мінімальної довжини.

     

                             «Рис. 1.6 Розгалуження на першому кроці»

Зведена платіжна матриця(табл. 1.6) для має вигляд: 

«Таблиця 1.6. Платіжна Матриця»

	1	2	3	5	6
2	0	∞	15	29	24
3	14	13	∞	5	0
4	∞	0	9	2	2
5	1	41	22	∞	0
6	12	0	0	0	∞

 

     Далі  продовжуємо процес розгалуження. Знайдемо степені Θ_ij нульових елементів матриці (табл. 1.6):

Θ₂₁ =16, Θ₃₆ = 5, Θ₄₂ = 2, Θ₅₆ = 2, Θ₆₂ = 0, Θ₆₃ =9, Θ₆₅ = 2.

     Як  видно, найбільша степінь - Θ₂₁. Далі, множина розбивається по ребру (4,1) на два нових і .

     В матриці для  викреслюємо рядок 2 и стовпчик 1. Ребра (1,4) і (2,4) утворюють зв’язний шлях, тому покладемо c₄₂= ∞, щоб запобігти появи циклу 2→1→ 4 → 2 (табл. 1.7) 

«Таблиця 1.7. Платіжна Матриця»

	2	3	5	6
3	13	∞	5	0
4	∞	9	2	2
5	41	22	∞	0
6	0	0	0	∞

 

     Аналогічно, до попередніх етапів проводимо зведення матриці по рядках (мінімум рядка 4: r₄=2). При цьому нижня межа стане рівною 48+2 = 50. Нижня межа для ,  буде рівною 48+15+1=64. Порівнюємо межі             φ ( ) = 64 та φ ( ) = 50 і вибираємо підмножину для продовження розгалуження.

     

                                «Рис. 1.7. Розгалуження на другому кроці»

     Зведена платіжна матриця(табл. 1.8) для  

«Таблиця 1.8. Платіжна Матриця»

	2	3	5	6
3	13	∞	5	0
4	∞	7	0	0
5	41	22	∞	0
6	0	0	0	∞

 

     Степені нульових елементів матриці (табл. 1.8)

     Θ₃₆ = 5, Θ₄₅ = 0, Θ₅₆ = 22, Θ₆₂ = 13, Θ₆₃ =7, Θ₆₅ = 0. Найбільша степінь Θ_56.

     Множина , по ребру (2,1),  розбивається на дві нових і .

Нижня межа для  - 50 + 22 = 72. В матриці для викреслюємо рядок 5 і стовпчик 6 и покладемо c₆₅= ∞. В результаті отримаємо матрицю (табл. 1.9): 

«Таблиця 1.9. Платіжна Матриця»

	2	3	5
3	13	∞	5
4	∞	7	0
6	0	0	∞

 

Для зведеня  віднімаємо по рядку 3: r₃=5. Нижня межа, при цьому, стане рівною 50+5 = 55. Для подальшого розгалуження вибираємо підмножину маршрутів .

Рис. 1.7. Розгалуження та третьому кроці. 

Зведена платіжна матриця(табл. 1.10) для

 «Таблиця 1.10. Платіжна Матриця»

	2	3	5
3	8	∞	0
4	∞	7	0
6	0	0	∞

 

Степені нульових елементів: Θ₃₅ = 8, Θ₄₅ = 7, Θ₆₂ = 8, Θ₆₃ =7.

Найбільша - Θ₃₅ = 8. Розбиваємо на і .

Нижня границя для рівна 55 + 8 = 64. В матриці(табл. 1.10) для викреслюємо рядок 3 і стовпчик 5 і покладемо c₆₃= ∞. Отримаємо: 

    «Таблиця 1.11. Платіжна Матриця»

	2	3
4	∞	7
6	0	∞

 

Віднімаємо  мінімум по рядку 4: r4=7. Нижня межа стане рівною 55+7 = 62. Після зведення отримається матриця(табл. 1.12) 

  «Таблиця 1.12. Платіжна Матриця»

	2	3
4	∞	0
6	0	∞

 

С двовимірної  матриці маємо два переходи нульової довжини: (4,3) та (6,2). 
 
 

 
 
 
 

«Рис. 1.8. Розгалуження на четвертому кроці.» 

     

                    «Рис. 1.9. Дерево розгалуження з оцінками» 

     Отриманий маршрут має вигляд z₀ = (1, 4, 3, 5, 6, 2, 1) або (A-D-C-E-F-B-A).

     Для порівняння використаємо програму (текст якої наведений в Додатку).

    1.5 Мурашиний алгоритм

 

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

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

                                

    Рис. 1.10

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