Discussion :

[HourofRagnarok]

J'accumule les problèmes sur mon algorithme de Dijkstra.
Si vous pouvez m'aider à trouver où caml relève un invalid_argument "vect_item", cela fait deux jours que je m'arrache les cheveux dessus...

Voici mon algorithme, et la réponse de Caml :

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
let distance_min e = 
    let n= vect_length e in 
	let rec comparer2 = fun
	      d t i j when i=n+1 -> t
	    | d t i j when j=n+1 -> comparer2 d t (i+1) 0
	    | d t i j -> let m= (M.(i)).(j-1) in 
			     let g = m+snd(e.(i)) in
			 if fst(e.(j))=j && fst(e.(i))<>i && m<>0 &&( g<d or d=0)
 					then comparer2 g ((i,j),m) i (j+1)
						else comparer2 d t i (j+1) 
		in comparer2 0 ((0,0),0) 0 1;;
 
let dijkstra t = 
	let l= ref([]) in
		let n= (vect_length t) in
			let e= make_vect n (0,0) in e.(0)<- (-1,0) ; 
                             for i= 1 to (n-1) do e.(i) <- (i,0); done; 
				 let k= ref(0) in
					while !k<>n do
						let t = distance_min e in 
						let u= snd(fst(t)) in
						let v= fst(fst(t)) in                          e.(v) <- (u,snd(t)+snd(e(u)));                           
 k:= v; 
				done; let x= ref(n-1) in
						while !x<>0 do 
							let w= fst(e.(!x)) in 
								l:= (w:: (!l)); x:= w;
						done; 
						(!l,snd(e.(n-1))) ;; 
 
let M = [|[|112;91;193;0;0;0;0;0;0|];
          [|0;0;107;0;0;0;0;0;0|];
          [|0;0;0;80;0;0;0;0;0|];
          [|107;0;0;0;217;109;0;0;0|];
          [|0;80;0;0;117;219;0;0;0|];
          [|0;0;217;117;0;126;159;200;0|];
          [|0;0;109;219;126;0;65;128;0|];
          [|0;0;0;0;159;65;0;114;121|];
          [|0;0;0;0;200;128;114;0;101|]|];;
 
dijkstra M;;
 
#distance_min : (int * int) vect -> (int * int) * int = <fun>
#dijkstra : 'a vect -> int list * int = <fun>
#Exception non rattrapée: Invalid_argument "vect_item"

(* L'algorithme dijkstra construit un tableau e de doublets e.(i)= (antécédent, temps de parcours du carrefour 0 au carrefour i). A chaque étape, on trouve le sommet s le plus proche de chacun des sommets déjà parcourus,ainsi que le noeud a qui le précède et la distance d les séparant (c'est le travail de la fonction distance_min) et on modifie alors e par e.(s) <- (a,d+snd(e.(a))) et on peut ainsi connaitre la distance parcourue depuis le carrefour 0 jusqu'au carrefour s (on est assuré que c'est la distance minimale) et on peut remonter d'antécédent en antécédent pour connaître le trajet. On s'arrête quand s est le dernier sommet.

Ici M représente la matrice d'un réseau routier simplifié de Paris à Marseille, de sorte que (M.(i)).(j) soit la durée de parcours en minute de i à j+1 (la ligne finale et la colonne initiale sont inutiles, car on ne retourne pas au point de départ et l'on ne part pas non plus du point d'arrivée !)*)

Encore merci si une bonne âme peut me répondre...

[prgasp77]

Salut,
je te donnerais volontiers un coup de main si d'une part tu modifiais ton message pour entourer ton code des balises [code] et d'autre part si tu nommais tes variables de manière un peu plus intelligibles (les d, t, i, j, g, u ...).

Pour information, la balise code génère un bloc de ce style (exemple extrait de la doc Objective Caml) :

Code OCaml :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#let h’ g = g ~y:2 ~x:3;;
val h’ : (y:int -> x:int -> ’a) -> ’a = <fun>
 
#h’ f;;
Error: This expression has type x:int -> y:int -> int
       but an expression was expected of type y:int -> x:int -> ’a
 
#let bump_it bump x =
   bump ~step:2 x;;
val bump_it : (step:int -> ’a -> ’b) -> ’a -> ’b = <fun>
 
#bump_it bump 1;;
Error: This expression has type ?step:int -> int -> int
       but an expression was expected of type step:int -> ’a -> ’b

Cordialement,

[HourofRagnarok]

Désolé, c'est le premier message que je poste sur ce forum et je ne suis pas habitué aux balises codes... Je reconnais que mon algorithme est indigeste, d'autant plus que l'indentation originelle est passée à la trappe quand j'ai tapé le message. Je dois débugger mon programme pour ce soir. Je vais mettre la balise code ocaml, même si le programme est en caml light en espérant que le rendu sera mieux.

Code ocaml :

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
 
 
let M = [|[|112;91;193;0;0;0;0;0;0|];
[|0;0;107;0;0;0;0;0;0|];
[|0;0;0;80;0;0;0;0;0|];
[|107;0;0;0;217;109;0;0;0|];
[|0;80;0;0;117;219;0;0;0|];
[|0;0;217;117;0;126;159;200;0|];
[|0;0;109;219;126;0;65;128;0|];
[|0;0;0;0;159;65;0;114;121|];
[|0;0;0;0;200;128;114;0;101|]|];;
 
