Conclusion

Ainsi, puisque TSP peut se réduire dans HC qui est NP et comme tout problème NP peut se réduire dans TSP alors TSP est NP-Complet

Nous avons donc vu qu'un problème qui est en apparence simple est en fait un qui demande des temps de calculs très long dès que le nombre de ville est assez élevé. Heureusement, des algorithmes utilisant des méta heuristiques peuvent arriver a résoudre ce genre de problème (même si l'on pas pas la certitude que la solution trouvée est la meilleure) dans des temps acceptable par rapport aux algorithmes deterministes