Discussion :

[xvid110]

Bonjour,
Je dois programmer l'algo de dijkstra et j'ai un problème de compilation sur le "done;" voici mon code:

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
				(* 1 ;  2 ;  3 ;  4 ;  5 *)
let mat = [|[| 0 ; 10 ;  6 ; -1 ; -1 |];  (* 1 *)
				[| 0 ;  0 ; -1 ;  2 ;  4 |];  (* 2 *)
				[| 0 ;  0 ;  0 ;  1 ;  7 |];  (* 3 *)
				[| 0 ;  0 ;  0 ;  0 ;  9 |];  (* 4 *)
				[| 0 ;  0 ;  0 ;  0 ;  0 |]|] (* 5 *)
;;
 
 
let poid n1 n2 =
	if mat.(n1-1).(n2-1) <> 0 & n1<>n2 then mat.(n1-1).(n2-1)
	else if n1<>n2 then mat.(n2-1).(n1-1)
	else 0
	;;
 
 
let poid_p mat_p n1 n2 =
	mat_p.(n1-1).(n2-1);;
 
 
let rec minimum = function
	| [x] , i -> x
	| h::t ,i -> 	
			match (poid i h) with
			| 0  -> 	failwith "Le point de depart est dans provisoire!"
			| _  -> 	if (poid i h) < (poid i (minimum (t,i))) then h 
						else (minimum (t,i));;
 
 
let rec remove_list x = function
	| [] 	-> failwith "Rien a supprimer"
	| h::t -> if h = x then t else h::(remove_list x t);;
 
 
let rec belong_list x = function
	| [] 	 -> false
	| h::t -> if x = h then true else belong_list x t;;
 
 
let dijkstra mat =
	(* Initialisation *)
	let calcule = ref [1] in
	let provisoires = ref [] in
	let mat_p = ref mat in
	for i = 2 to 5 do
		if (poid 1 i) <> (-1) then provisoires := i::!provisoires;
	done;
	(*----------------*)
 
	(* Itérations *)
	while !provisoires <> [] do
		let x = minimum !provisoires 1 in
		calcule := x::!calcule;
		provisoires := remove_list x !provisoires;
		for y = 2 to 5 do
			if (poid x y) <> (-1) & x<>y 
			then begin
            	if belong_list y !calcule then failwith "calcule"
					else if belong_list y !provisoires 
					then begin
						if (poid_p mat_p 1 x) + (poid x y) < (poid_p mat_p 1 y) then
						!mat_p.(0).(y) <- (poid_p !mat_p 1 x) + (poid !mat_p x y) 
					end
					else begin
						provisoires := y::!provisoires;
						!mat_p.(0).(y) <- (poid_p !mat_p 1 x) + (poid x y);
					end
				end;
		done;
	done;
	!mat_p;
;;

Je ne vois vraiment pas l'erreur!

[xvid110]

J'ai résolu ce problème maintenant il faudrait que je corrige la fonction minimum!

[Cacophrene]

Bonjour,

Quelques remarques en vrac pour t'aider un peu dans ton débogage et dans l'écriture du code caml :

• L'opérateur & est obsolète : remplacer par &&.
• Un détail qui le fait pas du tout : c'est poids ou weight.
• Pour ta fonction minimum, le premier filtrage ne gère pas le cas de la liste vide. De plus la fonction peut être écrite avec deux arguments t et i distincts plutôt qu'un couple de valeurs.
• Ta fonction belong_list est une spécialisation de List.mem. Le second cas peut s'écrire plus simplement x = h || belong_list x t

Cordialement,
Cacophrène

[xvid110]

Merci pour ces conseil je précise simplement que je programme avec caml-light et je ne vois pas comment programmer ma fonction minimum!

[Cacophrene]

je ne vois pas comment programmer ma fonction minimum

Que doit faire exactement cette fonction ?

Cordialement,
Cacophrène

[xvid110]

La matrice mat représente les poids entre les différents points du graphes et la fonction minimum doit trouver le poids minimum entre un point et l'ensemble des points d'une liste (la liste provisoires).

[xvid110]

Ok bon j'ai reprogrammé la fonction minimum en la séparant en deux fonctions seulement la case 0.4 de la matrice mat_p ne se rempli pas comme elle devrait quelles erreurs ai-je donc faites?

minimum:

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
let rec min_r = function
	| [] , i -> failwith "liste vide"
	| [x] ,i	 -> x
	| h::t ,i -> 	
			match (poid i h) with
			| 0  -> 	failwith "Le point de depart est dans provisoire!"
			| a  -> 	if (poid i (min_r (t,i))) > a then h
						else (min_r (t,i));;
 
 
