Мы представляем самоорганизующуюся "нейронную" сеть для решения задачи коммивояжера. Она частично основана на сети Кохонена. Наш подход отличается от прежних работ в этом направлении тем, что не используются кольцевые структуры с фиксированным количеством элементов. Вместо этого, небольшая начальная структура постепенно распространяется и увеличивается. Это позволяет заменить начальный шаг поиска, который, обычно, требует времени O(n), локальной процедурой, которая требует время O(1). Так как полное количество шагов поиска, которые нужно выполнить, оценивается величиной O(n), то время, затрачиваемое нашей моделью, линейно зависит от размерности задачи. Это лучше, чем любой другой известный нейронный или конвенциональный алгоритм. Длина пути найденного решения, обычно, менее чем на девять процентов длиннее, чем оптимальное решение, известное для такой задачи из литературы.

Оригинал статьи: FLEXMAP - A Neural Network For The Traveling Salesman Problem (как PDF)