Algo

algo glouton

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : algo glouton

nabrouska

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

Publicité

jagstang

Pa Capona ಠ_ಠ

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?

jagstang

Pa Capona ಠ_ಠ

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?

jagstang

Pa Capona ಠ_ಠ

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

Code :

void voyageur(int **distance, int nbVilles)
{
// vecteur contenant l'ordre des villes
int *ordre = (int *) malloc((nbVilles+1) * sizeof(int)) ;
// vecteur de contrôle, pour savoir si on est déjà allé à cette ville
int *vc = (int *) malloc(nbVilles * sizeof(int)) ;
for (int i=0 ; i< nbVilles ; i++)
vc[i] = 1 ;
ordre[0] = 0 ; // ville de départ, 0
int distMin = 0xFFFFFFF ; // initialisé à grand, pour que le premier
// résultat trouvé soit meilleur
_voyageur(distance, ordre, 1, 0, &distMin, nbVilles, vc) ;
}
void _voyageur(int **distance, int *parcours, int index, int km, int *kmMin, int n, int *vc)
{
// optimisation, si on est déjà plu grand que le meilleur résultat, on sort
if (km >= *kmMin)
return ;
// on arrive à la dernière ville, il faut encore revenir au départ
if (index == n)
{
parcours[index] = 0 ; // va à 0 ;
_voyageur(distance, parcours, index+1,
km+distance[0][parcours[index-1]], kmMin, n, vc) ;
return ;
}
// fin, solution trouvée
if (index == n+1)
{
*kmMin = km ; // on enregistre le nouveau meilleur résultat
cout << endl ;
cout << "solution : " ;
for (int i=0 ; i<n ; i++)
cout << parcours[i] << " " ;
cout << " --> km : " << km ;
return ;
}
for (int i=1 ; i<n ; i++)
{
parcours[index] = i ; // on essaie d'aller à cette ville
if (vc[i]) // pas encore allé (vecteur de contrôle), si on peut
{
vc[i] = 0 ;
_voyageur(distance, parcours, index+1,
km+distance[i][parcours[index-1]], kmMin, n, vc) ;
vc[i] = 1 ; // backtracking ! on enlève le 0 !
}
}
}

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

nabrouska

JagStang a écrit :

en effet c une matrice...

Code :

A C1 550
C1 C2 100
C2 C3 225
C3 C4 300
C4 C5 100
C5 C6 50
C6 C7 75
C7 C8 100
C8 C9 300
C9 C10 175
C10 B 400

voici mon algo:

Code :

autonomie = 600
ptot = 0
tant i < 11
si (ptot + di < Auto) et (ptot + di+1 < autonomie)
Arret[i]= ci
ptot = ptot+di
else
ptot=0
increment i

mais je suis pas certain que c du glouton..

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

Kyle_Katarn

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.

jagstang

Pa Capona ಠ_ಠ

>> 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?

Profil supprimé

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:

MagicBuzz

c koi un algo glouton ?

MagicBuzz

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

Publicité

MagicBuzz

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

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

MagicBuzz

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

Nombre d'arrêts : (je vous défie de trouver plus concis )

Code :

if (D < d1 + 10 * di + dVancouver)
{
// On va devoir s'arrêter
if (D < dVancouver + di * (10 - int((D - d1) / di)))
{
// Une fois arrêté une première fois, on va devoir s'arrêter dans un autre poste
nbA = 1 + int(di * (10 - int((D - d1) / di)) / D);
if (D < (dVancouver + di * (10 - int((D - d1) / di))) - (int(di * (10 - int((D - d1) / di)) / D) * di))
{
// 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
nbA++;
}
}
else
{
// On ne fait qu'un arrêt
nbA = 1;
}
}
else
{
// Ben on n'a pas besoin de s'arrêter...
nbArrets = 0;
}

C trop facile comme problème 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

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

jagstang

Pa Capona ಠ_ಠ

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?

jagstang

Pa Capona ಠ_ಠ

Code :

void voyageur(float **distance, int nbVilles)
{
// vecteur contenant l'ordre des villes
int *ordre = (int *) malloc((nbVilles+1) * sizeof(int)) ;
// vecteur de contrôle, pour savoir si on est déjà allé à cette ville
int *vc = (int *) malloc(nbVilles * sizeof(int)) ;
for (int i=0 ; i< nbVilles ; i++)
vc[i] = 1 ;
ordre[0] = 0 ; // ville de départ, 0
int distMin = 0xFFFFFFF ; // initialisé à grand, pour que le premier
// résultat trouvé soit meilleur
_voyageur(distance, ordre, 1, 0, &distMin, nbVilles, vc) ;
}
void _voyageur(float **distance, int *parcours, int index, int km, int *kmMin, int n, int *vc)
{
// optimisation, si on est déjà plu grand que le meilleur résultat, on sort
if (km >= *kmMin)
return ;
// on arrive à la dernière ville, il faut encore revenir au départ
if (index == n)
{
parcours[index] = 0 ; // va à 0 ;
_voyageur(distance, parcours, index+1,
km+distance[0][parcours[index-1]], kmMin, n, vc) ;
return ;
}
// fin, solution trouvée
if (index == n+1)
{
*kmMin = km ; // on enregistre le nouveau meilleur résultat
cout << endl ;
cout << "solution : " ;
for (int i=0 ; i<n ; i++)
cout << parcours[i] << " " ;
cout << " --> km : " << km ;
return ;
}
for (int i=1 ; i<n ; i++)
{
parcours[index] = i ; // on essaie d'aller à cette ville
if (vc[i]) // pas encore allé (vecteur de contrôle), si on peut
{
vc[i] = 0 ;
_voyageur(distance, parcours, index+1,
km+distance[i][parcours[index-1]], kmMin, n, vc) ;
vc[i] = 1 ; // backtracking ! on enlève le 0 !
}
}
}

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

MagicBuzz

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é...

jagstang

Pa Capona ಠ_ಠ

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

MagicBuzz

FORUM HardWare.fr

Programmation

Algo

algo glouton

Sujets relatifs
Question methode c++ (algo)	[ASP/Algo] Nombre en Français
[RESOLU][ALGO]Comment fonctionne le tracking par mail ?	Algo de Hashage/Signature
changer un entier en double ? ou bien mon algo est mauvais ...help	algo de graph
Compilation et debogage de module linux, aux pros de l'algo et systeme	[VBA] [ALGO] Découper une chaine de charactères d'après séparateur
Algo de génération de dégrade [RESOLU]	[Java/Algo] Reconnaitre un disque dans un image
Plus de sujets relatifs à : algo glouton

Page générée en 0.123 secondes