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

Задача коммивояжера является оптимизационной задачей, часто возникающей на практике. Она может быть сформулирована следующим образом: для некоторой группы городов с заданными расстояниями между ними требуется найти кратчайший маршрут с посещением каждого города один раз и с возвращением в исходную точку. Было доказано, что эта задача принадлежит большому множеству задач, называемых "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}$

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