Задача комівояжера
Деякі задачі розв’язують, перебираючи можливі розв’язки і перевіряючи, яке з них істина. При цьому треба подбати, щоб істинний розв’язок був серед можливих, інакше його не знайти. Якщо невідомий інший спосіб ро в’язку задачі, її називають переборною.
Класичним прикладом переборної задачі служить задача комівояжера. Дано множину з N міст, відстані між який відомі. У якому порядку повинний відвідати їх комівояжер, заїжджаючи в кожне місто лише один раз, щоб загальний пройдений шлях був найкоротшим?
Можливими розв’язками тут є перестановки з N міст. З них потрібно вибрати ту, що дасть найменшу сумарну довжину маршруту. Перше, що потрібно зробити, розв’язуючи задачу комівояжера, це організувати перебір перестановок. Занумеруємо міста числами від 1 до N. Всі пере оротшим?
Можливими розв’язками тут є перестановки з N міст. З них потрібно вибрати ту, що дасть найменшу сумарну довжину маршруту. Перше, що потрібно зробити, розв’язуючи задачу комівояжера, це організувати перебір перестановок. Занумеруємо міста числами від 1 до N. Всі перестановки можна одержати, обираючи з множини [1..N] один елемент усілякими способами і приєднуючи до нього по черзі перестановки з елементів , що залишилися. Це рекурсивний алгоритм, тому що для одержання побудови перестановок із N елементів він потребує перестановку з N-1 елемента. Додамо, що єдина перестановка з одного елемента - це самий елемент.
Запрограмуємо одержання перестановок у вигляді рекурсивної процедури. Множину елементів, що переставляються, зробимо параметром процедури. Іншим параметром буде позиція перестановки, що заповнюється даним викликом процедури. Всі становки можна одержати, обираючи з множини [1..N] один елемент усілякими способами і приєднуючи до нього по черзі перестановки з елементів , що залишилися. Це рекурсивний алгоритм, тому що для одержання побудови перестановок із N елементів він потребує перестановку з N-1 елемента. Додамо, що єдина перестановка з одного елемента - це самий елемент.
Запрограмуємо одержання перестановок у вигляді рекурсивної процедури. Множину елементів, що переставляються, зробимо параметром процедури. Іншим параметром буде позиція перестановки, що заповнюється даним викликом процедури. Всі перестановки будемо по черзі будувати в зовнішньому масиві з N цілих чисел.
Програма одержання перестановок з множини чисел [1..N]
Program Perebor;
Const
N=5;
Type
IntSet = Set Of 1..N;
Var
A: Array [1..N] Of Integer;
о, що єдина перестановка з одного елемента - це самий елемент.
Запрограмуємо одержання перестановок у вигляді рекурсивної процедури. Множину елементів, що переставляються, зробимо параметром процедури. Іншим параметром буде позиція перестановки, що заповнюється даним викликом процедури. Всі перестановки будемо по черзі будувати в зовнішньому масиві з N цілих чисел.
Програма одержання перестановок з множини чисел [1..N]
Program Perebor;
Const
N=5;
Type
IntSet = Set Of 1..N;
Var
A: Array [1..N] Of Integer;
Procedure Perest (S: IntSet; K: Integer);
Var
I: Integer;
Begin
For I:=1 To N Do
If I In S Then
Begin
A[K]:=I;
Perest(S-[I], K+1)
End
End;
Begin
Perest([1..N], 1);
End.
Ця програма тільки будує перестановки в масиві А і більше нічого не робить, навіть не виводить їх на екран. Перестановка готова, коли S=[].
Доповнимо процедуру Perest підрахунком довжини маршруту, заданого перестановкою, і вибором самого короткого з маршрутів. Для схову найкоротшого з побудованих маршрутів і його довжини скористаємося зовнішніми змінними Amin і Lmin. Відстані між містами утримуються в двовимірному масиві Dist.
Попробуйте самостійно розв’язати задачу комівояжера.
Метод гілок і меж
Головна складність переборних задач у тому, що кількість можливих розв’язків буває в буквальному значенні безмежним. Порахуйте, скільки існує перестановок, скажемо, із 50 міст. Навіть якщо комп'ютер зможе опрацьовувати по мільйону перестановок у секунду то на це пішло б багато часу. Як же розв’язують такі задачі? Один із підходів полягає в тому, щоб знайти таку стратегію перебору й аналізу можливих вирішень, коли можна відкидати їх цілими групами, не займаючись перевіркою кожного окремо.
Наприклад, якщо для комівояжера знайдений маршрут довжиною Lrnin, а заїзд до перших K міст чергового варіанта вже дає довжину, більшу, ніж Lrnin, то вже нема чого перевіряти не тільки цей варіант, але і всі маршрути, що збігаються з ним у перших K містах.
Перебір маршрутів можна розглядати як прямування по гілках дерев, а відкидання маршрутів - як відсікання гілок дерева на межі досягнення ними вже знайденої мінімальної довжини маршруту. Цим пояснюється назва методу гілок і меж.
Метод гілок і меж не є алгоритмом вирішення переборних задач. Його можна вважати ідеєю вирішення, що потребує творчого підходу для кожної оригінальної задачі. |
