algo glouton

algo glouton - Algo - Programmation

Marsh Posté le 28-07-2003 à 18:08:37    

salut j'ai un algo a faire dont voici l'énoncé:
 
 
Vous désirez vous rendre en automobile de Montréal à Vancouver. Le réservoir de votre voiture vous permet de parcourir une distance D lorsqu?il est plein. Au cours du voyage vous rencontrerez k postes d?essences où vous pourriez faire le plein.  
 
Soient :
? di la distance pour aller du poste i?1 au poste i,  
? d1 la distance de Montréal au poste 1, et  
? dVancouver  la distance du poste k à Vancouver (on suppose di <= D et dVancouver <= D). (Donc il n?est pas possible de manquer d?essence)
? C = { c1, c2, ..., ck} l?ensemble des postes d?essence.
 
On désire faire le moins d?arrêts possibles.
 
1. Écrire un algorithme glouton qui détermine les postes où on devrait arrêter.  
 
2.  Si votre voiture a une autonomie de 600 km (D = 600km)
 
Soit  10 postes d?essences C1 à C10.
 
En appliquant l?algorithme que vous avez écrit, pour voyager du point A au point B, indiquer les postes d?essences où vous arrêterez. (Nombre de poste d?essence  
minimal).  
 
je sais pas trop par où commencé... alors si vous avez une idée

Reply

Marsh Posté le 28-07-2003 à 18:08:37   

Reply

Marsh Posté le 28-07-2003 à 18:51:50    

Va voir du côté du voyageur de commerce. Tu dois pouvir résoudre ça en utilisant le backtracking il me semble


---------------
What if I were smiling and running into your arms? Would you see then what I see now?  
Reply

Marsh Posté le 28-07-2003 à 18:56:39    

Oh non c'est pas si simple. Il y a surement plusieurs routes possibles pour aller de A vers B
 
Sinon, pas besoin d'un algo pour faire ça.
 
Les distances sont sous quelles formes ? une matrice ?
 
 
EDIT : Merci à SirJeannot d'avoir effacé son message. Comme ça plus personne comprend le topic


Message édité par jagstang le 28-07-2003 à 19:00:46

---------------
What if I were smiling and running into your arms? Would you see then what I see now?  
Reply

Marsh Posté le 28-07-2003 à 18:57:59    

Si ça peut t'aider, un algo que j'ai fait il y a quelques temps. C'est avec une matrive de distances
 

Code :
  1. void voyageur(int **distance, int nbVilles)
  2.     {
  3.     // vecteur contenant l'ordre des villes
  4.     int *ordre = (int *) malloc((nbVilles+1) * sizeof(int)) ;
  6.     // vecteur de contrôle, pour savoir si on est déjà allé à cette ville
  7.     int *vc = (int *) malloc(nbVilles * sizeof(int)) ;
  9.     for (int i=0 ; i< nbVilles ; i++)
  10.         vc[i] = 1 ;
  12.     ordre[0] = 0 ; // ville de départ, 0
  14.     int distMin = 0xFFFFFFF ; // initialisé à grand, pour que le premier
  15.                               // résultat trouvé soit meilleur
  17.     _voyageur(distance, ordre, 1, 0, &distMin, nbVilles, vc) ;
  18.     }
  20. void _voyageur(int **distance, int *parcours, int index, int km, int *kmMin, int n, int *vc)
  21.     {
  22.     // optimisation, si on est déjà plu grand que le meilleur résultat, on sort
  23.     if (km >= *kmMin)
  24.         return ;
  26.     // on arrive à la dernière ville, il faut encore revenir au départ
  27.     if (index == n)
  28.         {
  29.         parcours[index] = 0 ;  // va à 0 ;
  31.         _voyageur(distance, parcours, index+1,
  32.                   km+distance[0][parcours[index-1]], kmMin, n, vc) ;
  33.         return ;
  34.         }
  36.     // fin, solution trouvée
  37.     if (index == n+1)
  38.         {
  39.         *kmMin = km ;               // on enregistre le nouveau meilleur résultat
  40.         cout << endl ;
  41.         cout << "solution : " ;
  42.         for (int i=0 ; i<n ; i++)
  43.             cout << parcours[i] << " " ;
  44.         cout << " --> km : " << km ;
  45.         return ;
  46.         }
  48.     for (int i=1 ; i<n ; i++)
  49.         {
  50.         parcours[index] = i ;   // on essaie d'aller à cette ville
  52.         if (vc[i])   // pas encore allé (vecteur de contrôle), si on peut
  53.             {
  54.             vc[i] = 0 ;
  56.             _voyageur(distance, parcours, index+1,
  57.                       km+distance[i][parcours[index-1]], kmMin, n, vc) ;
  59.             vc[i] = 1 ;  // backtracking ! on enlève le 0 !
  60.             }
  61.         }
  62.     }



