Материал: 24_41
Найчастіше кількість спроб, які необхідно зробити для одер жання шуканого розв'язку задачі, дорівнює 2N або N1, де N - кількість вхідних даних. У цьому випадку збільшення вхідних даних лише на один елемент приводить до подвоєння спроб по шуку розв'язку або до збільшення їх у (N + 1) разів. Це набага то більше, ніж поліноміальна складність алгоритму. Напри клад, якщо N = 10, то 102 = 100, а 21 0 = 1024 та 10! = 3 628 800. Коментарі до наведених прикладів зайві.
Отже, можна зробити висновок, що для отримання шукано го розв'язку задачі, що відноситься до класу NP, необхідно пе ребрати всі можливі варіанти таких розв'язків і, порівнюючи отримані відповіді, вибрати шукану. Якщо ми говорили, що за дачі класу Р називаються практично розв'язуваними, то навіть при не дуже великій кількості вхідних даних задачі класу NP можуть практично не розв'язуватися.
Ті задачі, для яких не знайдено поліноміального алгоритму розв'язку, називаються NP-повними. Але, з іншого боку, не можна стверджувати, що таких поліноміальних розв'язків не існує. Вивчення NP-повних задач на сьогоднішній день є однією з найцікавіших і складних проблем теорії обчислень. Будемо говорити, що якщо для деякої задачі не вдалося знайти поліноміального розв'язку, то вона є NP-повною і є підстави вважати її практично не розв'язуваною. Які можуть існувати шляхи виходу із ситуації, що складається навколо NP-повних задач? Можливо, краще витратити час на побудову наближено го алгоритму розв'язання даної задачі або обмежитися перебо ром усіх можливих розв'язків для одержання шуканої відпові ді при невеликій кількості вхідних даних.
Наведемо далі кілька прикладів задач, що відносяться до класу NP.
Задача про комівояжера
Відома відстань між будь-якою парою ./V міст. Стартуючи з будь-якого міста, комівояжер повинен побувати в решті (N - 1) міст лише по одному разу і повернутися у місто, з якого він по чав свою подорож. Треба знайти найкоротший маршрут відвідання всіх заданих міст.
Наша задача зводиться до того, щоб перебрати всі можливі ва ріанти послідовностей об'їзду N міст, одночасно додаючи відстані між цими містами. Одержавши і порівнявши всі одержані довжи ни шляхів, необхідно буде вибрати серед них найменшу (мал. 4).
Для перебору всіх можливих варіантів об'їзду N міст слід використати алгоритм генерації перестановок їх порядкових номерів. Для кожного із цих варіантів будемо рахувати суму довжин відстаней між сусідніми містами у визначеній пере-
39
Мал. 4
становці. У результаті задача зводиться до пошуку мінімально го значення серед довжин усіх можливих маршрутів комівоя жера.
Як підрахувати довжину поточного маршруту? Нехай, на приклад, для N = 5 поточний маршрут визначається такою по слідовністю номерів міст: 2 5 1 3 4. Тоді довжина маршруту може
бути представлена таким чином: d[2 5] + cL5 Х] + d„ 3] + <і[3 4] + d[4 2] . Як бачимо, необхідно не забувати про те, що комівояжер пови
нен повернутися у місто, з якого він почав свій об'їзд: d[4 2] . До речі, згідно з наведеним прикладом, можна стверджувати, що об'їзд починається і завершується у місті з номером 2.
Визначимо кількість можливих маршрутів для N міст. Оскільки будь-який із цих маршрутів повинен починатися і за вершуватися в одному і тому самому місті, то перестановкам підлягають всі решта (N - 1) міст. Тому кількість можливих маршрутів дорівнює (N - 1)!.
Схематично всі можливі варіанти об'їзду 5 міст, зображених на малюнку 4, починаючи і завершуючи їх у місті з номером 1, можна представити так, як це показано на малюнку 5.
На малюнку 5 можемо побачити, що при кількості міст 5 кіль кість можливих маршрутів їх об'їзду складає 24. Серед них як мінімум один є найкоротшим.
Мал. 5
40
Ми вже ознайомилися з такою структурою даних, як дерево. Тому, проаналізувавши схему, зображену на малюнку 5, можна зробити висновок, що розв'язок задачі про комівояжера пред ставляється у вигляді дерева, вершиною якого є номер міста, з якого починається об'їзд, починаючи з кореня дерева, у якому вершини на кожному рівні мають відповідно (N - 1),(N - 2), ..., 2, 1 нащадків. Особливістю даного дерева є те, що термінальною вершиною є вершина, з якої починається об'їзд усіх міст.
Наведемо фрагмент тексту Pascal-програми, що реалізує описаний алгоритм:
f o r i := 1 t o f - 1 do |
|
{f=(/v - i)!} |
|
begin |
|
|
|
permutation; |
|
{Одержання поточної перестановки.} |
|
sum := 0; |
|
{Ініціалізація одержання довжини поточного маршруту.} |
|
for j := 1 to П — 1 do |
|
{Одержання довжини поточного маршруту.} |
|
sum := sum |
+ d [ a [ j ] , |
a[j + |
1 ] ] ; |
sum := sum + d [ a [ n ] , a [ 1 ] ] ; |
{Додавання останньої ланки маршруту.} |
||
if sum < min then |
|
{Перевірка оптимальності поточного маршруту.} |
|
begin |
|
|
|
min : = s u m ; |
|
{Визначення оптимального поточного маршруту.} |
|
Ь := а |
{Збереження послідовності об'їзду міст оптимального маршруту.} |
||
end; |
|
|
|
end; |
|
|
|
Ініціалізацію початкового стану нашої задачі можнаї вико нати такою послідовністю команд:
f : = 1 ; m i n : = 0 ; {Ініціалізація підрахунку значення факторіалу та довжини початкового}
а[1 ] := к; |
{маршруту. Вершина з номером к є початком будь-якого маршруту.} |
|
j := 2; |
|
{Визначення решти маршрутів.} |
for і := 1 to n do |
{Перебір усіх номерів міст.} |
|
if І О k |
|
{Перевірка того, чи не збігається значення поточного міста з к.} |
then |
|
|
begin |
|
|
a[j] := і; |
{Визначення поточного міста початкового маршруту.} |
|
inc(j) |
|
{Перехід до розгляду наступного за номером міста.} |
end; |
|
|
Для одержання стартового значення довжини маршруту, що відповідає першій перестановці заданих міст, можна виконати таку послідовність команд:
for і := 1 to п - 1 do begin
min := min + d[a[i], a[i + 1]]; f :=f *i;
end;
min:=min + d[a[n],a[1]]; b :=a;
41