Цифрові пристрої зі зворотним зв’язком

Описане в роботі рішення, засноване на мережах із зворотними зв'язками, є типовим в цьому відношенні. Все ж відповідь виходить так швидко, що в певних випадках метод може виявитися корисним.

Допустимо, що міста, які необхідно відвідати, помічені буквами А, В, С і 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-им по порядку містом маршруту.Функція енергії повинна задовольняти двом вимогам: по-перше, повинна бути малою тільки для тих рішень, які мають по одній одиниці в кожному рядку і в кожному стовпці; по-друге, повинна надавати перевагу рішенням з короткою довжиною маршруту.

Перша вимога задовольняється введенням наступної, що складається з трьох сум, функції енергії:

,(4)

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

1.Перша потрійна сума рівна нулю в тому і тільки в тому випадку, якщо кожний рядок (місто) містить не більше однієї одиниці.

2.Друга потрійна сума рівна нулю в тому і тільки в тому випадку, якщо кожний стовпець (порядковий номер відвідування) містить не більше однієї одиниці.

3.Третя сума рівна нулю в тому і тільки в тому випадку, якщо матриця містить рівне n одиниць.

МістоПорядок відвідування

1234

A0100

B0001

C1000

D0010

Рис. 4. Маршрут комівояжера

Друга вимога - перевага коротким маршрутам - задовольняється за допомогою додавання наступного члена до функції енергії:

, (5)