---------------
What if I were smiling and running into your arms? Would you see then what I see now?  
Reply

Marsh Posté le 28-07-2003 à 19:39:16    

JagStang a écrit :

Oh non c'est pas si simple. Il y a surement plusieurs routes possibles pour aller de A vers B
 
Sinon, pas besoin d'un algo pour faire ça.
 
Les distances sont sous quelles formes ? une matrice ?
 
 
EDIT : Merci à SirJeannot d'avoir effacé son message. Comme ça plus personne comprend le topic


 
en effet c une matrice...
 

Code :
  1. A C1 550
  2. C1 C2 100
  3. C2 C3 225
  4. C3 C4 300
  5. C4 C5 100
  6. C5 C6 50
  7. C6 C7 75
  8. C7 C8 100
  9. C8 C9 300
  10. C9 C10 175
  11. C10 B 400


 
voici mon algo:

Code :
  1. autonomie = 600
  2. ptot =  0
  3. tant i < 11
  4.   si (ptot + di < Auto) et (ptot + di+1 < autonomie)
  5.     Arret[i]= ci
  6.     ptot = ptot+di
  7.   else
  8.     ptot=0
  9.   increment i


 
mais je suis pas certain que c du glouton..


Message édité par nabrouska le 28-07-2003 à 19:47:31
Reply

Marsh Posté le 28-07-2003 à 23:42:34    

