РЕФЕРАТ
на тему:
“Задача комівояжера”
Задача комівояжера є оптимізаційною задачею, що часто виникає на
практиці. Вона може бути сформульована таким чином: для деякої групи
міст із заданими відстанями між ними потрібно знайти найкоротший маршрут
з відвідуванням кожного міста один раз і з поверненням в початкову
точку. Було доведено, що ця задача належить великої множини задач,
званих “NP-повними” (недетерміновано поліноміальними). Для NP-повних
задач не відомо кращого методу рішення, ніж повний перебір всіх можливих
варіантів, і, на думку більшості математиків, малоймовірно, щоб кращий
метод був колись знайдений. Оскільки такий повний пошук практично
нездійсненний для великого числа міст, то евристичні методи
використовуються для знаходження прийнятних, хоч і неоптимальних рішень.
Описане в роботі рішення, засноване на мережах із зворотними зв’язками,
є типовим в цьому відношенні. Все ж відповідь виходить так швидко, що в
певних випадках метод може виявитися корисним.
Допустимо, що міста, які необхідно відвідати, помічені буквами А, В, С і
D, а відстані між парами міст є dab, dbc і т.д.
Рішенням є впорядкована множина з n міст. Задача складається у
відображенні його в обчислювальну мережу з використанням нейронів в
режимі з великою крутизною характеристики (наближається до
нескінченності). Кожне місто представлене рядком з n нейронів. Вихід
одного і тільки одного нейрона з них рівний одиниці (всі інші рівні
нулю). Цей рівний одиниці вихід нейрона показує порядковий номер, в
якому дане місто відвідується при обході. На рис. 6.6 показаний випадок,
коли місто С відвідується першим, місто А – другим, місто D – третім і
місто В – четвертим.
Для такого представлення потрібно n2 нейронів – число, яке швидко росте
із збільшенням числа міст. Довжина такого маршруту була б рівна dca +
dad + ddb + dbc. Оскільки кожне місто відвідується тільки один раз і в
кожний момент відвідується лише одне місто, то в кожному рядку і в
кожному стовпці є по одній одиниці. Для задачі з n містами всього є n!
різних маршрутів обходу. Якщо n = 60, то є 6934155х1078 можливих
маршрутів. Якщо брати до уваги, що в нашій галактиці (Чумацькому Шляху)
є лише 1011 зірок, то стане ясним, що повний перебір всіх можливих
маршрутів для 1000 міст навіть на самому швидкому в світі комп’ютері
займе час, порівнянний з геологічною епохою.
Продемонструємо тепер, як сконструювати мережу для розв’язання цієї
NP-повної проблеми. Кожний нейрон забезпечений двома індексами, які
відповідають місту і порядковому номеру його відвідування в маршруті.
Наприклад, OUTxj = 1 показує, що місто х було j-им по порядку містом
маршруту.
Функція енергії повинна задовольняти двом вимогам: по-перше, повинна
бути малою тільки для тих рішень, які мають по одній одиниці в кожному
рядку і в кожному стовпці; по-друге, повинна надавати перевагу рішенням
з короткою довжиною маршруту.
Перша вимога задовольняється введенням наступної, що складається з трьох
сум, функції енергії:
,(6.9)
де А, В і С – деякі константи. Цим досягається виконання наступних умов:
Перша потрійна сума рівна нулю в тому і тільки в тому випадку, якщо
кожний рядок (місто) містить не більше однієї одиниці.
Друга потрійна сума рівна нулю в тому і тільки в тому випадку, якщо
кожний стовпець (порядковий номер відвідування) містить не більше однієї
одиниці.
Третя сума рівна нулю в тому і тільки в тому випадку, якщо матриця
містить рівне n одиниць.
Місто Порядок відвідування
1 2 3 4
A 0 1 0 0
B 0 0 0 1
C 1 0 0 0
D 0 0 1 0
Рис. 6.6. Маршрут комівояжера
Друга вимога – перевага коротким маршрутам – задовольняється за
допомогою додавання наступного члена до функції енергії:
, (6.10)
Помітимо, що цей член являє собою довжину будь-якого припустимого
маршруту. Для зручності індекси визначаються по модулі n, тобто OUTn+j =
OUTj, a D – деяка константа.
При досить великих значеннях A, B і C низькоенергетичні стани будуть
представляти припустимі маршрути, а великі значення D гарантують, що
буде знайдений короткий маршрут.
Тепер задамо значення ваг, тобто встановимо відповідність між членами у
функції енергії і членами загальної форми (див. рівняння 6.2)).
Одержуємо
wxi,yi =
-Adxy(1 – dij) (не допускає більш однієї одиниці в рядку)
-B dij(1 – dxy) (не допускає більш однієї одиниці в стовпці)
-С (глобальне обмеження)
-Ddxy(dj,i+1 + dj,і-1) (член, відповідальний за довжину циклу),
де dij = 1, якщо i = j, у противному випадку dij = 0. Крім того, кожен
нейрон має зміщену вагу хі, з’єднаний з +1 і рівний Сn.
У роботі повідомляється про експеримент, у якому задача комівояжера була
вирішена для 10 міст. У цьому випадку збуджуюча функція дорівнює
OUT = Ѕ [1 + th(NET/U0)].
Як показали результати, 16 з 20 прогонів зійшлися до припустимого
маршруту і близько 50% рішень виявилися найкоротшими маршрутами, як це
було встановлено за допомогою повного перебору. Цей результат стане
більш вражаючим, якщо усвідомити, що є 181440 припустимих маршрутів.
Повідомлялося, що збіжність рішень, отриманих за методом Хопфілда для
задачі комівояжера, у сильному ступені залежить від коефіцієнтів, і
немає систематичного методу визначення їхніх значень. У цій роботі
запропонована інша функція енергії з єдиним коефіцієнтом, значення якого
легко визначається. На додаток запропонований новий збіжний алгоритм.
Можна чекати, що будуть розроблятися нові методи, тому що цілком
задовільне рішення знайшло би масу застосувань.
Задача
На острові розкидані горіхи. Лари хоче зібрати всі горіхи по
найкоротшому шляху і повернутися на вихідне місце.
Вхід. Перший рядок кожного тесту містить довжину x і ширину y острова
(x, y РІШЕННЯ
задача комівояжера, NP повнота, динамічне програмування
Аналіз алгоритму
Класична задача комівояжера. Варто знайти цикл мінімальної довжини, що
проходить по усіх вершинах графа. Чи те ж саме що знайти гамильтонов
цикл мінімальної довжини. Задача є NP повної і вимагає експонентного
часу для її рішення щодо числа вершин у графі.
Нехай n – число вершин у графі. Кожному горіху і початковому місцеві
розташування Лари поставимо у відповідність вершину графа. З умови
задачі випливає, що n ??16. Усі вершини графа будуть попарно з'єднані
(зважується евклидова задача комівояжера). Довжина ребра, що з'єднує
вершини яким відповідають координати (a, b) і (c, d), дорівнює max( |a –
c|, |b – d| ). Матрицю суміжності побудованого графа зберігаємо в
двовимірному масиві m.
Можна згенерувати за допомогою функції next_permutation усі можливі
перестановки чисел від 1 до n, кожній перестановці буде відповідати
гамильтонов цикл. Шукаємо мінімальне значення серед усіх довжин таких
циклів. Приведений алгоритм вимагає n! часу, що для n = 16 занадто
багато (варто перебрати 16! = 20922789888000 варіантів).
Використовуючи метод динамічного програмування, можна вирішити задачу з
оцінкою O(2n) по використовуваній пам'яті і O(n2 * 2n) за часом роботи
алгоритму. При n = 16 варто перебрати 16777216 варіантів, що реально за
часом.
Для непорожньої підмножини S ? {1, 2, …, n} і кожної вершини i ??S
визначимо dp(S, i) як довжину найкоротшого шляху, що починається в
першій (початкової) вершині, що проходить по усіх вершинах з безлічі S \
{i} у довільному порядку і закінчується у вершині i. Тоді мають місце
рівності:
dp({1, i}, i) = m[1][i],
(dp(S \ {i}, j) + m[j, i] )
Значення dp(S, i) перераховуємо динамічно, запам'ятовуючи їх у масиві
dp. Гамильтонов цикл мінімальної довжини дорівнює
(dp({1, 2, ..., n}, j) + m[j, 1] )
Приклад
У першому тесті досить пройти вниз острова (4 кроки), зібравши по шляху
всі горіхи, і піднятися нагору до вихідного місця (ще 4 кроки).
Реалізація алгоритму
Визначимо перемінну INF, умовно рівну нескінченності, максимально
можливе число вершин у графі MAX і масив dp, у якому будемо зберігати
динамічно перелічувані значення dp(S, i). Кожна підмножина S будемо
зберігати у виді числа, у якому i - ий біт дорівнює 1, якщо вершина з
номером i в ньому є присутнім, і нулю інакше. Наприклад, при n = 5
підмножина {1, 4, 5} кодується числом 110012 = 25.
#define INF 100000000
#define MAX 16
int dp[1Використана література
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для
инженера. - М.: Энергоатомиздат, 1988. - 480с.
Грэй П. Алгебра, логика и базы данных: Пер. с англ. - М.:
Машиностроение, 1989. - 260 с.
Оре О. Теория графов: Пер. с англ. - М.: Наука, 1968. - 310 с.
Форд Л., Фалкерсон Д. Потоки в сетях: Пер. с англ. - М.: Мир, 1966.–288
с.
Марков А.А., Нагорный Н.И. Теория алгоритмов. - М.: Наука, 1984.–300 с.
Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической
логике и теории алгоритмов. - М.: Наука, 1975.- 240 c.
Кэррол Л. История с узелками: Пер. с англ. - М.: Мир, 1973. - 408 c.
Нашли опечатку? Выделите и нажмите CTRL+Enter
