FM! - Wonderful минус

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


Первая тройная сумма равна нулю в том и только в том случае, если каждая строка (город) содержит не более одной единицы.

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

Третья сумма равна нулю в том и только в том случае, если матрица содержит ровно п единиц.

город

Порядок следования

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) (не допускает более одной единицы в столбце)

–С (глобальное ограничение)

–Ddxyj,i+1 + δj,i-1) (член, отвечающий за длину цикла),

где δij = 1, если i = j, в противном случае δij = 0. Кроме того, каждый нейрон имеет смещающий вес хi, соединенный с +1 и равный Сп.

- Начало - - Назад - - Вперед -