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

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

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

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

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

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

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

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

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

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

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

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

город	Порядок следования
	1	2	3	4
A	0	1	0	0
B	0	0	0	1
C	1	0	0	0
D	0	0	1	0

Продемонстрируем теперь, как сконструировать сеть для решения этой NP-полной проблемы. Каждый нейрон снабжен двумя индексами, которые соответствуют городу и порядковому номеру его посещения в маршруте. Например, показывает, что город был -м по порядку городом маршрута.
Функция энергии должна удовлетворять двум требованиям: во-первых, должна быть малой только для тех решений, которые имеют по одной единице в каждой строке и в каждом столбце; во-вторых, должна оказывать предпочтение решениям с короткой длиной маршрута.
Первое требование удовлетворяется введением следующей, состоящей из трех сумм, функции энергии:

где , и — некоторые константы. Этим достигается выполнение следующих условий:

1. Первая тройная сумма равна нулю в том и только в том случае, если каждая строка (город) содержит не более одной единицы.
2. Вторая тройная сумма равна нулю в том и только в том случае, если каждый столбец (порядковый номер посещения) содержит не более одной единицы.
3. 
   Третья сумма равна нулю в том и только в том случае, если матрица содержит ровно
   
   единиц. Второе требование — предпочтение коротких маршрутов — удовлетворяется с помощью добавления следующего члена к функции энергии:
   
   

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


(член, отвечающий за длину цикла),
где , если , в противном случае . Кроме того, каждый нейрон имеет смещающий вес , соединенный с и равный .
Был проведен эксперимент, в котором задача коммивояжера была решена для 10 городов. В этом случае возбуждающая функция была равна

Как показали результаты, 16 из 20 прогонов сошлись к допустимому маршруту и около 50% решений оказались кратчайшими маршрутами, что было установлено с помощью полного перебора. Наш результат станет более впечатляющим, если осознать, что имеется 181440 допустимых маршрутов.

Содержание раздела

---