Пошук найкоротшого шляху кур’єра компанії «tianDE» на прикладі задачі кімівояжера

Класична постановка задачі комівояжера полягає в тому, що є

сукупність міст, які необхідно відвідати. Потрібно знайти оптимальний

(найкоротший) маршрут, який поєднує усі міста.

В технічних системах аналогом цієї задачі виступають задачі

прокладання лінії електропередач, об’єднання персональних ЕОМ в

комп’ютерну мережу, тощо.

Формалізуємо постановку задачі.

Задано n– об’єктів, які необхідно з’єднати між собою:

M=(M₁, M₂, М₃, …,М_n)

Задано матрицю відстаней:

D=I d_i,j I

Треба знайти перестановку об’єктів:

P_n= ,

для якої довжина маршруту

буде оптимальною.

Дата добавления: 2015-08-17