ВУЗ:
Составители:
122
при n=60 число возможных маршрутов становится равным 6934155·10
78
(для
сравнения в нашей галактике «лишь» 10
11
звезд). Время решения такой задачи
простым перебором даже на самом быстром компьютере будет соразмерно с
геологическими эпохами.
Таблица 11.1
Задание порядка посещения городов
Порядок следования
Город
1 2 3 4
A
0 1 0 0
B
0 0 0 1
C
1 0 0 0
D
0 0 1 0
Построим сеть для решения ЗК. Снабдим каждый нейрон сети двумя
индексами: первый соответствует городу; второй – порядковому номеру его
посещения в маршруте. Энергетическая функция должна удовлетворять двум
требованиям:
− должна быть малой только для тех решений, которые имеют по одной
единице в каждой строке и в каждом столбце;
− должна оказывать
предпочтение решениям с более короткой длиной
маршрута.
Первое требование удовлетворяется, если энергетическая функция будет
иметь вид:
∑∑∑ ∑∑∑ ∑∑
≠≠
−++=
xi ijixxy
xiyixixjxi
nz
K
zz
K
zz
K
E
xi
2
321
,
222
])[( (11.9)
где
K
1
, K
2
, K
3
– некоторые константы.
В выражении (11.9):
– первый член равен нулю только в том случае, если каждая строка (город)
содержит не более одной единицы.
– второй член равен нулю только в том случае, если каждый столбец
(порядковый номер посещения) содержит не более одной единицы.
– третий член равен нулю только в том случае,
если матрица содержит
ровно
n единиц.
Второе требование – предпочтение коротким маршрутам –
удовлетворяется добавлением в энергетическую функцию (11.9) четвертого
члена:
Страницы
- « первая
- ‹ предыдущая
- …
- 120
- 121
- 122
- 123
- 124
- …
- следующая ›
- последняя »
