Графики и СетиAnts

Задача коммивояжера является NP-трудной , что означает, что ее очень трудно решить с помощью компьютеров (по крайней мере, для большого числа городов).

Поиск быстрого и точного алгоритма имел бы серьезные последствия в области компьютерных наук: это означало бы, что существуют быстрые алгоритмы для всех NP-сложных задач. Это также сделает большую часть безопасности в Интернете бесполезной, поскольку полагается, что определенные проблемы считаются очень сложными для компьютеров.

Поиск быстрого алгоритма для решения проблемы коммивояжера также решил бы одну из самых известных открытых задач в математике и информатике, проблему P vs NP . Это одна из семи проблем , связанных с премией тысячелетия , каждая из которых имеет приз в 1 миллион долларов.