let distance_min vecteur =
  let longueur = vect_length vecteur in
    let rec comparer2 = fun
        poids_min tronçon initial final when initial=longueur+1 -> tronçon
      | poids_min tronçon initial final when final=longueur+1  -> comparer2     poids_min tronçon (initial+1) 0
      | poids_min tronçon initial final -> let poids_tronçon= (M.(initial)).(final-1) in
                  let poids_chemin = poids_tronçon+snd(vecteur.(initial)) in
                       if fst(vecteur.(final))=final && fst(vecteur.(initial))<>initial && poids_tronçon<>0 &&( poids_chemin<poids_min or poids_min=0)
                         then comparer2 poids_chemin ((initial,final),poids_tronçon) initial (final+1)
                         else comparer2 poids_min tronçon initial (final+1) 
      in comparer2 0 ((0,0),0) 0 1;;
 
let dijkstra tableau =
  let plus_court_chemin= ref([]) in
    let longueur= (vect_length tableau) in
      let vecteur= make_vect longueur (0,0) in vecteur.(0)<- (-1,0) ;
        for indice= 1 to (longueur-1) do vecteur.(indice) <- (indice,0); done;
      let dernier_sommet= ref(0) in
        while !dernier_sommet<>longueur do
          let plus_court_tronçon = distance_min vecteur in
          let precedent,suivant = fst(plus_court_tronçon) in
                vecteur.(suivant) <- (precedent,(snd(plus_court_tronçon)+snd(vecteur.(precedent))));
               dernier_sommet:= suivant;
       done; 
     let antecedent= ref(longueur-1) in
        while !antecedent<>0 do
           let nouvel_antecedent= fst(vecteur.(!antecedent)) in
              plus_court_chemin:= (nouvel_antecedent::(!plus_court_chemin));antecedent:= nouvel_antecedent;
       done; 
      (!plus_court_chemin,snd(vecteur.(longueur-1))) ;;
 
dijkstra M;;

[gasche]

L'erreur "vect_item" n'est pas une erreur à la compilation (erreur de syntaxe ou de typage) mais une erreur à l'exécution : au cours de son exécution le programme rencontre une condition aberrante, et s'arrête. Ici l'erreur (indiquée par "vect_item") est que tu fais un accès hors d'un tableau : c'est-à-dire avec un indice négatif ou supérieure à (sa taille - 1) (pour rappel, les indices valides d'un tableau à N éléments sont entre 0 et N-1 inclus).

Il faut donc que tu regardes chacun de tes accès (en lecture ou écriture) à un tableau, c'est-à-dire les "foo.(bar)", et que tu te demandes si l'indice est bien valide. Après un rapide parcours de ton code je suspecte que le problème est avec M.(initial) (tu arrêtes initial à longueur+1 plutôt que longueur), mais je ne comprends pas le code dans son ensemble donc c'est peut-être autre chose, ou il y a peut-être plusieurs erreurs (j'ai juste regardé le premier accès à un tableau me tombant sous le nez).

Par ailleurs, sur la forme, ton utilisation de "fun / when" est à déconseiller. Globalement je pense que les débutants ne devraient *jamais* utiliser "when", ça les encourage à écrire des choses lourdes, peu lisibles, et plus propices aux bugs. Il vaut mieux écrire:

Code :

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

1
2
3
4
5
 
let rec comparer2 poids_min tronçon initial final =
  if initial = ...
  else if final = ....
  else ...

Enfin, j'ai beaucoup de mal à considérer ton code comme une implémentation de Dijsktra. Oui, l'idée de Dijsktra est de sélectionner, à chaque tour, le nœud le plus court du point de départ, mais la clé de l'algorithme est qu'on peut faire ça *efficacement*, en utilisant une structure de donnée adaptée (une file de priorité, où l'accès est logarithmique ou constant amorti). Dans ton algorithme j'ai l'impression que la sélection est quadratique, ou au moins linéaire. Du coup, c'est la même idée, mais ce n'est pas du tout la bonne complexité. Du coup, est-ce que c'est le bon algorithme... je ne sais pas.

Au cas où ça t'intéresse (par contre je ne sais pas si tu aurais le temps d'ici demain), le manuel ocaml contient une implémentation de file de priorité (donc c'est du OCaml au lieu de Caml Light, mais le code de "type 'a queue" à la fin de "extract" est aussi du Caml Light valide), ou sinon tu peux faire quelque chose au-dessus du module set de la bibliothèque standard Caml Light (mais il faut utiliser un ordre lexicographique (priorité * sommet), donc c'est un chouilla plus compliqué).

[HourofRagnarok]

Merci beaucoup pour ton aide. J'ai modifié mon erreur sur M.(initial) entre-temps mais effectivement ce n'est pas la seule erreur et de plus la complexité est trop grande... En fait il me faudrait clairement un algorithme déjà préparé. Puisqu'il s'agit d'un travail dans le cadre de mon école, il me faudrait un algorithme facile adapté au niveau prépa, que je puisse commenter. Je vais essayer de trouver un lien...
Merci pour vos efforts et votre patience.

[gasche]

Dijkstra n'est pas vraiment difficile à implémenter avec la bonne complexité, comme je l'ai dit c'est la même idée, il suffit d'avoir la bonne structure de donnée.

Je ne comprends pas exactement ce que tu cherches maintenant : tu dois faire une présentation orale sur un algorithme classique, c'est ça ? Le fait d'avoir un code fonctionnel est-il une obligation ?

[Cacophrene]

Bonsoir,

Je rejoins l'avis de gasche (bluestorm), si tu as une présentation orale à faire, l'essentiel est d'avoir compris le principe de l'algorithme, les idées mises en œuvre et les bénéfices qu'on peut en tirer.

Une implémentation fonctionnelle dans un langage donné, c'est un plus, certes intéressant car il te permet de mettre en pratique les concepts que tu as développés dans ta présentation, mais ce n'est peut-être pas indispensable.

Ou alors... veux-tu faire une démo interactive ou quelque chose dans ce genre ?

Cordialement,
Cacophrène