Soit n le nombre de villes dans le problème du voyageur de commerce.

Il n'existe pas d'algorithme capable de résoudre ce problème en temps polynomial par rapport à n.

Soit un problème de voyageur de commerce avec 4 villes : A, B, C, D.

Au cours de l'exécution de l'algorithme de Little, on a déjà inclus les trajets AB et BC.

Quel trajet parasite faut-il éliminer à ce stade ?

Écrivez simplement 2 lettres, sans aucun autre caractère.

Quel algorithme avez-vous implémenté pour résoudre le problème du voyageur de commerce ?

Qu'est-ce que le regret associé à un trajet ?

Soit la matrice de coûts réduite suivante : 

Quelle est la valeur du regret maximal (pas sa position) ? 

Écrire un nombre entier.

L'arbre de recherche de l'algorithme de Little est un arbre binaire.

Reliez chaque étape du branch & bound à leur définition

La matrice d'adjacence d'un graphe non-orienté est symétrique