UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75843
останнє поновлення: 2016-12-04
за 7 днів додано 15

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваЗадача комівояжера (реферат)
Авторdimich
РозділІнформатика, компютерні науки
ФорматWord Doc
Тип документуРеферат
Продивилось2911
Скачало489
Опис
ЗАКАЧКА
Замовити оригінальну роботу

РЕФЕРАТ

 

на тему:

 

“Задача комівояжера”

 

Задача комівояжера є оптимізаційною задачею, що часто виникає на

практиці. Вона може бути сформульована таким чином: для деякої групи

міст із заданими відстанями між ними потрібно знайти найкоротший маршрут

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

точку. Було доведено, що ця задача належить великої множини задач,

званих "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)

 

де А, В і С - деякі константи. Цим досягається виконання наступних умов:

-----> Page:

0 [1] [2] [3]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