Sujet Le Pub du Ctrl V

Citation : https://fr.audiofanzine.com/img/membres/normal/9/8/98961.jpg

Citation : http://rue89.com/2007/05/13/cecilia_sarkozy_na_pas_vote_un_scoop_censure_du_jdd

Citation : #open "random" ;;

(*"int 10 ;; donne un entier compris entre 0 et 9 non inclus"*)

let generateur_probleme taille valeur_max =
let matrice=(make_matrix taille taille 0) in
for k=0 to (taille-1)
do for q=k+1 to (taille-1)
do let a=int valeur_max in
(matrice.(k)).(q)<-a ;
(matrice.(q)).(k)<-a
done
done;
matrice
;;

(*utilise la fonction "random" (=tire au hasard un entier) pour creer une mautrice de flux ou de distance (note: ces matrices sont symétriques*)

let evaluation_legere place i j flux distance = let r=ref 0 in
let n =(vect_length place) in
for k = 0 to (n-1)
do r:=(((distance.(i)).(k))
*(((flux.(place.(i))).(place.(k)))
-((flux.(place.(j))).(place.(k))))+(!r))
done;
for k=0 to (n-1)
do r:=(((distance.(j)).(k))
*(((flux.(place.(j))).(place.(k)))
-((flux.(place.(i))).(place.(k))))+(!r))
done;(-(!r))
;;

(*implimente la formule plus "fine" vu dans le commentaire.
elle permet d'évaluer non pas le coût globale mais seulement la variation de ce coût*)

(*evaluation_legere [|1;0;2|]
1 2
[|[|0;5;1|];[|5;0;7|];[|1;7;0|]|]
[|[|0;1;2|];[|1;0;1|];[|2;1;0|]|] *)

let rec evaluation_sytematique_auxiliaire place liste flux distance =
match liste with
[(a,b)]->(a,b)
|[]->(0,0)
|(a,d)::b->

let (r,e)=
evaluation_sytematique_auxiliaire place b flux distance
in

if (evaluation_legere place r e flux distance )>
(evaluation_legere place a d flux distance )
then (a,d)
else (r,e)
;;

(*au départ on a un PLACEMENT des composants, la matrice des FLUX, celle des DISTANCES et enfin une LISTE DE PERMUTATIONS POSSIBLES.

l'algorithme est une fonction récursive simple: si le delta du mouvement selectionné est inférieur à celui du delta de la queue de la liste
alors il est sélectionné, sinon on prend celui de la queue de la liste.
on a bien diminution de la taille de la liste à chaque itération.
on arrête lorsqu'il n'y a plus qu'une permutation.
pour le cas où il n'y a pas de mouvement selectionné (liste vide), on affiche un message d'erreur (l'algorithme à échoué)*)


let selection_aleatoire place n = let l=((vect_length place))
and list= ref []
in

for k=1 to n
do list:=((int l),(int l)):!list)
done;
(!list)
;;





let transpose i j vect = let v=copy_vect vect in
v.(i)<-vect.(j);
v.(j)<-vect.(i);
v
;;

let controle permutation place interdiction rang =
let (i,j)=permutation in
let place2=transpose i j place in

if ((interdiction.(i)).(place2.(j)))<rang
&& ((interdiction.(j)).(place2.(i)))<rang
then [(i,j)]
else []
;;


let rec controletotal permutations place interdiction rang =
match permutations with
[]->[]
|a::b->(controle a place interdiction rang)
@(controletotal b place interdiction rang)

;;

let creation_tableau n = let tab=make_vect n 0 in
for k=0 to (n-1)
do tab.(k)<-k
done;tab
;;

let transpose2 i j vect = let a=(vect.(i)) in
vect.(i)<-(vect.(j));
vect.(j)<-a;
;;


let remplir_interdiction interdiction
nombres_mvt interdictionmin place i j rang =
let a = (rang+(int nombres_mvt-interdictionmin)
-interdictionmin)
in
(interdiction.(i)).(place.(i))<-a;
(interdiction.(j)).(place.(j))<-a
;;

let rec selection resultat_intermediaire nombres_mvt mat_interdiction compteur=


let a=( controletotal(selection_aleatoire resultat_intermediaire nombres_mvt) resultat_intermediaire mat_interdiction compteur)

in
if a=[]
then (selection resultat_intermediaire
nombres_mvt mat_interdiction compteur)
else a

;;







let euristhique etapes nombres_mvt interdictionmin flux distance =
let taille = (vect_length flux) in
let mat_interdiction=(make_matrix taille taille 0) in
let resultat_final= ref (creation_tableau taille) in
let resultat_intermediaire=creation_tableau taille in
let compteur = ref 0 in
let delta = ref 0 in

for k = 1 to etapes
do (incr compteur);
let a =( controletotal(selection_aleatoire resultat_intermediaire nombres_mvt)
resultat_intermediaire mat_interdiction (!compteur))
in
let (c,d) = (evaluation_sytematique_auxiliaire resultat_intermediaire
a flux distance)
in
transpose2 c d resultat_intermediaire ;
let var=(!delta)+(evaluation_legere resultat_intermediaire c d flux distance) in
if var<(!delta)
then resultat_final:=resultat_intermediaire ;
remplir_interdiction mat_interdiction nombres_mvt interdictionmin
resultat_intermediaire c d (!compteur);
delta:=var
done;(!resultat_final)
;;

let selection n resultat_intermediaire nombres_mvt mat_interdiction compteur = let compte=ref 0 in
let a= ref (selectionbis resultat_intermediaire nombres_mvt mat_interdiction compteur )in
while (((!a)=[]) || ((!compte)<n))
do a:= (selectionbis resultat_intermediaire nombres_mvt mat_interdiction compteur) ;
compte:= ((!compte)+1);
done;!a
;;

let euristhique etapes nombres_mvt interdictionmin flux distance =
let taille = (vect_length flux) in
let mat_interdiction=(make_matrix taille taille 0) in
let resultat_final= ref (creation_tableau taille) in
let resultat_intermediaire=creation_tableau taille in
let compteur = ref 0 in
let delta = ref 0 in

for k = 1 to etapes
do (incr compteur);
let a =(selection taille resultat_intermediaire nombres_mvt mat_interdiction (!compteur))
in
let (c,d) = (evaluation_sytematique_auxiliaire resultat_intermediaire
a flux distance)
in
transpose2 c d resultat_intermediaire ;
let var=(!delta)+(evaluation_legere resultat_intermediaire c d flux distance) in
if var<(!delta)
then resultat_final:=resultat_intermediaire ;
remplir_interdiction mat_interdiction nombres_mvt interdictionmin
resultat_intermediaire c d (!compteur);
delta:=var
done;(!resultat_final)
;;


let evaluation place flux distance = let resultat = ref 0
and l = ((vect_length place)-1) in
for k=0 to l
do for q=k to l
do resultat:=(!resultat)+((flux.((place.(k)))).((place.(q))))
*(distance.(k)).(q)
done
done;
!resultat
;;
let rec insert e list = match list with
[]->[e]
|a::b->if a>e then (e::a::b) else (a::insert e b)
;;



let rec rajoute tab i j list = match j with
0->tab.(i)<-(hd list)
|_->rajoute tab i (j-1) (tl list)
;;

let rec proche e d list = match list with
[]->0
|[a]->a
|a::b->let d2=a-e in if (0<d2 &&d2<d) then let h=(proche e d2 b) in (min h a)
else proche e d b
;;

let rec retire e list = match list with
[]->[]
|a::b->if a=e then b else a:retire e b)
;;

let suivant tab = let lg= vect_length tab in
let reserve= ref [] in
let k= ref (lg-1) in
let maxi = ref (-1) in

while (!maxi)<tab.(!k)
do reserve:=(insert (tab.(!k))(!reserve));
maxi:= tab.(!k);
k:=((!k)-1)
done;
let t=tab.(!k) in
tab.(!k)<-(proche (tab.(!k)) lg (!reserve));
reserve:=(insert t(!reserve));
reserve:=(retire (tab.(!k)) (!reserve));
for q = (!k)+1 to (lg-1)
do (rajoute tab q (q-((!k)+1)) (!reserve))
done
;;

suivant [|0;1;2;3|] ;;

let creer n = let tab=make_vect n 0 in
for k = 1 to (n-1)
do tab.(k)<-k
done;tab
;;

let creerb n = let tab=make_vect n 0 in
for k = 0 to (n-1)
do tab.(k)<-(n-k-1)
done;tab
;;

let evaluation_barbar flux distance =

let tab=(creer (vect_length flux)) in
let fin=(creerb (vect_length flux)) in
let resultat=ref (copy_vect tab) in
let cout= ref (evaluation tab flux distance) in
suivant tab ;

while tab<>fin
do let a=(evaluation tab flux distance) in if a<(!cout)
then (resultat:=(copy_vect tab) ; cout:=a);
suivant tab;
done;if (!cout)>(evaluation fin flux distance)
then fin
else(!resultat)
;;


let make_matricecubique n = let tab=(make_vect n (make_vect n (make_vect n (-1))))in
let m= ( make_vect n (-1) ) in

for i=0 to (n-1)
do for j = 0 to (n-1)
do (tab.(i)).(j)<-(copy_vect m)
done
done;
tab;;


let statistique n max etapes = let flux=generateur_probleme n max in
let distance=generateur_probleme n max in
let delta = (evaluation (evaluation_barbar flux distance) flux distance) in
let resultat = make_matricecubique etapes in
for k=1 to etapes
do for i = 1 to etapes
do for j = 1 to etapes
do let a=euristhique k i j flux distance in resultat.(i-1).(j-1).(k-1)<-((evaluation a flux distance)-delta)
done done done; resultat;;


statistique 10 10 10 ;;


#open "random" ;;

(*"int 10 ;; donne un entier compris entre 0 et 9 non inclus"*)

let generateur_probleme taille valeur_max =
let matrice=(make_matrix taille taille 0) in
for k=0 to (taille-1)
do for q=k+1 to (taille-1)
do let a=int valeur_max in
(matrice.(k)).(q)<-a ;
(matrice.(q)).(k)<-a
done
done;
matrice
;;

(*utilise la fonction "random" (=tire au hasard un entier) pour creer une mautrice de flux ou de distance (note: ces matrices sont symétriques*)

let evaluation_legere place i j flux distance = let r=ref 0 in
let n =(vect_length place) in
for k = 0 to (n-1)
do r:=(((distance.(i)).(k))
*(((flux.(place.(i))).(place.(k)))
-((flux.(place.(j))).(place.(k))))+(!r))
done;
for k=0 to (n-1)
do r:=(((distance.(j)).(k))
*(((flux.(place.(j))).(place.(k)))
-((flux.(place.(i))).(place.(k))))+(!r))
done;(-(!r))
;;

(*implimente la formule plus "fine" vu dans le commentaire.
elle permet d'évaluer non pas le coût globale mais seulement la variation de ce coût*)

(*evaluation_legere [|1;0;2|]
1 2
[|[|0;5;1|];[|5;0;7|];[|1;7;0|]|]
[|[|0;1;2|];[|1;0;1|];[|2;1;0|]|] *)

let rec evaluation_sytematique_auxiliaire place liste flux distance =
match liste with
[(a,b)]->(a,b)
|[]->(0,0)
|(a,d)::b->

let (r,e)=
evaluation_sytematique_auxiliaire place b flux distance
in

if (evaluation_legere place r e flux distance )>
(evaluation_legere place a d flux distance )
then (a,d)
else (r,e)
;;

(*au départ on a un PLACEMENT des composants, la matrice des FLUX, celle des DISTANCES et enfin une LISTE DE PERMUTATIONS POSSIBLES.

l'algorithme est une fonction récursive simple: si le delta du mouvement selectionné est inférieur à celui du delta de la queue de la liste
alors il est sélectionné, sinon on prend celui de la queue de la liste.
on a bien diminution de la taille de la liste à chaque itération.
on arrête lorsqu'il n'y a plus qu'une permutation.
pour le cas où il n'y a pas de mouvement selectionné (liste vide), on affiche un message d'erreur (l'algorithme à échoué)*)


let selection_aleatoire place n = let l=((vect_length place))
and list= ref []
in

for k=1 to n
do list:=((int l),(int l)):!list)
done;
(!list)
;;





let transpose i j vect = let v=copy_vect vect in
v.(i)<-vect.(j);
v.(j)<-vect.(i);
v
;;

let controle permutation place interdiction rang =
let (i,j)=permutation in
let place2=transpose i j place in

if ((interdiction.(i)).(place2.(j)))<rang
&& ((interdiction.(j)).(place2.(i)))<rang
then [(i,j)]
else []
;;


let rec controletotal permutations place interdiction rang =
match permutations with
[]->[]
|a::b->(controle a place interdiction rang)
@(controletotal b place interdiction rang)

;;

let creation_tableau n = let tab=make_vect n 0 in
for k=0 to (n-1)
do tab.(k)<-k
done;tab
;;

let transpose2 i j vect = let a=(vect.(i)) in
vect.(i)<-(vect.(j));
vect.(j)<-a;
;;


let remplir_interdiction interdiction
nombres_mvt interdictionmin place i j rang =
let a = (rang+(int nombres_mvt-interdictionmin)
-interdictionmin)
in
(interdiction.(i)).(place.(i))<-a;
(interdiction.(j)).(place.(j))<-a
;;

let rec selection resultat_intermediaire nombres_mvt mat_interdiction compteur=


let a=( controletotal(selection_aleatoire resultat_intermediaire nombres_mvt) resultat_intermediaire mat_interdiction compteur)

in
if a=[]
then (selection resultat_intermediaire
nombres_mvt mat_interdiction compteur)
else a

;;







let euristhique etapes nombres_mvt interdictionmin flux distance =
let taille = (vect_length flux) in
let mat_interdiction=(make_matrix taille taille 0) in
let resultat_final= ref (creation_tableau taille) in
let resultat_intermediaire=creation_tableau taille in
let compteur = ref 0 in
let delta = ref 0 in

for k = 1 to etapes
do (incr compteur);
let a =( controletotal(selection_aleatoire resultat_intermediaire nombres_mvt)
resultat_intermediaire mat_interdiction (!compteur))
in
let (c,d) = (evaluation_sytematique_auxiliaire resultat_intermediaire
a flux distance)
in
transpose2 c d resultat_intermediaire ;
let var=(!delta)+(evaluation_legere resultat_intermediaire c d flux distance) in
if var<(!delta)
then resultat_final:=resultat_intermediaire ;
remplir_interdiction mat_interdiction nombres_mvt interdictionmin
resultat_intermediaire c d (!compteur);
delta:=var
done;(!resultat_final)
;;

let selection n resultat_intermediaire nombres_mvt mat_interdiction compteur = let compte=ref 0 in
let a= ref (selectionbis resultat_intermediaire nombres_mvt mat_interdiction compteur )in
while (((!a)=[]) || ((!compte)<n))
do a:= (selectionbis resultat_intermediaire nombres_mvt mat_interdiction compteur) ;
compte:= ((!compte)+1);
done;!a
;;

let euristhique etapes nombres_mvt interdictionmin flux distance =
let taille = (vect_length flux) in
let mat_interdiction=(make_matrix taille taille 0) in
let resultat_final= ref (creation_tableau taille) in
let resultat_intermediaire=creation_tableau taille in
let compteur = ref 0 in
let delta = ref 0 in

for k = 1 to etapes
do (incr compteur);
let a =(selection taille resultat_intermediaire nombres_mvt mat_interdiction (!compteur))
in
let (c,d) = (evaluation_sytematique_auxiliaire resultat_intermediaire
a flux distance)
in
transpose2 c d resultat_intermediaire ;
let var=(!delta)+(evaluation_legere resultat_intermediaire c d flux distance) in
if var<(!delta)
then resultat_final:=resultat_intermediaire ;
remplir_interdiction mat_interdiction nombres_mvt interdictionmin
resultat_intermediaire c d (!compteur);
delta:=var
done;(!resultat_final)
;;


let evaluation place flux distance = let resultat = ref 0
and l = ((vect_length place)-1) in
for k=0 to l
do for q=k to l
do resultat:=(!resultat)+((flux.((place.(k)))).((place.(q))))
*(distance.(k)).(q)
done
done;
!resultat
;;
let rec insert e list = match list with
[]->[e]
|a::b->if a>e then (e::a::b) else (a::insert e b)
;;



let rec rajoute tab i j list = match j with
0->tab.(i)<-(hd list)
|_->rajoute tab i (j-1) (tl list)
;;

let rec proche e d list = match list with
[]->0
|[a]->a
|a::b->let d2=a-e in if (0<d2 &&d2<d) then let h=(proche e d2 b) in (min h a)
else proche e d b
;;

let rec retire e list = match list with
[]->[]
|a::b->if a=e then b else a:retire e b)
;;

let suivant tab = let lg= vect_length tab in
let reserve= ref [] in
let k= ref (lg-1) in
let maxi = ref (-1) in

while (!maxi)<tab.(!k)
do reserve:=(insert (tab.(!k))(!reserve));
maxi:= tab.(!k);
k:=((!k)-1)
done;
let t=tab.(!k) in
tab.(!k)<-(proche (tab.(!k)) lg (!reserve));
reserve:=(insert t(!reserve));
reserve:=(retire (tab.(!k)) (!reserve));
for q = (!k)+1 to (lg-1)
do (rajoute tab q (q-((!k)+1)) (!reserve))
done
;;

suivant [|0;1;2;3|] ;;

let creer n = let tab=make_vect n 0 in
for k = 1 to (n-1)
do tab.(k)<-k
done;tab
;;

let creerb n = let tab=make_vect n 0 in
for k = 0 to (n-1)
do tab.(k)<-(n-k-1)
done;tab
;;

let evaluation_barbar flux distance =

let tab=(creer (vect_length flux)) in
let fin=(creerb (vect_length flux)) in
let resultat=ref (copy_vect tab) in
let cout= ref (evaluation tab flux distance) in
suivant tab ;

while tab<>fin
do let a=(evaluation tab flux distance) in if a<(!cout)
then (resultat:=(copy_vect tab) ; cout:=a);
suivant tab;
done;if (!cout)>(evaluation fin flux distance)
then fin
else(!resultat)
;;


let make_matricecubique n = let tab=(make_vect n (make_vect n (make_vect n (-1))))in
let m= ( make_vect n (-1) ) in

for i=0 to (n-1)
do for j = 0 to (n-1)
do (tab.(i)).(j)<-(copy_vect m)
done
done;
tab;;


let statistique n max etapes = let flux=generateur_probleme n max in
let distance=generateur_probleme n max in
let delta = (evaluation (evaluation_barbar flux distance) flux distance) in
let resultat = make_matricecubique etapes in
for k=1 to etapes
do for i = 1 to etapes
do for j = 1 to etapes
do let a=euristhique k i j flux distance in resultat.(i-1).(j-1).(k-1)<-((evaluation a flux distance)-delta)
done done done; resultat;;


statistique 10 10 10 ;;

Citation : pfff c'est d'un ennui ce post

Citation : nan c'est très très drole à faire marcher ce programme

Citation : http://beatmaker-hiphop.forumactif.com/

Citation : je confirme, ça marche

Citation :