Pour modéliser ce problème nous utilisons les entiers non signés usize pour représenter les noeuds. Les coûts sont représentés par
une valeur signées sur 32 bits (i32).
Loading content...
Pour modéliser notre chemin, nous utilisons deux listes, la liste des noeuds vus (appartenant au chemin parcouru) et la liste des noeuds non vus.
Loading content...
La première partie du TP consiste à générer l’ensemble des permutations possible pour $n$ sommets. Pour ce faire, nous utilisons une fonction récursive qui travaille en deux étapes. Lors de la première étape nous ajoutons un des sommets de l’ensemble $non\_vus$ à l’ensemble des sommets $vus$, nous effectuons ensuite l’appel recursif. Au retour de cet appel, nous enlevons le dernier sommet de l’ensemble $vus$ pour le remettre dans l’ensemble $non\_vus$ puis nous passons au noeud suivant. La condition d’arrêt est que l’ensemble des $non\_vus$ est vide.
Loading content...
Une fois la génération des chemins effectuée, il suffit de calculer la longueur du chemin en ajoutant le cout de l’arc partant du dernier sommet non vus (avant l’ajout du nouveau noeud) vers le dernier sommet non vus (après l’ajout du nouveau noeud). On veillera également à ne pas oublier d’ajouter le cout de l’arc partant du dernier des sommets vus vers le noeud $0$ lors d’une récursion terminale.
Loading content...
Le calcul du coût minimal se fait simplement en mémorisant le cout minimal, i.e. à chaque appel terminal, on vérifie si le coût du chemin est meilleur que le meilleur coût déjà trouvé.
Loading content...
BoundMaintenant que nous avons une solution au problème, nous pouvons réfléchir à comment améliorer les performances. La valeur $pcc$ enregistre à tout moment une borne maximale de la solution au problème. Or il se peut qu’au cours de la recherche la longueur de certains chemins dépassent cette valeur. Nous pouvons alors arrêter les appels récursifs pour ces chemins puisqu’ils ne pourront pas améliorer la solution.
Nous pouvons ajouter une condition avant l’appel récursif :
let new_path_len = path_len + cost[seen[seen.len() - 2]][seen[seen.len() - 1]];
if new_path_len < *pcc {
permute_len_pcc(seen, unseen, new_path_len, cost, pcc);
}
Cette amélioration permet de couper une partie des solutions mais est assez limitée. En effet, nous prenons en compte la taille du chemin parcouru, mais pas la taille du chemin à parcourir ($non\_vus$). Sachant que déterminer le coût du chemin optimal pour les sommets $non\_vus$ est combinatoire, nous utilisons des heuristiques pour l’approximer.
Nous définissons un Trait permettant de calculer la borne :
Loading content...
La fonction principale pourra alors utiliser les informations de la fonction de bornage comme ceci :
Loading content...
Une première approximation très simple est de considérer que le coût de chemin restant à parcourir est $(\mid non\_vus \mid + 1) \times d\_min$ où $d\_min$ est le coût minimal des arcs du graphe.
La fonction bound est définie alors par :
Loading content...
La première heuristique est très simple mais n’est pas trés efficace. Afin d’améliorer les performances nous choisissons une autre heuristique. Cette heuristique calcule, pour chaque sommet non vus, le coût de l’arc minimal permettant de relier le noeud au circuit.
Loading content...
Jusqu’à maitenant, nous énumérons les différentes permutations dans un ordre quelconque. Afin d’essayer de trouver rapidement une borne proche de l’optimale nous souhaitons changer l’ordre dans lequel sont effectuer les permutations à l’aide d’une solution gloutonne. Pour se faire, à chaque appel récursif nous trions les noeuds dans l’odre de distance au dernier point vus.
Loading content...
La recherche avec ordonnancement devient alors :
Loading content...
Un point important est de copier le tableau dans une nouvelle structure à chaque appel récursif afin de ne pas modifier l’ordre des variables sur lequel
permute fonction.
Le voyageur de commerce étant un problème $\mathcal{NP}-complet$ il n’est pas possible de calculer la solution optimale dans une temps correct pour certaines instances. Une solution consiste à limiter le facteur de branchement à l’aide d’une variable comptant le nombre branchement effectué.
Loading content...