let minimum l i =
	let list_poid =ref[] in
	for k=1 to 10 do
	if belong_list k l & poid i k <> (-1) then list_poid:= k::!list_poid
	done;
	min_r (!list_poid,i);
;;

En testant avec l'exemple de wiki http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra Toute les cases de mon tableau sont bonnes sauf la dernière, le code:

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
101
102
103
104
105
106
107
let mat = [|[| 0 ; 85 ; 217 ; -1 ; 173 ; -1 ; -1  ; -1  ; -1  ; -1  |];  (* 1 *)
				[| 0 ;  0 ; -1  ; -1 ; -1  ; 80 ; -1  ; -1  ; -1  ; -1  |];  (* 2 *)
				[| 0 ;  0 ;  0  ; -1 ; -1  ; -1 ; 186 ; 103 ; -1  ; -1  |];  (* 3 *)
				[| 0 ;  0 ;  0  ;  0 ; -1  ; -1 ; -1  ; 183 ; -1  ; -1  |];  (* 4 *)
				[| 0 ;  0 ;  0  ;  0 ;  0  ; -1 ; -1  ; -1  ; -1  ; 502 |];
				[| 0 ;  0 ;  0  ;  0 ;  0  ;  0 ; -1  ; -1  ; 250 ; -1  |];
				[| 0 ;  0 ;  0  ;  0 ;  0  ;  0 ;  0  ; -1  ; -1  ; -1  |];
				[| 0 ;  0 ;  0  ;  0 ;  0  ;  0 ;  0  ;  0  ; -1  ; 167 |];
				[| 0 ;  0 ;  0  ;  0 ;  0  ;  0 ;  0  ;  0  ;  0  ;  84 |];
				[| 0 ;  0 ;  0  ;  0 ;  0  ;  0 ;  0  ;  0  ;  0  ;  0  |]|];;
 
 
let poid n1 n2 =
	if n1<n2 then mat.(n1-1).(n2-1)
	else if n1=n2 then 0
	else mat.(n2-1).(n1-1)
	;;
 
 
let poid_p mat_p n1 n2 =
	mat_p.(n1-1).(n2-1);;
 
 
let rec remove_list x = function
	| [] 	-> failwith "Rien a supprimer"
	| h::t -> if h = x then t else h::(remove_list x t);;
 
 
let rec belong_list x = function
	| [] 	 -> false
	| h::t -> if x = h then true else belong_list x t;;
 
 
#open "printf";;
let affiche mat =
 
	for i = 0 to 9 do
		printf "[|";
		for j = 0 to 8 do
			printf "%d ; " mat.(i).(j);
		done;
		printf "%d|]" mat.(i).(4);
		print_newline ();
	done;;
 
 
let rec min_r = function
	| [] , i -> failwith "liste vide"
	| [x] ,i	 -> x
	| h::t ,i -> 	
			match (poid i h) with
			| 0  -> 	failwith "Le point de depart est dans provisoire!"
			| a  -> 	if (poid i (min_r (t,i))) > a then h
						else (min_r (t,i));;
 
 
let minimum l i =
	let list_poid =ref[] in
	for k=1 to 10 do
	if belong_list k l & poid i k <> (-1) then list_poid:= k::!list_poid
	done;
	min_r (!list_poid,i);
;;
 
 
let dijkstra mat =
	(* Initialisation *)
	let calcule = ref [1] in
	let provisoires = ref [] in
	let mat_p = ref mat in
	for i = 2 to 10 do
		if (poid 1 i) <> (-1) then provisoires := i::!provisoires;
	done;
	(*----------------*)
 
	(* Itérations *)
	while !provisoires <> [] do
		(*affiche mat;
		printf "mat-p";
		print_newline ();
		affiche !mat_p;*)
		let x = minimum !provisoires 1 in
		calcule := x::!calcule;
		provisoires := remove_list x !provisoires;
		for y = 2 to 10 do
			if (poid x y) <> (-1) & x<>y 
			then begin
            	if not(belong_list y !calcule) then begin
						if belong_list y !provisoires 
						then begin
							if (poid_p !mat_p 1 x) + (poid x y) < (poid_p !mat_p 1 y) then
							!mat_p.(0).(y-1) <- (poid_p !mat_p 1 x) + (poid x y)
						end
						else begin
							provisoires := y::!provisoires;
							!mat_p.(0).(y-1) <- (poid_p !mat_p 1 x) + (poid x y);
						end
					end
				end
		done;
	done;
	affiche !mat_p;
	print_newline ();
	!calcule;
;;
 
dijkstra mat;;