ВУЗ:
Составители:
121
городов, начиная от некоторого исходного города, посещая каждый город один
раз и возвращаясь в исходный город. Задача коммивояжера (ЗК) относится к
классу задач, называемых математиками
NP-полными (недетерминистки
полиномиальные)
. Трудность решения таких задач состоит в высокой степени
возрастания числа комбинаций при увеличении параметра, характеризующего
объем задачи. Степень возрастания комбинаций в
NP-полных задачах растет
экспоненциально с увеличением объема задачи. Попытки прямого решения
таких задач методом простого перебора комбинаций вскоре порождает
комбинаторный взрыв, который быстро исчерпывает возможности обычных
компьютеров. В ЗК параметром, задающим объем задачи, является число
городов. При большом числе городов простой перебор из-за колоссальных
временных затрат становится просто невозможным, и решение обычно сводится
к поиску приемлемых, хотя и неоптимальных, эвристических решений. Решение
ЗК на сети Хопфилда также относится к эвристическим
и потому является
квазиоптимальным. Вместе с тем, решение получается так быстро, что метод
оказывается весьма привлекательным.
Пусть схема городов выглядит так, как показано на рис. 11.5 [16].
Рис. 11.5. Схема городов в задаче коммивояжера
Решением является упорядоченное множество из
n городов (на схеме n=4).
В сети будем использовать нейроны с большой крутизной выходной
характеристики, близкой к пороговой. Каждый город представлен строкой из
n
нейронов. Выход только одного нейрона в строке равен 1 (остальные равны 0).
Позиция единицы в строке показывает порядковый номер, в котором город
посещается при обходе. В нашем примере для
n=4 городов потребуется n
2
нейронов, т.е. 16. Порядок посещения городов может быть, например, таким,
как показан в табл. (11.1), т.е:
C, A, D, B. Длина такого маршрута L = d
ca
+ d
ad
+
d
db
+ d
bc
.
ЗК с
n городами соответствует n! различных маршрутов. Для нашего
простого примера число возможных маршрутов равно 24. Для большего числа
городов рост числа возможных маршрутов несет взрывной характер. Например,
В
d
ab
d
bd
d
bc
d
ac
d
cd
d
ad
С
D
А
Страницы
- « первая
- ‹ предыдущая
- …
- 119
- 120
- 121
- 122
- 123
- …
- следующая ›
- последняя »