J'utilise l'algo Glouton dans Ignition ( http://www.katarncorp.com/?ignition ) mais mon prof d'IA m'a conseillé de regarder CA : http://www.nada.kth.se/~viggo/wwwc [...] de160.html qui à l'air plus intéressant.

Reply

Marsh Posté le 29-07-2003 à 00:31:08    

>> nabrouska  
 
Donne moi ton mail en privé
 
J'ai un projet que j'ai fait qui utilise 3 méthodes
 
Recherche heuristique par la methode : ville la plus proche
Recherche heuristique par la methode : meilleure insertion
Recherche backtracking (tres long.........)
 
 


---------------
What if I were smiling and running into your arms? Would you see then what I see now?  
Reply

Marsh Posté le 29-07-2003 à 09:42:48    

contenu de mon message effacé qui était le 3e [:dawa] et qui était une bétise
 
"ben tu vois si ta titine est capable d'aller à la station suivante étant à une station"
mais bon, je n'avais pas vu le pb du backtracking  :cry:  
 
enfin ajouter du backtrackingà ce genre de raisonnement n'est pas très difficile non plus  :whistle:

Reply

Marsh Posté le 30-07-2003 à 23:09:45    

c koi un algo glouton ? :D

Reply

Marsh Posté le 30-07-2003 à 23:14:43    

Euh... Juste un truc... Je vous vois tous partir dans un délire de graph... Seulement, si on lit l'énoncé, il y a une chose capitale que vous n'avez visiblement pas remarqué :
 
Au cours du voyage vous rencontrerez k postes d?essences où vous pourriez faire le plein.
 
Les postes d'essence sont donc pas disséminés géographiquement n'importe comment, ils sont ordonnés sur un trajet déjà calculé. Il s'agit dinc ni plus ni moins d'un tableau à une seule dimension... Pas besoin de partir dans des algos genre le voyageur de commerce... L'algo de nabrouska résoud parfaitement le problème en toute simplicité (il est améliorable niveau perfs - puisque les postes sont répartis à distance constante sur le parcours, on peut calculer le nombre de postes qu'on peut sauter avant d'atteindre D, histoire de ne pas les passer chacun en revue, mais sauter x postes à chaque fois -, mais pas au niveau algo... Enfin... Faut le corriger, parcequ'il est complètement faux, mais l'approche logique est la bonne)
Par contre, c'est trop simple, je doute que ce soit ça un algo glouton... C quoi au juste ce truc ?


Message édité par MagicBuzz le 30-07-2003 à 23:16:03
Reply

Marsh Posté le 30-07-2003 à 23:14:43   

Reply

Marsh Posté le 30-07-2003 à 23:26:29    

Perso, je ferais : (pseudo code VB)
 
saut = int(D / di)
numPoste = 0
nbArret = 0
 
// On vérifie que D < d1 + d[1..k] + dVancouver, çe serait con de s'arrêter pour rien ;)
if D < d1 + 10 * di + dVancouver
 
  // Premier tronçon : on prends en compte d1, la distance initiale
  numPoste = int((D - d1) / di)
  dist = d1 + numPoste * di
 
  // Ensuite : saut de poste en poste
  do while dist < (d1 + 10 * di + dVancouver) - D
     numPoste = numPoste + saut
     dist = dist + di * saut
     nbArret = nbArret + 1
  loop
 
End if
 
// Maintenant, nbArret contient le nombre d'arrêts, on peut sauvegarder les numPoste si on veut la liste des postes où on s'est arrêté.
 
PS: attention, dans mon cas, les postes sont nommés de 0 à k - 1
 
Mais bon, de toute façon, ça doit pas être un glouton :D
 
Par contre, je doute qu'on puisse faire plus optimisé... Doit y avoir quand même moyen de se passer du while, mais je vois pas trop comment... mais certainement tout à fait faisable... C'est la seule optimisation possible.


Message édité par MagicBuzz le 30-07-2003 à 23:36:25
Reply

Marsh Posté le 30-07-2003 à 23:40:43    

Tout compte fait, si on veut conserver la liste des postes d'arrêt, il faut inévitablement une boucle :)
 
Mais pour connaître le nombre d'arrêt, ça se fait les doigts dans le nez avec un seul if en fait, plus celui qui vérifie que D < la distance totale :D
 
 
Nombre d'arrêts : (je vous défie de trouver plus concis :D)
 

Code :
  1. if (D < d1 + 10 * di + dVancouver)
  2. {
  3.    // On va devoir s'arrêter
  4.    if (D < dVancouver + di * (10 - int((D - d1) / di)))
  5.    {
  6.       // Une fois arrêté une première fois, on va devoir s'arrêter dans un autre poste
  7.       nbA = 1 + int(di * (10 - int((D - d1) / di)) / D);
  8.       if (D < (dVancouver + di * (10 - int((D - d1) / di))) - (int(di * (10 - int((D - d1) / di)) / D) * di))
  9.       {
  10.          // Pas de pot, le dernier arrêt était trop loin de Vancouver, on va devoir s'arrêter une dernière fois, au dernier poste par exemple
  11.          nbA++;
  12.       }
  13.    }
  14.    else
  15.    {
  16.       // On ne fait qu'un arrêt
  17.       nbA = 1;
  18.    }
  19. }
  20. else
  21. {
  22.    // Ben on n'a pas besoin de s'arrêter...
  23.    nbArrets = 0;
  24. }


 
 
C trop facile comme problème :D Tout compte fait, il fallait tout de même 3 if :)
Pour rajouter les numéros des postes où on s'arrête, c'est pas très compliqué, il faut rajouter le pemier arrêt et le dernier (s'il existe) et faire un petit for pour ceux du parcours poste à poste.
 
 
M'enfin c'est tout faut, chais pas ce qu'est un algo glouton et tout le monde pionce :o


Message édité par MagicBuzz le 31-07-2003 à 00:04:53
Reply

Marsh Posté le 31-07-2003 à 02:10:11    

Je t'ai envoyé mon prog.
 
Pour ceux que ça intéresse, message privé svp pour me donner le mail


---------------
What if I were smiling and running into your arms? Would you see then what I see now?  
Reply

Marsh Posté le 31-07-2003 à 14:39:19    

Code :
  1. void voyageur(float **distance, int nbVilles)
  2.     {
  3.     // vecteur contenant l'ordre des villes
  4.     int *ordre = (int *) malloc((nbVilles+1) * sizeof(int)) ;
  6.     // vecteur de contrôle, pour savoir si on est déjà allé à cette ville
  7.     int *vc = (int *) malloc(nbVilles * sizeof(int)) ;
  9.     for (int i=0 ; i< nbVilles ; i++)
  10.         vc[i] = 1 ;
  12.     ordre[0] = 0 ; // ville de départ, 0
  14.     int distMin = 0xFFFFFFF ; // initialisé à grand, pour que le premier
  15.                               // résultat trouvé soit meilleur
  17.     _voyageur(distance, ordre, 1, 0, &distMin, nbVilles, vc) ;
  18.     }
  22. void _voyageur(float **distance, int *parcours, int index, int km, int *kmMin, int n, int *vc)
  23.     {
  24.     // optimisation, si on est déjà plu grand que le meilleur résultat, on sort
  25.     if (km >= *kmMin)
  26.         return ;
  28.     // on arrive à la dernière ville, il faut encore revenir au départ
  29.     if (index == n)
  30.         {
  31.         parcours[index] = 0 ;  // va à 0 ;
  33.         _voyageur(distance, parcours, index+1,
  34.                   km+distance[0][parcours[index-1]], kmMin, n, vc) ;
  35.         return ;
  36.         }
  38.     // fin, solution trouvée
  39.     if (index == n+1)
  40.         {
  41.         *kmMin = km ;               // on enregistre le nouveau meilleur résultat
  42.         cout << endl ;
  43.         cout << "solution : " ;
  44.         for (int i=0 ; i<n ; i++)
  45.             cout << parcours[i] << " " ;
  46.         cout << " --> km : " << km ;
  47.         return ;
  48.         }
  50.     for (int i=1 ; i<n ; i++)
  51.         {
  52.         parcours[index] = i ;   // on essaie d'aller à cette ville
  54.         if (vc[i])   // pas encore allé (vecteur de contrôle), si on peut
  55.             {
  56.             vc[i] = 0 ;
  58.             _voyageur(distance, parcours, index+1,
  59.                       km+distance[i][parcours[index-1]], kmMin, n, vc) ;
  61.             vc[i] = 1 ;  // backtracking ! on enlève le 0 !
  62.             }
  63.         }
  64.     }


 


---------------
What if I were smiling and running into your arms? Would you see then what I see now?  
Reply

Marsh Posté le 31-07-2003 à 15:49:55    

JagStang a écrit :

Je t'ai envoyé mon prog.
 
Pour ceux que ça intéresse, message privé svp pour me donner le mail


Je vois toujours pas le rapport entre ton prog et l'énnoncé...

Reply

Marsh Posté le 31-07-2003 à 17:51:03    

:D


---------------
What if I were smiling and running into your arms? Would you see then what I see now?  
Reply

Marsh Posté le 31-07-2003 à 20:02:10    

:p ;)

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed