(* 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 *)
  match l with
| [] -> failwith "erreur"
| e::ll -> if e = x then ll else e::(supprime x ll);;

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 *)
  match par with
  | [] -> failwith "Impossbile"
  | [v] -> 0
  | v :: w :: ppar -> distances.(v).(w) + distance (w::ppar)
;;

assert (distance [3;2;1;4] = 640);;

(* Backtracking classique *)

let meilleur_parcours = ref [];;
let meilleure_distance = ref max_int;;

let compteur_appels = ref 0;;

let rec backtrack par reste =
  (* par : parcours courant en ordre inverse,
     reste : villes restant à visiter *)
  compteur_appels := !compteur_appels + 1;
  if reste = [] then (* parcours complet : penser à revenir au point de départ *)
    begin
      let circuit = 0::par in
      let dist = distance circuit in
      if dist < !meilleure_distance then begin
        meilleure_distance := dist;
        meilleur_parcours := List.rev circuit
      end
    end
  else begin
    (* pour chaque élément de la liste reste, 
       appeler backtracking avec les bons paramètres *)
    let poursuivre_avec s =
      backtrack (s::par) (supprime s reste)
    in
    List.iter poursuivre_avec reste
  end;;

backtrack [0] [1;2;3;4;5;6;7;8;9];;

Printf.printf "Meilleure solution : %d (en %d appels)\n" !meilleure_distance !compteur_appels;;
affiche_trajet !meilleur_parcours;; (* 10 villes : 986410 appels  -  14 villes : ??? appels *)


(* Backtracking b&b 1 *)

let meilleur_parcours = ref [];;
let meilleure_distance = ref max_int;;

let compteur_appels = ref 0;;

let rec backtrack_bnb_1 par dist reste =
  (* par : parcours courant en ordre inverse,
     dist : distance totale courante, 
     reste : villes restant à visiter *)
  compteur_appels := !compteur_appels + 1;
  if reste = [] then (* parcours complet : penser à revenir au point de départ *)
    begin
      let last = List.hd par (* tete de liste *)
      in
      if dist + distances.(last).(0) < !meilleure_distance then begin
        meilleure_distance := dist + distances.(last).(0);
        meilleur_parcours := List.rev (0::par) (* ne pas oublier le retour à Limoges *)
      end
    end
  else begin
    let last = List.hd par in 
    if (dist + distances.(last).(0) >= !meilleure_distance) then
      ()   (* élagage : inutile de poursuivre si on a déjà un parcours trop long *)
    else
      let poursuivre_avec s =
        backtrack_bnb_1 (s::par) (dist + distances.(last).(s)) (supprime s reste)
      in
      List.iter poursuivre_avec reste
  end;;

backtrack_bnb_1 [0] 0 [1;2;3;4;5;6;7;8;9];;

Printf.printf "Meilleure solution B&B 1 : %d (en %d appels)\n" !meilleure_distance !compteur_appels;;
affiche_trajet !meilleur_parcours;;  (* 10 villes : 100593 appels  -  14 villes : ???? appels *)


(* Backtracking b&b 2 *)

let meilleur_parcours = ref [];;
let meilleure_distance = ref max_int;;

let compteur_appels = ref 0;;

let rec backtrack_bnb_2 par dist reste =
  (* par : parcours courant en ordre inverse,
     dist : distance totale courante, 
     reste : villes restant à visiter *)
  compteur_appels := !compteur_appels + 1;
  if reste = [] then (* parcours complet : penser à revenir au point de départ *)
    begin
      let last = List.hd par (* tete de liste *)
      in
      if dist + distances.(last).(0) < !meilleure_distance then begin
        meilleure_distance := dist + distances.(last).(0);
        meilleur_parcours := List.rev (0::par)
      end
    end
  else begin
    if (dist < !meilleure_distance) then (* élagage brutal pour éviter les calculs inutiles *)

      (* on cherche la plus grande distance  : sommet_courant -> sommet restant -> Limoges *)
      let last = List.hd par in (* sommet courant *)

      let maxi = ref min_int in
      let traite s =
        let d = distances.(last).(s) + distances.(s).(0) in
        if d > !maxi then maxi := d
      in
      List.iter traite reste;

      if dist + !maxi >= !meilleure_distance then
        () (* élagage*)
      else
        let poursuivre_avec s =
          backtrack_bnb_2 (s::par) (dist + distances.(last).(s)) (supprime s reste)
        in
        List.iter poursuivre_avec reste
  end;;

backtrack_bnb_2 [0] 0 [1;2;3;4;5;6;7;8;9];;


Printf.printf "Meilleure solution B&B 2 : %d (en %d appels)\n" !meilleure_distance !compteur_appels;;
affiche_trajet !meilleur_parcours;; (* 10 villes : 9047 appels  -  14 villes : 1961944 appels *)

(* Backtracking b&b 3 *)

let meilleur_parcours = ref [];;
let meilleure_distance = ref max_int;;

let compteur_appels = ref 0;;

let rec backtrack_bnb_3 par dist reste =
  (* par : parcours courant en ordre inverse,
     dist : distance totale courante, 
     reste : villes restant à visiter *)
  compteur_appels := !compteur_appels + 1;
  if reste = [] then (* parcours complet : penser à revenir au point de départ *)
    begin
      let last = List.hd par (* tete de liste *)
      in
      if dist + distances.(last).(0) < !meilleure_distance then begin
        meilleure_distance := dist + distances.(last).(0);
        meilleur_parcours := List.rev (0::par)
      end
    end
  else begin
    if (dist < !meilleure_distance) then (* élagage brutal pour éviter les calculs inutiles *)

      (* on cherche la plus grande distance  : sommet_courant -> sommet restant -> Limoges *)
      let last = List.hd par in (* sommet courant *)

      let maxi = ref min_int in
      let traite s =
        let d = distances.(last).(s) + distances.(s).(0) in
        if d > !maxi then maxi := d
      in
      List.iter traite reste;

      if dist + !maxi >= !meilleure_distance then
        () (* élagage*)
      else 
        let poursuivre_avec s =
          backtrack_bnb_3 (s::par) (dist + distances.(last).(s)) (supprime s reste)
        in

        (* on reordonne reste *)
        let reste2 = List.sort (fun x y -> distances.(last).(x) -  distances.(last).(y)) reste in

        List.iter poursuivre_avec reste2
  end;;

backtrack_bnb_3 [0] 0 [1;2;3;4;5;6;7;8;9];;


Printf.printf "Meilleure solution B&B 3 : %d (en %d appels)\n" !meilleure_distance !compteur_appels;;
affiche_trajet !meilleur_parcours;; (* 10 villes : 7954 appels -  14 villes : 1787071 appels *)