(* TP09 branch-and-bound *) (* Avec 10 villes : 9! = 362880 circuits possibles à partir de Limoges *) let villes = [|"Limoges"; "Tulle"; "Périgueux"; "Toulouse"; "Bordeaux"; "Brive"; "Guéret"; "Niort"; "Rochefort"; "Bergerac"|];; let distances = [| [| 0; 90; 100; 290; 220; 90; 90; 230; 220; 200|]; (* distances depuis Limoges *) [| 90; 0; 120; 245; 245; 25; 175; 250; 360; 155|]; (* distances depuis Tulle *) [|100; 120; 0; 275; 140; 75; 185; 200; 250; 50|]; (* distances depuis Périgueux *) [|290; 245; 275; 0; 245; 205; 375; 425; 395; 210|]; (* distances depuis Toulouse *) [|220; 245; 140; 245; 0; 205; 300; 190; 165; 120|]; (* distances depuis Bordeaux *) [| 90; 25; 75; 205; 205; 0; 180; 255; 320; 130|]; (* distances depuis Brive *) [| 90; 175; 185; 375; 300; 180; 0; 230; 290; 300|]; (* distances depuis Gueret *) [|230; 250; 200; 425; 190; 255; 230; 0; 60; 260|]; (* distances depuis Niort *) [|220; 360; 250; 395; 165; 320; 290; 60; 0; 230|]; (* distances depuis Rochefort *) [|200; 155; 50; 210; 120; 130; 300; 260; 230; 0|]; (* distances depuis Bergerac *) |];; (* Avec 14 villes : 13! = 6 milliards de circuits possibles à partir de Limoges *) (* let villes = [|"Limoges"; "Tulle"; "Périgueux"; "Toulouse"; "Bordeaux"; "Brive"; "Guéret"; "Niort"; "Rochefort"; "Bergerac"; "Agen"; "Arras"; "Cahors"; "Villefranche de Rouergue"|];; let distances = [| [| 0; 90; 100; 290; 220; 90; 90; 230; 220; 200; 320; 570; 190; 225|]; (* distances depuis Limoges *) [| 90; 0; 120; 245; 245; 25; 175; 250; 360; 155; 270; 650; 130; 165|]; (* distances depuis Tulle *) [|100; 120; 0; 275; 140; 75; 185; 200; 250; 50; 140; 660; 175; 210|]; (* distances depuis Périgueux *) [|290; 245; 275; 0; 245; 205; 375; 425; 395; 210; 115; 850; 110; 130|]; (* distances depuis Toulouse *) [|220; 245; 140; 245; 0; 205; 300; 190; 165; 120; 140; 760; 233; 290|]; (* distances depuis Bordeaux *) [| 90; 25; 75; 205; 205; 0; 180; 255; 320; 130; 240; 655; 100; 140|]; (* distances depuis Brive *) [| 90; 175; 185; 375; 300; 180; 0; 230; 290; 300; 410; 565; 270; 310|]; (* distances depuis Gueret *) [|230; 250; 200; 425; 190; 255; 230; 0; 60; 260; 315; 590; 350; 470|]; (* distances depuis Niort *) [|220; 360; 250; 395; 165; 320; 290; 60; 0; 230; 290; 655; 385; 440|]; (* distances depuis Rochefort *) [|200; 155; 50; 210; 120; 130; 300; 260; 230; 0; 90; 775; 110; 175|]; (* distances depuis Bergerac *) [|320; 270; 140; 115; 140; 240; 410; 315; 290; 90; 0; 895; 85; 165|]; (* distances depuis Agen *) [|570; 650; 660; 850; 760; 655; 565; 590; 655; 775; 895; 0; 750; 785|]; (* distances depuis Arras *) [|190; 130; 175; 110; 233; 100; 270; 350; 385; 110; 85; 750; 0; 60|]; (* distances depuis Cahors *) [|225; 165; 210; 130; 290; 140; 310; 470; 440; 175; 165; 785; 60; 0|]; (* distances depuis Villefranche de Rouergue*) |];; *) (* Fonction d'affichage *) let affiche_trajet parcours = let lv = List.map (fun i -> villes.(i)) parcours in List.iter (fun v-> print_string v; print_string "->") lv; print_newline ();; (* Exemple d'affichage *) affiche_trajet [0;1;2;3;0];; (* Fonctions utilitaires *) let rec supprime x l = (* supprime une occurrence de l'élément x de la liste l *) failwith "à faire";; assert (supprime 3 [2;3;5] = [2;5]);; let rec distance par = (* calcule la longueur totale du parcours : somme des distances entre deux villes successives de la liste *) failwith "à faire" ;; assert (distance [3;2;1;4] = 640);; (* Backtracking classique *) let meilleur_parcours = ref [];; let meilleure_distance = ref max_int;; let rec backtrack par reste = (* par : parcours courant (en ordre inverse), reste : villes restant à visiter *) failwith "à faire" ;; backtrack [0] [1;2;3;4;5;6;7;8;9];; Printf.printf "Meilleure solution : %d\n" !meilleure_distance;; affiche_trajet !meilleur_parcours;; (* Backtracking b&b 1 *) let meilleur_parcours = ref [];; let meilleure_distance = ref max_int;; (* let rec backtrack_bnb_1 ... = *) (* A FAIRE *) Printf.printf "Meilleure solution B&B 1 : %d\n" !meilleure_distance;; affiche_trajet !meilleur_parcours;; (* Backtracking b&b 2 *) let meilleur_parcours = ref [];; let meilleure_distance = ref max_int;; (* let rec backtrack_bnb_2 ... = *) (* A FAIRE *) Printf.printf "Meilleure solution B&B 2 : %d\n" !meilleure_distance;; affiche_trajet !meilleur_parcours;;