Первая тройная сумма равна нулю в том и только в том случае, если каждая строка (город) содержит не более одной единицы.
Вторая тройная сумма равна нулю в том и только в том случае, если каждый столбец (порядковый номер посещения) содержит не более одной единицы.
Третья сумма равна нулю в том и только в том случае, если матрица содержит ровно п единиц.
город
Порядок следования
1
2
3
4
A
0
1
0
0
B
0
0
0
1
C
1
0
0
0
D
0
0
1
0
Рис. 6.6. Маршрут коммивояжера
Второе требование – предпочтение коротким маршрутам – удовлетворяется с помощью добавления следующего члена к функции энергии:
, (6.10)
Заметим, что этот член представляет собой длину любого допустимого маршрута. Для удобства индексы определяются по модулю n, т. е. OUTn+j = OUTj, a D – некоторая константа.
При достаточно больших значениях A, B и C низкоэнергетические состояния будут представлять допустимые маршруты, а большие значения D гарантируют, что будет найден короткий маршрут.
Теперь зададим значения весов, т. е. установим соответствие между членами в функции энергии и членами общей формы (см. уравнение 6.2)).
Получаем
wxi,yi = –Aδxy(1 – δij) (не допускает более одной единицы в строке)
–Bδij(1 – δxy) (не допускает более одной единицы в столбце)
–С (глобальное ограничение)
–Ddxy(δj,i+1 + δj,i-1) (член, отвечающий за длину цикла),
где δij = 1, если i = j, в противном случае δij = 0. Кроме того, каждый нейрон имеет смещающий вес хi, соединенный с +1 и равный Сп.
