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


         

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


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

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

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

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


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