Основы теории нейронных сетей



         

Задача коммивояжера


Задача коммивояжера является оптимизационной задачей, часто возникающей на практике. Она может быть сформулирована следующим образом: для некоторой группы городов с заданными расстояниями между ними требуется найти кратчайший маршрут с посещением каждого города один раз и с возвращением в исходную точку. Было доказано, что эта задача принадлежит большому множеству задач, называемых "NP-полными" (недетерминистски полиномиальными). Для NP-полных задач не известно лучшего метода решения, чем полный перебор всех возможных вариантов, и, по мнению большинства математиков, маловероятно, чтобы лучший метод был когда-либо найден. Так как такой полный поиск практически неосуществим для большого числа городов, то эвристические методы используются для нахождения приемлемых, хотя и неоптимальных решений.

Существует решение этой задачи, основанное на сетях с обратными связями. Допустим, что города, которые необходимо посетить, помечены буквами

A
,
B
,
C
и
D
, а расстояния между парами городов есть
d_{ab}
,
d_{bc}
и т.д.

Решением является упорядоченное множество из

n
городов. Задача состоит в отображении его в вычислительную сеть с использованием нейронов в режиме с большой крутизной характеристики (
\lambda

приближается к бесконечности). Каждый город представлен строкой из

n

нейронов. Выход одного и только одного нейрона из них равен единице (все остальные равны нулю). Этот равный единице выход нейрона показывает порядковый номер, в котором данный город посещается при обходе. В табл. 23.1 приведен случай, когда город

C
посещается первым, город
A
— вторым, город
D
— третьим и город
B
— четвертым. Для такого представления требуется
n^2
нейронов — число, которое быстро растет с увеличением числа городов. Длина полученного маршрута была бы равна
d_{ca} + d_{ad} + d_{db} + d_{bc}
. Так как каждый город посещается только один раз, и в каждый момент посещается лишь один город, то в каждой строке и в каждом столбце имеется по одной единице. Для задачи с
n

городами всего имеется

n!
различных маршрутов обхода. Если
n = 60
, то имеется
6934155\times 10^{78}
возможных маршрутов. Если принять во внимание, что в нашей галактике (Млечном Пути) имеется лишь
10^{11}




Содержание  Назад  Вперед