Grafos e RedesAnts

O problema do Vendedor ambulante é NP-difícil, o que significa que é muito difícil ser resolvido por computadores (pelo menos para um grande número de cidades).

Encontrar um algoritmo rápido e exato teria implicações sérias no campo da ciência da computação: significaria que existem algoritmos rápidos para todos os problemas difíceis de NP. Isso também tornaria inútil a maior parte da segurança da Internet, que se baseia no fato de que certos problemas são considerados muito difíceis para os computadores.

Encontrar um algoritmo rápido para resolver o problema do vendedor ambulante também resolveria um dos problemas abertos mais famosos da matemática e da ciência da computação, o problema de P vs NP. É um dos sete Problemas do Prêmio Millennium, cada um com um prêmio de US $ 1 milhão.