Первая тройная сумма равна нулю

Первая тройная сумма равна нулю в том и только в том случае, если каждая строка (город) содержит не более одной единицы. Вторая тройная сумма равна нулю в том и только в том случае, если каждый столбец (порядковый номер посещения) содержит не более одной единицы. Третья сумма равна нулю в том и только в том случае, если матрица содержит ровно п единиц. город Порядок следования 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. Маршрут коммивояжера Второе требование – предпочтение коротким маршрутам – удовлетворяется с помощью добавления следующего члена к функции энергии: Заметим, что этот член представляет собой длину любого допустимого маршрута. Для удобства индексы определяются по модулю n, т. е. OUT_n+j = OUT_j, a D – некоторая константа. При достаточно больших значениях A, B и C низкоэнергетические состояния будут представлять допустимые маршруты, а большие значения D гарантируют, что будет найден короткий маршрут. Теперь зададим значения весов, т. е. установим соответствие между членами в функции энергии и членами общей формы (см. уравнение 6.2)). Получаем w_xi,yi = –Aδ_xy(1 – δ_ij) (не допускает более одной единицы в строке) –Bδ_ij(1 – δ_xy) (не допускает более одной единицы в столбце) –С (глобальное ограничение) –Dd_xy(δ_j,i+1 + δ_j,i-1) (член, отвечающий за длину цикла), где δ_ij = 1, если i = j, в противном случае δij = 0. Кроме того, каждый нейрон имеет смещающий вес х_i, соединенный с +1 и равный Сп. Содержание раздела

---