SetNor
Messages postés1Date d'inscriptiondimanche 4 mai 2008StatutMembreDernière intervention 4 mai 2008
-
4 mai 2008 à 22:30
Éfenwël -
10 mai 2011 à 14:20
Bonjour,
J'ai un petit problème en ce qui concerne le language de programmation Ocaml (objective Caml), c'est à dire que j'ai quelques fonctions à faire, mais il m'est impossible de les réaliser, je n'arrive pas à en trouver la solution.
Le but en quelque sorte étant de créer un GPS qui calcul la distance entre deux villes en passant par d'autres villes.
Voici les fonctions ci dessous (je vous met le projet en intégralité):
Je tiens à préciser que la 3e fonction principale, la 2e partie du projet ainsi que la toute dernière fonctions, m'est très difficile de les réaliser, je n'arrive pas à trouver la solution, merci de m'aider au plus vite^^:
(**************************************************************************************)
(**************************************************************************************)
(**** STRUCTURES DE DONNEES : EXEMPLE DE DONNEES SUR DES VILLES DU CANADA *******)
(**************************************************************************************)
(**************************************************************************************)
(* Un tableau de distances se lit de la manière suivante : la première ligne représente les
distances relatives à la première ville (Ashuapmushan dans notre cas), la deuxième concerne
la seconde ville (Toronto) etc. Les colonnes représente les distances relatives aux villes mais
en sens inverse ! Ainsi la première colonne (le premier élément des listes) donne les distances
relativement à la dernière ville (ici Bonaventure), la seconde colonne l'avant dernière
ville (Carleton) etc.
Ainsi la distance entre Ashuapmushan et Toronto est de 1098 (première ligne, dernière colonne). La
distance entre Ashuapmushan et Charlevoix est 430 (troisième colonne première ligne). etc. *)
type carte = ville list * tableau_distances;;
(* une carte (lv,td) est une liste de ville (lv) parmi les villes de villes_canada
plus le tableau des distances entre les villes de (lv) donné par rapport à l'ordre
de la liste lv.
On impose la précondition que la liste des villes ne doit pas être vide.
*)
let (carte_canada : carte ) = (villes_canada,distances_canada);;
(* Carte regroupant l'ensemble des villes et des distances *)
type graphe_distances = (ville * distance * ville) list;;
(* La notion de graphe comme liste d'arrête sans répétition
à partir d'une carte est définie. A partir du graphe on pourra créer l'arbre de
recouvrement minimal : il faut trier le graphe de distance correspondant
puis de prendre les arrêtes telles que les deux sommets n'apparaissent pas dans
la liste des sommets déjà piochés.*)
(**************************************************************************************)
(**************************************************************************************)
(************* PREMIERE PARTIE DU PROJET : MANIPULATION DES DONNEES ***************)
(**************************************************************************************)
(**************************************************************************************)
+++
(*Cette fonction compte le nombre de Villes dans la liste*)
let rec(nbv: carte -> int) = function
c -> let (a::lv,td) = c in
if (lv=[]) then 1
else nbv(lv,td)+1;;
+++
(*Cette fonction donne un numéro aux villes et leur donne un numéro dans l'ordre croissant*)
(*Précondition: la liste est non vide*)
let rec(cvoc: ville*carte->int) = function
(e,c)-> let (a::lv,td) = c in
if(e=a) then 1
else cvoc(e,(lv,td))+1;;
+++
(*Cette fonction donne un numéro aux villes et leur donne un numéro dans l'ordre décroissant*)
(*Précondition: la liste est non vide*)
let rec(cvod: ville*carte*carte->int) = function
(e,c,c_memoire)-> let (a::lv,td) = c in
if(e=a) then nbv(c_memoire)
else cvod(e,(lv,td),c_memoire)-1;;
+++
(*Cette fonction prends le nième élément de la liste de liste d'éléments *)
(*Précondition: la liste ne doit pas être vide*)
let rec(neul: int*carte-> 'elt list) = function
(n,c)-> let (lv,a::td) = c in
if(n=1) then a
else neul(n-1,(lv,td));;
+++
(*Cette fonction prends le nième élément de la liste d'éléments *)
(*Précondition: la liste ne doit pas être vide*)
let rec(neul2: int*'elt list -> 'elt) = function
(n,a::l)-> if(n=1) then a
else neul2(n-1,l);;
========================= 1e fonction principale ======
(* dist_entre_villes(v1,v2,c) = distance entre la ville v1 et v2 selon
le tableau des distances défini dans la carte c.
Précondition : les deux villes doivent être distinctes et doivent faire
parties de la carte.*)
let (dist_entre_villes : ville * ville * carte * carte -> int) = function
(v1,v2,c,c_memoire)-> if (cvoc(v1,c)+cvod(v2,c,c_memoire)>nbv(c)) then neul2(cvod(v1, c,c_memoire), neul(cvoc(v2,c), c))
else neul2(cvod(v2,c,c_memoire), neul(cvoc(v1,c), c));;
========================= 2e fonction principale =================================
(* graphe_distances_of_carte(c) = gd, gd est le graphe de distances représentants
la carte c. gd ne contient qu'une seule arrête entre deux villes. Ainsi
(va,d,vb) signifie que le chemin entre a et b ou entre b et a est de distance d.*)
let rec (inter: ville list -> graphe_distances ) = function
|m::ms -> let rec (inter_deux: ville list-> graphe_distances) = function
|[] -> []
|x::xs -> (m, dist_entre_villes(m,x,carte_canada,carte_canada),x)::inter_deux(xs) in
inter_deux(ms);;
let rec (graphe_distances_of_carte : carte -> graphe_distances) = function
([],d)-> []
|(e::es,d) -> inter(e::es)@graphe_distances_of_carte(es,d);;
========================= 3e fonction principale =============
let (sous_carte : ville list * carte -> carte) = function
(* sous_carte(lv,c) = la carte contenant lv comme liste de ville
et le tableau des distances correspondant en utilisant la carte c
comme référence. Par exemple sous_carte([Ashuapmushuan ; Toronto],carte_canada)
donnera comme résultat : ([Ashuapmushuan ; Toronto],1098).
Précondition : la liste lv doit être inclue dans la liste des villes de c. *)
...
(**************************************************************************************)
(**************************************************************************************)
(************* SECONDE PARTIE DU PROJET : CALUL DU CIRCUIT MINIMAL ***************)
(**************************************************************************************)
(**************************************************************************************)
let (construction_arbre : carte -> graphe_distances) = function
(*construction_arbre(c)= a, a représente un arbre couvrant de poids
minimal associé au graphe défini par c. *)
...
(**************************************************************************************)
(**************************************************************************************)
(*** FONCTIONS FOURNIES POUR LE CALCUL DU CYCLE EN UTILISANT L'ARBRE COUVRANT *****)
(**************************************************************************************)
(**************************************************************************************)
let rec(premier_non_deja_visite : ville list * ville list -> ville* bool )= function
(* premier_non_deja_visite(l,m)) = (v,b). v est le premier element de l qui n'est pas dans m
si possible (en ce cas b est vrai). sinon s'il n'existe pas déléments de l qui ne sont pas
dans m, v est n'importe quelle ville et b est faux.
La liste m représente les villes déjà visitées.
POUR FONCTIONNER Il FAUT REALISER LA FONCTION est_dans dont la spécification est la suivante :
Profil : est_dans : 'a * 'a list -> bool
Sémantique : est_dans(e,l) est vrai si et seulement si e est dans l.*)
([],m) -> (Toronto,false) (* on répond n'importe quelle ville, cela n'a pas d'importance*)
| (v::l,m) -> if (not (est_dans(v,m))) then (v,true)
else premier_non_deja_visite(l,m);;
let rec(enleve_arrete: ville * ville * graphe_distances -> graphe_distances) = function
(* enleve_arrete(vdep,var,l) est la liste l privée de l'arrête (vdep,d,var) si cette arrête
est dans l, l sinon.*)
(vdep,var,[]) -> []
| (vdep,var,(v,d,w)::l) -> if ((v=vdep) && (w=var)) then l
else (v,d,w)::enleve_arrete(vdep,var,l);;
let rec(premiere_arrete_libre : ville * graphe_distances -> ville )= function
(* premier_arrete_libre (vd,gd) = w avec (v,d,w) dans gd et vd=v.
Precondition : gd contient au moins une arrête contenant vd comme origine. *)
(vd,(v,d,w)::reste) -> if vd=v then w else premiere_arrete_libre(vd,reste);;
let rec (make_circuit : ville * graphe_distances * ville list -> ville list) = function
(* make_circuit(v,gd,lv)=l, l est la liste d'un circuit correspondant à l'arbre gd. Le circuit
part de la ville v, le graphe de distance est représenté par gd, les villes déjà visitées
sont dans lv.
Précondition : gd est un graphe représentant un arbre où chaque arrête est donnée dans les
deux sens.
POUR FONCTIONNER Il FAUT REALISER LA FONCTION voisins dont la spécification est la suivante :
Profil : voisins : ville * graphes_distances -> ville list
Sémantique : voisins (v,gd) = l, l est la liste des villes reliées à
v par une arrête c'est à dire tous les l tels que (l,d,v) ou (v,d,l)
soit dans gd.. *)
(vdep,[],l) -> []
| (vdep,gd,l) -> let vsns=voisins(vdep,gd) in
let (next_ville,b)=premier_non_deja_visite(vsns,l) in
let next_l= if (est_dans(vdep,l)) then l else vdep::l in
if b then let gd_rec=enleve_arrete(vdep,next_ville,gd)
in vdep::make_circuit(next_ville,gd_rec,next_l)
else let new_next_ville=premiere_arrete_libre(vdep,gd) in
let gd_rec=enleve_arrete(vdep,new_next_ville,gd) in
vdep::make_circuit(new_next_ville,gd_rec,next_l);;
let (circuit : graphe_distances -> ville list) = function
(* circuit(gd)=lv, lv est une liste de ville qui forme un cricuit étant donné un arbre
gd représenté sous forme de graphe_distances.
Précondition : le graphe donné en paramètre doit être un arbre avec
une arrête dans chaque direction entre chaque villes ce qui fait que pour relier va à vb on
a dans la liste (mais pas forcément de manière contigüe) (va,d,vb) et (vb,a,va).
Il faut aussi que le graphe donné soit non vide *)
(v,d,w)::gd -> make_circuit(v,gd,[]);;
(* Vous pouvez tester cette fonction sur la donnée suivante
[(Toronto,0,Québec);(Québec,0,Toronto);(Québec,0,Mauricie);(Mauricie,0,Québec);
(Toronto,0,Ottawa);(Ottawa,0,Toronto);(Cartier,0,Québec);(Québec,0,Cartier)] *)
(**************************************************************************************)
(**************************************************************************************)
(*************** FONCTION PRINCIPALE DU PROJET *******************)
(**************************************************************************************)
(**************************************************************************************)
let (circuit_voyageur_commerce : ville list * carte -> ville list) = function
(* circuit_voyageur_commerce(lv,c) = res, où res est un circuit calculé par l'algorithme
de Christofides contenant toutes les villes de lv selon la carte c.
Précondition : toues les villes contenues dans lv doivent aussi être dans c*)
...
Salut, je ne connais pas Dijsktra, et c'est quelque chose que je dois présenter sous Ocaml, donc je dois faire cela uniquement sur Ocaml ^^, pour certains ça doit paraitre très facile, car malgré la longueur c'est plutôt basique en fin de compte, mais pour moi j'ai vraiment du mal.
Bonjour.
Tu annonce GPS mais ta dernière fonction s'appelle tout de même "voyageur_de_commerce"... Le premier est facile à faire à partir de l'algorithme de Dijkstra, le second est NP-complet... :/
Je te conseille de commencer par trois choses :
1 - tes données sont fixes dans le programme, donc utilise des tableaux, pas des listes !
2 - indente ton code de manière un peu plus lisible (et concise ?), ça pourrait donner envie de le lire ;)
3 - puisqu'il semble en fait que tu veuille appliquer un algorithme déjà existant, que tu n'arrive simplement pas à implémenter, commence par l'appliquer à la main sur de petites structures, ça te permettras de mieux l'appréhender.
