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

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

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

, а расстояния между парами городов есть

и т.д.

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

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

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

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

посещается первым, город

— вторым, город

— третьим и город

— четвертым. Для такого представления требуется

нейронов — число, которое быстро растет с увеличением числа городов. Длина полученного маршрута была бы равна

. Так как каждый город посещается только один раз, и в каждый момент посещается лишь один город, то в каждой строке и в каждом столбце имеется по одной единице. Для задачи с

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

различных маршрутов обхода. Если

, то имеется

возможных маршрутов. Если принять во внимание, что в нашей галактике (Млечном Пути) имеется лишь

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