On considère le début d'un arbre de recherche construit par l'algorithme de Little.

La racine a été évaluée à 1000. On choisit de séparer le problème sur le trajet AB, de regret 100.

Quelle est la valeur du nœud ?

Entrez un nombre.

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

Nous avons exécuté l'algorithme de Little jusqu'à obtenir l'arbre de recherche suivant :

Quelles branches peut-on couper à ce stade ?

Nous sommes au cours de l'exécution de l'algorithme de Little.

Un noeud vient d'être évalué, et nous avons identifié le projet trajet qui fera l'objet de la prochaine séparation : AB.

Nous allons évaluer le noeud de type "Trajet AB exclu". Pour cela, nous devons modifier la matrice de coûts.

Quelle opération doit-on réaliser sur cette matrice ?

Cocher toutes les réponses possibles. Attention : les mauvaises réponses donnent lieu à un malus.

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

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

Écrire un nombre entier.

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

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

Écrire un nombre entier.

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

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

Écrire un nombre entier.

L'algorithme de Little est un algorithme de Branch & Bound.

Dans l'étape "Bound", qu'évalue-t-on ?

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

Nous avons exécuté l'algorithme de Little jusqu'à obtenir l'arbre de recherche suivant :

Quelles branches peut-on couper à ce stade ?

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

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

Écrire un nombre entier.

Quels type de trajets sont explorés de manière prioritaire par l'algorithme de Little ?