Twin C# de App-13-TSP-Metaheuristics (Python : brute force, plus-proche-voisin, 2-opt, recuit simulé, GA, ACO, OR-Tools). Suite du marathon .NET ⇄ Python (#4956), volet Search / Applications / Hybrid. BCL .NET seule, 0 NuGet, from-scratch (Prong B #3801).
Objectifs d’apprentissage
Modéliser le Traveling Salesman Problem (TSP) : villes, coordonnées, matrice de distances, longueur d’une tournée.
Distinguer méthode exacte (force brute, factorielle — réservée aux petites instances) et heuristiques.
Implémenter from-scratch les trois piliers de la résolution approchée du TSP :
construction (plus proche voisin — glouton),
recherche locale (2-opt — inversion de segments),
métaheuristique (recuit simulé sur l’espace des permutations).
Comparer empiriquement qualité vs temps sur des instances Euclidiennes.
Complémentarité (#3801 Prong B)
Twin
Outil
Valeur
Python
OR-Tools routing + numpy + matplotlib
solveur industriel (routing), visualisation
Twins C# Hybrid existants (App-9b, App-10b)
GeneticSharp (librairie .NET)
algorithme génétique clé en main
Ce twin (.NET BCL seule)
from-scratch (2-opt, recuit simulé sur permutations)
comprendre les heuristiques canoniques du TSP
★ Le twin Python appelle OR-Tools ; les autres twins C# appellent GeneticSharp. Ce twin déroule les heuristiques à la main (2-opt = inversion de segment, recuit simulé = move 2-opt + critère de Metropolis) — la mécanique que les librairies cachent.
Hommage — Stearns et l’analyse de pire cas des heuristiques du voyageur de commerce
Avant de fonder la théorie de la complexité, Richard E. Stearns (1936–2026, prix Turing 1993) a produit la première analyse systématique de pire cas des heuristiques du TSP, motivée par des problèmes industriels de General Electric — notamment le perçage de tôles (séquence de perçages = tournée minimale). Poser la question « quelle garantie de pire cas cette heuristique donne-t-elle ? » — au lieu de mesurer seulement sa performance moyenne sur une instance — est exactement le geste fondateur que ce notebook exerce en comparant nearest-neighbor, 2-opt et le Guided Local Search d’OR-Tools : à qualité d’instance égale, ce qui distingue une heuristique d’une recette, c’est sa garantie démontrable.
Hommage complet (hiérarchie de Hartmanis–Stearns, série Complexity/) : issue #15949 ; autres résonances — paradoxe d’Arrow 1959, jeux répétés à information incomplète, automates LL(k).
Le TSP : étant donné N villes et les distances entre elles, trouver la tournée fermée la plus courte passant par chaque ville exactement une fois. NP-dur. On travaille en Euclidien : les villes sont des points du plan, la distance est la distance Euclidienne.
using System;using System.Collections.Generic;using System.Globalization;using System.Linq;staticstringFI(double x,string fmt ="F2")=> x.ToString(fmt, CultureInfo.InvariantCulture);staticstringFI(long x)=> x.ToString("N0", CultureInfo.InvariantCulture);staticvoidShow(string s)=>display(s);// Instance du TSP : N villes, coordonnées Euclidiennes, matrice des distances précalculée.publicclass TSPInstance {publicint N;publicdouble[] X;publicdouble[] Y;publicdouble[][] D;// matrice NxN des distances EuclidiennespublicTSPInstance(double[] xs,double[] ys){ N = xs.Length; X = xs; Y = ys; D =newdouble[N][];for(int i =0; i < N; i++){ D[i]=newdouble[N];for(int j =0; j < N; j++){double dx = X[i]- X[j], dy = Y[i]- Y[j]; D[i][j]= Math.Sqrt(dx*dx + dy*dy);}}}// longueur d'une tournée fermée : somme des arêtes consécutives + retour au départpublicdoubleTourLength(int[] tour){double s =0;for(int k =0; k < N; k++) s += D[tour[k]][tour[(k+1)% N]];return s;}}// instance reproductible : N villes dans [0,100)^2 via RNG seededstatic TSPInstance RandomInstance(int n,int seed){var rnd =newRandom(seed);var xs =newdouble[n];var ys =newdouble[n];for(int i =0; i < n; i++){ xs[i]= rnd.NextDouble()*100; ys[i]= rnd.NextDouble()*100;}returnnewTSPInstance(xs, ys);}// affiche une tournée en abrégéstaticstringTourStr(int[] tour)=>"["+string.Join(",", tour.Take(Math.Min(tour.Length,12)))+(tour.Length>12?",...]":"]");var small =RandomInstance(6,42);Show("Instance Euclidienne : "+ small.N+" villes. Matrice 6x6 (extrait) :");var m =" ";for(int j =0; j < small.N; j++) m += j.ToString().PadLeft(6);Show(m);for(int i =0; i < small.N; i++)Show(i.ToString().PadLeft(4)+" "+string.Join("", Enumerable.Range(0, small.N).Select(j => small.D[i][j].ToString("F2", CultureInfo.InvariantCulture).PadLeft(6))));var t =newint[]{0,1,2,3,4,5};Show("Tournée [0,1,2,3,4,5] longueur = "+FI(small.TourLength(t)));
The below script needs to be able to find the current output cell; this is an easy method to get it.
La force brute énumère toutes les \((N-1)!\) tournées (en fixant la ville de départ à 0 pour casser la symétrie cyclique). Garantit l’optimum global mais devient inutilisable au-delà de ~10 villes. Sert de référence pour mesurer la qualité des heuristiques.
// force brute : énumère toutes les permutations des villes 1..N-1 (ville 0 fixée), garde la meilleurestatic(int[] tour,double len,long tried)BruteForce(TSPInstance tsp){int n = tsp.N;var rest = Enumerable.Range(1, n -1).ToArray();int[] bestTour =null;double bestLen =double.MaxValue;long tried =0;voidPermute(int k){if(k == rest.Length){var tour =newint[n]; tour[0]=0;for(int i =0; i < rest.Length; i++) tour[i+1]= rest[i]; tried++;double len = tsp.TourLength(tour);if(len < bestLen){ bestLen = len; bestTour =(int[])tour.Clone();}return;}for(int i = k; i < rest.Length; i++){(rest[k], rest[i])=(rest[i], rest[k]);Permute(k +1);(rest[k], rest[i])=(rest[i], rest[k]);}}Permute(0);return(bestTour, bestLen, tried);}var inst8 =RandomInstance(8,7);var sw = System.Diagnostics.Stopwatch.StartNew();var(bt, bl, tried)=BruteForce(inst8);sw.Stop();Show("Force brute N=8 : optimum = "+FI(bl)+" en "+FI(sw.Elapsed.TotalMilliseconds,"F1")+" ms ("+FI(tried)+" = 7! permutations testees).");Show("Tournée optimale : "+TourStr(bt));Show("Croissance : (N-1)! -> N=10 = 362880, N=12 = 4e7, N=15 = 8.7e10 (inatteignable).");
Force brute N=8 : optimum = 293.19 en 1.0 ms (5,040 = 7! permutations testees).
3. Heuristique de construction : plus proche voisin
Glouton : on part de la ville 0, et à chaque étape on va à la ville non visitée la plus proche. Rapide (\(O(N^2)\)) mais myope — construit des tournées typiquement 20-30% au-dessus de l’optimum.
// plus proche voisin : greedy, O(N^2)static(int[] tour,double len)NearestNeighbor(TSPInstance tsp){int n = tsp.N;var visited =newbool[n];var tour =newint[n]; tour[0]=0; visited[0]=true;for(int k =1; k < n; k++){int prev = tour[k-1];int best =-1;double bestD =double.MaxValue;for(int j =0; j < n; j++){if(!visited[j]&& tsp.D[prev][j]< bestD){ bestD = tsp.D[prev][j]; best = j;}} tour[k]= best; visited[best]=true;}return(tour, tsp.TourLength(tour));}var(nnTour, nnLen)=NearestNeighbor(inst8);Show("Plus proche voisin N=8 : longueur = "+FI(nnLen)+" (vs optimum "+FI(bl)+", gap = "+FI(100*(nnLen-bl)/bl,"F1")+"%).");Show("Tournée NN : "+TourStr(nnTour));
Plus proche voisin N=8 : longueur = 344.77 (vs optimum 293.19, gap = 17.6%).
Tournée NN : [0,5,2,3,4,7,1,6]
4. Recherche locale : 2-opt
Le 2-opt est la recherche locale canonique du TSP. Principe : tant qu’il existe deux arêtes de la tournée qui se croisent (ou sont sous-optimales), on inverse le segment entre elles. Une inversion de segment supprime deux arêtes \((a,b)\) et \((c,d)\) et les remplace par \((a,c)\) et \((b,d)\). On itère jusqu’à un optimum local (plus aucune inversion n’améliore).
C’est l’opération de base que tous les solveurs TSP utilisent en post-optimisation.
// 2-opt : répète les inversions de segments améliorantes jusqu'à optimum localstatic(int[] tour,double len,int improvements)TwoOpt(TSPInstance tsp,int[] initTour){int n = tsp.N;var tour =(int[])initTour.Clone();int improvements =0;bool improved =true;while(improved){ improved =false;for(int i =1; i < n -1; i++){for(int j = i +1; j < n; j++){int a = tour[i-1], b = tour[i], c = tour[j], d =(j+1< n)? tour[j+1]: tour[0];double before = tsp.D[a][b]+ tsp.D[c][d];double after = tsp.D[a][c]+ tsp.D[b][d];if(after +1e-12< before){ Array.Reverse(tour, i, j - i +1); improvements++; improved =true;}}}}return(tour, tsp.TourLength(tour), improvements);}// 2-opt sur la tournée du plus proche voisinvar(opt2Tour, opt2Len, opt2Imp)=TwoOpt(inst8, nnTour);Show("2-opt (depuis NN) N=8 : longueur = "+FI(opt2Len)+" ("+ opt2Imp +" inversions). Gap vs optimum = "+FI(100*(opt2Len-bl)/bl,"F2")+"%.");Show("2-opt rapproche fortement de l'optimum en O(N^2) par passage.");
2-opt (depuis NN) N=8 : longueur = 293.19 (4 inversions). Gap vs optimum = 0.00%.
2-opt rapproche fortement de l'optimum en O(N^2) par passage.
5. Métaheuristique : recuit simulé sur permutations
Le recuit simulé (Simulated Annealing) échappe aux optima locaux du 2-opt en acceptant parfois des mouvements dégradants avec probabilité \(\exp(-\Delta/T)\), où \(T\) décroît géométriquement. Sur le TSP, le mouvement proposé est une inversion 2-opt aléatoire. À haute température, exploration ; à basse température, exploitation → convergence vers un (très bon) optimum.
Le schéma de refroidissement décide tout. Une décroissance trop rapide (\(\alpha = 0.9995\)) fige le recuit dans un optimum local avant qu’il n’ait exploré — il sous-performe alors le 2-opt déterministe sur les grandes instances. Un refroidissement lent (\(\alpha = 0.99995\), \(T_0 \propto N\)) lui laisse le temps d’échapper aux optima locaux : c’est le paramétrage mesuré et retenu au benchmark ci-dessous (3 seeds, résultat moyen).
// recuit simulé sur permutations : move = inversion 2-opt aléatoire, acceptation de Metropolisstatic(int[] tour,double len,int accepted)SimulatedAnnealing(TSPInstance tsp,int[] initTour,double T0,double alpha,int iters,int seed){int n = tsp.N;var tour =(int[])initTour.Clone();var rnd =newRandom(seed);double curLen = tsp.TourLength(tour);int accepted =0;int[] best =(int[])tour.Clone();double bestLen = curLen;double T = T0;for(int it =0; it < iters; it++){int i =1+ rnd.Next(n -1);int j =1+ rnd.Next(n -1);if(i == j)continue;if(i > j)(i, j)=(j, i);int a = tour[i-1], b = tour[i], c = tour[j], d =(j+1< n)? tour[j+1]: tour[0];double delta =(tsp.D[a][c]+ tsp.D[b][d])-(tsp.D[a][b]+ tsp.D[c][d]);if(delta <=0|| rnd.NextDouble()< Math.Exp(-delta / T)){ Array.Reverse(tour, i, j - i +1); curLen += delta; accepted++;if(curLen < bestLen){ bestLen = curLen; best =(int[])tour.Clone();}} T *= alpha;}return(best, bestLen, accepted);}var(saTour, saLen, saAcc)=SimulatedAnnealing(inst8, nnTour, T0:50.0, alpha:0.9995, iters:20000, seed:1);Show("Recuit simulé N=8 (depuis NN, 20000 iters) : longueur = "+FI(saLen)+" ("+ saAcc +" moves acceptes). Gap vs optimum = "+FI(100*(saLen-bl)/bl,"F2")+"%.");
Recuit simulé N=8 (depuis NN, 20000 iters) : longueur = 293.19 (2056 moves acceptes). Gap vs optimum = -0.00%.
6. ★ Benchmark comparatif
On compare les quatre approches sur des instances de taille croissante. La force brute donne l’optimum exact pour N≤10 ; au-delà, elle est infaisable (\((N-1)!\) permutations).
Lecture discriminante : pour N≤10, le 2-opt trouve déjà l’optimum exact — l’instance est trop petite pour le distinguer de SA. Pour N≥30 en revanche, le 2-opt reste bloqué sur un optimum local, et le recuit simulé (bien refroidi, moyenné sur 3 seeds) l’améliore de ~1-4% (colonne SA vs 2-opt) : c’est précisément la valeur ajoutée de la métaheuristique, qui échappe là où la recherche locale s’arrête. Le plus-proche-voisin sert de baseline sous-optimale (~16-22% au-dessus).
C’est l’enseignement central : exact ↔︎ approché bascule dès que l’espace explose, et local-search ↔︎ métaheuristique bascule dès que le paysage présente des optima locaux — le même mouvement qu’on observe pour les autres problèmes combinatoires.
// Benchmark comparatif (4 approches) sur instances de taille croissante.// SA : refroidissement lent (alpha=0.99995, T0=n*5) + 3 seeds -> mesure reproductible.// (alpha=0.9995 trop rapide : SA converge prematurement et sous-performe 2-opt a grande echelle.)int[] seedsSA ={1,7,42};Show(" N | brut(opt) | NN | 2-opt | SA (3 seeds: mean) | gap NN | gap 2opt | gap SA | SA vs 2-opt");Show(newstring('-',102));foreach(var n innew[]{6,8,10,30,60,100}){var inst =RandomInstance(n,7);var(nnT, nnL)=NearestNeighbor(inst);var(o2T, o2L, o2I)=TwoOpt(inst, nnT);double saSum =0;foreach(var sd in seedsSA){var(saT, saL, saA)=SimulatedAnnealing(inst, nnT, T0: Math.Max(50.0, n*5.0), alpha:0.99995, iters: Math.Min(300000, n*3000), seed: sd); saSum += saL;}double saMean = saSum / seedsSA.Length;string brutCell, saVs2;double opt;if(n <=10){var(bT, bL, bTr)=BruteForce(inst); opt = bL; brutCell =FI(bL);}else{ opt =-1; brutCell ="(N/A)";} saVs2 =FI(100*(o2L - saMean)/o2L,"F1")+"%";string gapNNs = opt >0?(FI(100*(nnL-opt)/opt,"F1")+"%"):"(n/a)";string gap2s = opt >0?(FI(100*(o2L-opt)/opt,"F1")+"%"):"(n/a)";string gapSAs = opt >0?(FI(100*(saMean-opt)/opt,"F1")+"%"):"(n/a)";Show(n.ToString().PadLeft(5)+" | "+ brutCell.PadLeft(11)+" | "+FI(nnL).PadLeft(11)+" | "+FI(o2L).PadLeft(11)+" | "+(FI(saMean)+" (3 seeds)").PadLeft(19)+" | "+ gapNNs.PadLeft(8)+" | "+ gap2s.PadLeft(9)+" | "+ gapSAs.PadLeft(8)+" | "+ saVs2.PadLeft(11));}Show("Interpretation : NN est rapide mais sous-optimal (gap ~16-22%). Pour N<=10, 2-opt et SA");Show("atteignent l'optimum exact (gap 0.0% - instance trop petite pour discriminer). Pour N>=30,");Show("2-opt reste bloque sur un optimum local ; SA (refroidissement lent, 3 seeds) l'ameliore de ~1-4%");Show("(colonne 'SA vs 2-opt' > 0) : c'est la valeur ajoutee de la metaheuristique. Au-dela de N=10,");Show("la force brute est infaisable (OR-Tools dans le twin Python donne la reference industrielle).");
N | brut(opt) | NN | 2-opt | SA (3 seeds: mean) | gap NN | gap 2opt | gap SA | SA vs 2-opt
Interpretation : NN est rapide mais sous-optimal (gap ~16-22%). Pour N<=10, 2-opt et SA
atteignent l'optimum exact (gap 0.0% - instance trop petite pour discriminer). Pour N>=30,
2-opt reste bloque sur un optimum local ; SA (refroidissement lent, 3 seeds) l'ameliore de ~1-4%
(colonne 'SA vs 2-opt' > 0) : c'est la valeur ajoutee de la metaheuristique. Au-dela de N=10,
la force brute est infaisable (OR-Tools dans le twin Python donne la reference industrielle).
Synthèse
Approche
Type
Complexité
Qualité
Quand l’utiliser
Force brute
exacte
\(O((N-1)!)\)
optimum global
N ≤ 10 (référence)
Plus proche voisin
construction gloutonne
\(O(N^2)\)
16-22% au-dessus
initialisation rapide
2-opt
recherche locale
\(O(N^2)\)/passage
optimum local (bloqué)
post-optimisation systématique
Recuit simulé
métaheuristique
\(O(I \cdot N)\)/itération
échappe au 2-opt (+1-4% sur N≥30, refroidissement lent)
instances moyen/grandes
Leçon : le TSP illustre deux basculements. (1) Exact ↔︎ approché — la force brute garantit l’optimum mais explose ; les heuristiques s’en approchent à coût polynomial. (2) Recherche locale ↔︎ métaheuristique — sur les petites instances (N≤10), le 2-opt trouve déjà l’optimum et SA n’ajoute rien ; sur les moyennes/grandes (N≥30), le 2-opt se fige dans un optimum local et le recuit simulé l’améliore de ~1-4%, pourvu que son refroidissement soit assez lent. Les solveurs industriels (OR-Tools, twin Python) combinent ces idées à l’échelle.
Le twin Python App-13-TSP-Metaheuristics.ipynb appelle le moteur industriel OR-Tools (ortools.constraint_solver.routing, RoutingModel) comme référence là où la force brute devient infaisable (N>10). La Tranche 1 from-scratch ci-dessus (force brute, plus proche voisin, 2-opt, recuit simulé) est préservée intacte : on lui confronte maintenant le même moteur de production que le jumeau Python — Google.OrTools 9.11 (Perron & Furney ; solveur de routage avec recherche locale guidée GLS).
Honnêteté cruciale : le solveur de routage est une métaheuristique (recherche locale guidée), PAS un solveur exact — il ne délivre aucun certificat d’optimalité, contrairement à CP-SAT. C’est un paradigme différent : là où CP-SAT (App-5, App-11) prouve l’optimum via SAT + Lazy Clause Generation, le routing solver explore l’espace des tournées avec des opérateurs de recherche locale. Sa valeur est la qualité industrielle sur grandes instances, pas la garantie.
#r "nuget: Google.OrTools, 9.11.4210"using Google.OrTools.ConstraintSolver;using System.Diagnostics;// SolveRouting : miroir C# de ortools_tsp (Python pywrapcp.RoutingModel).// RoutingModel = metaheuristique (recherche locale guidee GLS), PAS solveur exact.(int[] tour,double cost,double ms)SolveRouting(TSPInstance tsp,int timeLimitS =2){var manager =newRoutingIndexManager(tsp.N,1,0);var routing =newRoutingModel(manager);longtransitCallback(long fromIdx,long toIdx){int f = manager.IndexToNode(fromIdx), too = manager.IndexToNode(toIdx);return(long)(tsp.D[f][too]*1000);// scale floats -> long (miroir Python *1000)}int transitIdx = routing.RegisterTransitCallback(transitCallback); routing.SetArcCostEvaluatorOfAllVehicles(transitIdx);var sp = operations_research_constraint_solver.DefaultRoutingSearchParameters(); sp.FirstSolutionStrategy= FirstSolutionStrategy.Types.Value.PathCheapestArc; sp.LocalSearchMetaheuristic= LocalSearchMetaheuristic.Types.Value.GuidedLocalSearch; sp.TimeLimit=new Google.Protobuf.WellKnownTypes.Duration{ Seconds =(long)timeLimitS };var sw = Stopwatch.StartNew();var sol = routing.SolveWithParameters(sp); sw.Stop();if(sol !=null){var tour =new List<int>();long idx = routing.Start(0);while(!routing.IsEnd(idx)){ tour.Add(manager.IndexToNode(idx)); idx = sol.Value(routing.NextVar(idx));}var arr = tour.ToArray();return(arr, tsp.TourLength(arr), sw.Elapsed.TotalMilliseconds);}return(null,-1, sw.Elapsed.TotalMilliseconds);}Show("--- Tranche 2 : OR-Tools routing solver (Google.OrTools 9.11) ---");Show("Miroir C# de ortools_tsp (twin Python). RoutingModel = metaheuristique GLS,");Show("PAS solveur exact : aucune garantie d'optimalite (contrairement a CP-SAT).");Show("");Show("Parite (routing vs force brute, small N) :");Show(" N | brut(opt) | routing | parite | routing ms");foreach(var n innew[]{6,8,10}){var inst =RandomInstance(n,7);var(bT, bL, bTr)=BruteForce(inst);var(rT, rC, rMs)=SolveRouting(inst,1);bool ok = Math.Abs(rC - bL)<0.5;Show(n.ToString().PadLeft(4)+" | "+FI(bL).PadLeft(12)+" | "+FI(rC).PadLeft(11)+" | "+(ok ?"OK":"DIFF").PadLeft(6)+" | "+FI(rMs,"F0"));}Show("");Show("Prong-B : reference industrielle (force brute infaisable pour N>10) :");Show(" N | NN | 2-opt | SA (mean) | routing | routing vs SA");foreach(var n innew[]{30,60,100}){var inst =RandomInstance(n,7);var(nnT, nnL)=NearestNeighbor(inst);var(o2T, o2L, o2I)=TwoOpt(inst, nnT);double saSum =0;foreach(var sd innew[]{1,7,42}){var(saT, saL, saA)=SimulatedAnnealing(inst, nnT, T0: Math.Max(50.0, n*5.0), alpha:0.99995, iters: Math.Min(300000, n*3000), seed: sd); saSum += saL;}double saMean = saSum /3;var(rT, rC, rMs)=SolveRouting(inst,3);string rVsSa =FI(100.0*(saMean - rC)/saMean,"F1")+"%";Show(n.ToString().PadLeft(4)+" | "+FI(nnL).PadLeft(11)+" | "+FI(o2L).PadLeft(11)+" | "+(FI(saMean)+" (3s)").PadLeft(13)+" | "+FI(rC).PadLeft(10)+" | "+ rVsSa.PadLeft(11));}Show("");Show("routing (GLS, moteur industriel) >= SA sur grandes instances : il combine recherche");Show("locale guidee multi-operateur + premiere solution chemin-cout-min. Aucun code TSP");Show("dedie cote utilisateur : toute la logique vit dans le moteur Google, comme en Python.");
dedie cote utilisateur : toute la logique vit dans le moteur Google, comme en Python.
Verdict SOTA-OK. Le routing solver trouve l’optimum exact (= force brute) sur les petites instances (N=6,8,10) et sert de référence industrielle sur les grandes (N=30,60,100) où la force brute est infaisable (la cellule §6 le mesurait déjà : N=15 ≈ 8,7×10¹⁰ permutations).
Hiérarchie honnête des quatre approches (mesurée sur N=100) :
Méthode
Nature
Qualité
Plus proche voisin (from-scratch §3)
Heuristique greedy O(N²)
sous-optimale (~16% gap)
2-opt (from-scratch §4)
Recherche locale, optimum local
bloque loin de l’optimum
Recuit simulé (from-scratch §5)
Métaheuristique, acceptation de Metropolis
améliore 2-opt de ~1-4%
OR-Tools routing (Tranche 2)
Métaheuristique industrielle GLS
meilleure qualité, moteur de production
La force de RoutingModel n’est pas un certificat d’optimalité (c’est une métaheuristique, contrairement à CP-SAT) mais sa qualité robuste sur grandes instances grâce à la recherche locale guidée et ses opérateurs multi-renversements. La Tranche 1 from-scratch reste valable : elle rend tangible le fonctionnement intime de chaque méthode. Ce sont deux leviers complémentaires — la Tranche 2 donne au C# le même outillage industriel que le jumeau Python.
8. Exercices
Exercice 1 : insertion de villes (heuristique Or-opt)
Le 2-opt inverse des segments. Une autre recherche locale classique est l’Or-opt : extraire un segment de 1-3 villes et le réinsérer ailleurs. Implémenter ce mouvement et le combiner au 2-opt.
Indice : Array.Copy pour extraire puis insérer ; recalculer le delta de longueur sur les arêtes affectées seulement.
// Exercice 1 : Or-opt (deplacement de segment court) combine au 2-opt// Etape 1 : ecrire OrOpt(tsp, tour) qui tente de deplacer chaque segment [i..i+k] (k=1..3) vers une autre position si cela raccourcit.// Etape 2 : alterner TwoOpt et OrOpt jusqu'a fixpoint, comparer la qualite au 2-opt seul.Show("Exercice 1 a completer — Or-opt combine au 2-opt.");
Exercice 1 a completer — Or-opt combine au 2-opt.
Exercice 2 : colonies de fourmis (ACO)
L’ACO adapte la métaphore des fourmis : chaque « fourmi » construit une tournée en pondérant le choix de la prochaine ville par une phéromone τ et une heuristique η = 1/d. Les phéromones évaporent et sont renforcées par les meilleures tournées. Implémenter une version simple.
Indice : probabilité \(P(i \to j) \propto \tau_{ij}^\alpha \cdot \eta_{ij}^\beta\) ; mise à jour \(\tau \leftarrow (1-\rho)\tau + \Delta\tau\) après chaque itération.
// Exercice 2 : ACO simplifie// Etape 1 : matrice de pheromones tau initialisee a 1.// Etape 2 : chaque fourmi construit une tournee par tirage pondere (tau^alpha * (1/d)^beta).// Etape 3 : evaporation (tau *= (1-rho)) + depot sur la meilleure tournee. Iterer.Show("Exercice 2 a completer - ACO (construction ponderee par pheromones + evaporation).");
Exercice 2 a completer - ACO (construction ponderee par pheromones + evaporation).
Exercice 3 : optimalité du 2-opt sur un instance symétrique
Construire une instance où les villes sont placées sur un cercle. Montrer que (a) le 2-opt depuis n’importe quelle tournée atteint l’optimum (parcours du cercle), et (b) le plus-proche-voisin l’atteint aussi. Pourquoi cette instance est-elle « facile » ?
Indice : sur un cercle, la tournée optimale est le périmètre dans l’ordre des angles ; toute arête « croisée » est strictement plus longue que sa correction 2-opt (inégalité triangulaire).
// Exercice 3 : villes sur un cercle, montrer que 2-opt atteint l'optimum (perimetre)// Etape 1 : generer N points equirepartis sur un cercle de rayon R.// Etape 2 : lancer NN + 2-opt depuis une tournee aleatoire, comparer au perimetre 2*pi*R.// Etape 3 : verifier que 2-opt converge vers le perimetre (gap ~0%).Show("Exercice 3 a completer - circularite => 2-opt atteint l'optimum.");
Exercice 3 a completer - circularite => 2-opt atteint l'optimum.
Conclusion
Ce twin C# a déroulé from-scratch les piliers de la résolution approchée du TSP :
Force brute (exacte, référence, factorielle) ;
Plus proche voisin (construction gloutonne) ;
2-opt (recherche locale canonique par inversion de segments) ;
Recuit simulé (métaheuristique, move 2-opt + critère de Metropolis).
★ Leçon : le TSP cristallise le basculement exact ↔︎ approché. Les solveurs industriels (OR-Tools, twin Python ; GeneticSharp, autres twins C#) combinent ces briques à grande échelle ; ce twin les expose individuellement pour qu’on saisisse la mécanique de chaque heuristique.