a
b
c
d
x
y
z
AC
i
Randomize
Про калькулятор задачі комівояжера
Розв'яжіть задачу комівояжера онлайн методом гілок і меж з детальним покроковим розв'язком. з повним, детальним, покроковим описом розв'язань, що розв'язує задачі лінійного програмування розміром до 20×20 з коефіцієнтами таких типів: десяткові числа та дроби.
Щоб почати обчислення, спочатку необхідно ввести розміри задачі у поля вводу у верхній частині екрана, а також вибрати потрібну операцію з бічного меню.
Нижче знаходиться вікно вводу, де за допомогою клавіатури потрібно ввести коефіцієнти, обмеження та значення правих частин. Тут також розташована панель керування вводом, яка спрощує роботу із задачами ЛП і містить такі елементи керування:
- Перший елемент дозволяє розгорнути вікно вводу. Це може бути особливо корисно, коли таблиця не вміщається повністю на екрані. Якщо таблиця все ще не повністю видна після розгортання вікна, можна змінити масштаб за допомогою кнопок + / -;
- Другий елемент копіює поточні вхідні дані задачі до буфера пам'яті. Це може бути корисно, коли ви часто розв'язуєте ту саму задачу ЛП або потрібно переносити дані між операціями;
- Останній елемент вставляє раніше скопійовані вхідні дані, що дозволяє відновити дані задачі лише кількома кліками замість повторного введення вручну;
Далі внизу знаходиться панель інструментів, яка дозволяє налаштувати калькулятор та спростити роботу з ним. Вона візуально розділена на три частини, кожна з яких відповідає за таку функціональність:
- Перша частина дозволяє вибрати формат чисел при відображенні результату розв'язання. Також можна вимкнути покрокові коментарі, якщо ви вже розумієте метод і потребуєте лише перевірки власних обчислень, або приховати покрокове розв'язання повністю, якщо потрібна лише кінцева відповідь;
- Друга частина містить кнопки для зміни розмірів таблиці вводу, очищення окремих коефіцієнтів або всього вводу, а також головну кнопку зі знаком рівності, що переводить на екран розв'язання. Всі ці кнопки продубльовані клавіатурними скороченнями. Наведіть курсор на кнопку, щоб побачити відповідну клавішу у підказці. Також можна використовувати клавіші зі стрілками для переміщення курсора між полями вводу;
- Остання частина дозволяє вибрати кількість знаків після коми для округлення нецілих результатів. Попередній перегляд показує, як виглядатимуть округлені значення;
Що таке задача комівояжера?
Задача комівояжера (TSP) — класична NP-важка задача комбінаторної оптимізації: дано повний зважений граф з n міст, знайти найкоротший гамільтонів цикл — замкнений маршрут, що відвідує кожне місто рівно один раз і повертається до початкового міста. Загальна кількість можливих маршрутів зростає факторіально з n, роблячи повний перебір непрактичним навіть для помірних розмірів, тому використовуються точні методи, такі як метод гілок і меж, для обрізання простору пошуку.
Як розв'язати задачу комівояжера методом гілок і меж?
Починайте з редукції матриці витрат: відніміть мінімум рядка від кожного рядка, потім мінімум стовпця від кожного стовпця; сума всіх редукцій є нижньою межею оптимального маршруту. На кожному кроці розгалуження оберіть ребро (i, j) з нульовою вартістю для включення або виключення. Для гілки ПРИЙНЯТИ: видаліть рядок i та стовпець j з матриці, заблокуйте зворотне ребро (j, i) нескінченністю для запобігання передчасним підмаршрутам і редукуйте знову. Для гілки ВІДХИЛИТИ: встановіть вартість (i, j) рівною нескінченності та редукуйте. Порівняйте нижні межі обох гілок і спочатку досліджуйте більш перспективну. Продовжуйте, поки не буде ідентифіковано повний гамільтонів цикл.
Приклад розв'язання задачі комівояжера методом гілок і меж
Розв'язання задачі починаємо з попереднього етапу. Для цього шукаємо найменші значення у рядках матриці (записуємо їх у зелений стовпець праворуч від матриці) і віднімаємо їх поелементно, отримуючи проміжну матрицю. Потім для отриманої матриці шукаємо найменші значення у стовпцях (записуємо їх у синій рядок під матрицею).
Знаходимо суму найменших значень у рядках і стовпцях та присвоюємо отримане значення накопичувальній змінній D
D = 18
Для проміжної матриці відніманням по елементах найменшого значення у стовпцях отримуємо матрицю, де в кожному рядку і стовпці є хоча б один нуль. Для кожного нуля матриці обчислюємо суму найменших значень у рядках і стовпцях, де розташовані відповідні нулі, не враховуючи самі нулі. Отримані значення записуємо в дужках.
Подальше розв'язання ведемо відносно нуля з найбільшою оцінкою, обчисленою на попередньому етапі.
Індекс, під яким знаходиться цей нуль, вказує на гілкове ребро.
Необхідно перевірити, чи слід включати це ребро до загального шляху чи ні.
Перевіримо, наскільки збільшиться вартість переміщення по маршруту без поточного гілкового ребра. Перевірка здійснюється шляхом заміни нуля з найбільшою оцінкою на M (нескінченність), після чого виконуємо редукцію матриці.
Матриця редукується шляхом пошуку в початковій матриці мінімальних значень у кожному рядку та поелементного віднімання їх від усіх елементів рядка. В отриманій матриці у кожному стовпці визначаємо мінімальне значення і поелементно віднімаємо його від усіх елементів стовпця.
Знаходимо суму найменших значень у рядках і стовпцях та визначаємо, наскільки збільшиться вартість переміщення по маршруту без поточного гілкового ребра.
H(2*,1*) = 6
Перевіримо, наскільки збільшиться вартість переміщення по маршруту, якщо додати поточне гілкове ребро до загального шляху. На основі цих даних приймаємо рішення про включення гілкового ребра до загального шляху або про вибір іншого шляху.
Перевірка виконується виключенням i-го рядка та j-го стовпця з матриці, де i, j — індекс елемента, відносно якого приймається рішення.
В отриманій матриці необхідно замінити на M (нескінченність) елемент під індексом, оберненим до того, що має елемент, відносно якого приймається рішення.
Потім знаходимо найменші значення за рядками і стовпцями матриці.
Потім для кожного нуля матриці обчислюємо суму найменших значень у рядках і стовпцях, де розташовані відповідні нулі, не враховуючи самі нулі.
Отримані значення записуємо в дужках.
Знаходимо суму найменших значень у рядках і стовпцях та визначаємо вартість переміщення по поточному гілковому ребру.
H(2,1) = 0
Оскільки H(2,1) <= H(2*,1*), то включаємо це ребро до загального шляху.
Подальше розв'язання ведемо відносно нуля з найбільшою оцінкою, обчисленою на попередньому етапі.
Індекс, під яким знаходиться цей нуль, вказує на гілкове ребро.
Необхідно перевірити, чи слід включати це ребро до загального шляху чи ні.
Перевіримо, наскільки збільшиться вартість переміщення по маршруту без поточного гілкового ребра. Перевірка здійснюється шляхом заміни нуля з найбільшою оцінкою на M (нескінченність), після чого виконуємо редукцію матриці.
Матриця редукується шляхом пошуку в початковій матриці мінімальних значень у кожному рядку та поелементного віднімання їх від усіх елементів рядка. В отриманій матриці у кожному стовпці визначаємо мінімальне значення і поелементно віднімаємо його від усіх елементів стовпця.
Знаходимо суму найменших значень у рядках і стовпцях та визначаємо, наскільки збільшиться вартість переміщення по маршруту без поточного гілкового ребра.
H(1*,4*) = 9
Перевіримо, наскільки збільшиться вартість переміщення по маршруту, якщо додати поточне гілкове ребро до загального шляху. На основі цих даних приймаємо рішення про включення гілкового ребра до загального шляху або про вибір іншого шляху.
Перевірка виконується виключенням i-го рядка та j-го стовпця з матриці, де i, j — індекс елемента, відносно якого приймається рішення.
В отриманій матриці необхідно замінити на M (нескінченність) елемент під індексом, оберненим до того, що має елемент, відносно якого приймається рішення.
Потім знаходимо найменші значення за рядками і стовпцями матриці.
Потім для кожного нуля матриці обчислюємо суму найменших значень у рядках і стовпцях, де розташовані відповідні нулі, не враховуючи самі нулі.
Отримані значення записуємо в дужках.
Знаходимо суму найменших значень у рядках і стовпцях та визначаємо вартість переміщення по поточному гілковому ребру.
H(1,4) = 7
Оскільки H(1,4) <= H(1*,4*), то включаємо це ребро до загального шляху.
Результат:
Вартість всього маршруту:
D = 18 + 0 + 7 + 0 + 0 = 25
Маршрут:
H(2,1) => H(1,4) => H(3,2) => H(4,3)
Часті запитання
Що знаходить калькулятор задачі комівояжера?
Він знаходить найкоротший можливий маршрут, який проходить через кожне місто рівно один раз і повертається до початку, за заданою матрицею попарних відстаней або вартостей.
Як тут працює метод гілок і меж?
Він будує дерево пошуку та обчислює нижню межу довжини маршруту для кожної гілки шляхом зведення рядків і стовпців матриці вартостей. Гілки, які не можуть перевершити найкращий знайдений маршрут, відсікаються, що дозволяє не перевіряти всі перестановки.
Чому діагональні клітинки позначені «M»?
Діагональ відповідає відстані міста до самого себе, яка ніколи не є частиною маршруту. Її встановлюють у дуже велике значення (M), щоб алгоритм ніколи її не обирав.
Чи завжди калькулятор повертає точно найкоротший маршрут?
Так. Метод гілок і меж є точним методом — він досліджує достатню частину дерева, щоб гарантувати оптимум, пропускаючи лише ті гілки, які доказово не можуть покращити найкращий відомий маршрут.