Discussion :

[Jeanpasse]

Bonjour,

j'essaie de de coder l'algorithme hongrois d'affectation optimale en camllight mais je rencontre quelques difficultés... En fait mon programme marche pour des tableaux de petites tailles mais tourne indéfiniment pour des tableaux de tailles supérieures a 10 et il lui arrive même de tourner parfois pour des tableaux plus petits.

Le problème je pense vient de l'étape de rayage de la matrice en un nombre de traits minimal. Il effectue le rayage avec trop de traits, croit la matrice exploitable et tourne pour trouver une combinaison solution (qui en réalité n'existe pas)
Voici donc mon code pour cette partie de l'algorithme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
(* Fonctions auxiliaires *)
 
 
(* Rang de l'élément minimal d'un tableau *)
let min_table t =
	let result = ref 0 in
	for i = 0 to (vect_length(t)-1)
	do 	if t.(i)<=t.(!result)
		then result:=i
		else ()
	done;
	!result;;
 
 
(* Rayage de la matrice étape 1 *)
let rayage_un m m' a u b v = match (a.(u),b.(v)) with
    |false,false ->   begin
                      match (m.(u).(v)=0.) with
                        |true ->  begin
                                  m'.(u).(v)<-3;
                                  a.(u)<- true;
                                  b.(v)<- true
                                  end
                        |false -> ()
                      end
    |_,_ -> ();;
 
(* Calcul du nombre de 0 non rayés *)
let calc_0 q m a b n =
   q:=0;
    for i = 0 to (n-1)
    do         for j = 0 to (n-1)
               do        if not(a.(i))  && not(b.(j)) && (m.(i).(j)=0.)
                         then q := !q+1
                         else ()
               done;
    done;;
 
 
 (* Rayage 2*)      
 
let rayage_deux m n m' a u b v = match (a.(u),b.(v)) with
    |false,false  ->  begin
                      match (m.(u).(v)=0.) with
                        |true  ->  begin
 
                                    m'.(u).(v)<-1;
                                    let k = ref 0 in
                                    while !k<n  && m'.(u).(!k)<>3
                                    do		k:=!k+1
                                    done;
 
                                    if !k>=n
                                    then b.(v)<-true
                                    else  begin a.(u)<-true; b.(!k)<-false end
 
                                   end
                        |false -> ()
                        end
    |_,_->();;
 
(* corps de l'algorithme *)
 
let marquage = make_matrix n n 0 in        
let lig = make_vect n false in
let col = make_vect n false in    
 
let zeros_lig = make_vect n 0 in
 
 
let c = min_table zeros_lig in
    for i = c to p
    do    for j = 0 to p 
          do  rayage_un m marquage lig i col j
          done;
    done;
 
	for i = 0 to (c-1)
    do    for j = 0 to p 
          do  rayage_un m marquage lig i col j
          done;
    done;
 
 
let lig = make_vect n false in
let uncov_zeros = ref 0 in
 
calc_0 uncov_zeros m lig col n;
 
 
    while !uncov_zeros<>0
    do    for i = 0 to p
          do    for j = 0 to p
                do rayage_deux m n marquage lig i col j
                done;
          done;
 
          calc_0 uncov_zeros m lig col n;
    done;

Légende: Lig et col sont des tableaux de booléens disant si la ligne ou la colonne de la matrice est barrée.

Merci de me suggérer pour des idées d'amélioration et de correction (je sais qu'il doit y en avoir pas mal...) ou même si quelqu'un connait un lien direct qui explique concrêtement comment coder cet algorithme ou bien un code déjà écrit sur lequel je puisse m'appuyer...

Enfin bref, Merci beaucoup

[Cacophrene]

Bonsoir,

Sans avoir regardé le code de façon détaillée, je remarque un grand nombre de boucles for et while, ainsi que des variables aux noms peu explicites, ce qui n'est généralement pas considéré comme une bonne pratique de programmation en caml (light ou pas).

Peut-être que l'algorithme hongrois ne se prête pas bien à un autre type de programmation, mais je dirais d'emblée qu'une partie du problème vient de là : en l'état actuel, le code est assez hermétique et donc d'un abord peu facile.

Cordialement,
Cacophrène

[Jeanpasse]

Je sais... C'est un peu mon problème.
Déjà j'ai essayé de définir pas mal de fonctions auxiliaires avec des match pour rendre ça plus lisible que des ribambelles de if les uns dans les autres mais puisqu'il faut parcourir la matrice m pour rayer tous les zéros en un minimum de traits je ne vois pas trop comment faire sans des boucles for et while...
De plus j'ai rencontré des bugs quand mes fonctions étaient uniquement définies comme internes au programme (messages du types "cette expression n'est pas une fonction, elle ne peut être appliquée" alors qu'il s'agissait justement d'une opération de type unit que devait effectuer la fonction...?), resultat j'ai préféré les définir globalement en augmentant de ce fait le nombre d'arguments (qui est illisible, même pour moi qui suis "dans le bain"). Est ce que quelqu'un sait comment résoudre ce problème?