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


Первая тройная сумма равна нулю в том и только в том случае, если каждая строка (город) содержит не более одной единицы. Вторая тройная сумма равна нулю в том и только в том случае, если каждый столбец (порядковый номер посещения) содержит не более одной единицы. Третья сумма равна нулю в том и только в том случае, если матрица содержит ровно п единиц. город Порядок следования 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, т. е. 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 и равный Сп. Содержание Назад Вперед




Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий