Algo glouton basé sur la programmation dynamique

Soyez le premier à donner votre avis sur cette source.

Snippet vu 7 981 fois - Téléchargée 33 fois

Contenu du snippet

La programmation dynamique permet de résoudre des problème d'optimisation mais il s'agit de méthodes assez lourde. Il existe donc les algo gloutons plus rapide. Un algo glouton fait un choix localement optimal en esperant que ce choix conduise vers une solution globalement optimale.
Dans l'exemple qui suit nous traitons le problème du choix d'activités optimale et qui ne se chevauche pas dans le temps.
Ex: Act1 Act2 Act3
Heure Debut= 0 2 5
Heure Fin = 4 5 7
Ici la solution est Act1 suivie d'activité Act3 car ne se chevauche pas et est optimal pour ce problème bien que l'exemple est vraiment très simple.

Source / Exemple :


#include <stdio.h>

int tabRes[11]; // tableau contenant les activités résultats
int AlgoGlouton(int *s,int *f, int i, int n,int nb);

int main (void)
{
	// tableau contenant les heures de début et fin d'activité
	int s[12]={0,1,3,0,5,3,5,6,8,8,2,12};
	int f[12]={0,4,5,6,7,8,9,10,11,12,13,14};

	AlgoGlouton(s,f,0,11,0);	
	

	
	return 0L;
}

// Méthode de l'algo glouton
// Entrée= s etant un tableau contenant les heures de début de l'activité
//         f etant un tableau contenant les heures de fin
//         i,n st les indices définissant le sous problème à traiter S(i,n+1)
//         nb est l'indice permettant d'insérer dans le tab résultat tabRes l'activité choisit
// Sortie= 0 ou 1 non utilisé dans cet algo
int AlgoGlouton(int *s,int *f, int i, int n,int nb)
{
	int m = i+1;

	while( (m<=n) && (s[m] < f[i]) )
		m++;
	
	if( m <= n )
	{
		tabRes[nb]=m;
		AlgoGlouton(s,f,m,n,nb+1);
		return 1;
	}
	else
		return 0;

}

Conclusion :


Cet algo est bien evidemment pas de moi.... Si vous voulez d'avantage d'explication, il est tiré du bouquin: "Intro à l'algo"... Livre très bien fait pour comprendre tous ces algo d'optimisation en particulier.
Cette source a juste pour but de faire découvrir cette partie de l'algo aux personnes ne connaissant pas l'optimisation.
<<-- H@ldwin -->>

A voir également

Ajouter un commentaire

Commentaires

NicoProg
Messages postés
26
Date d'inscription
lundi 2 avril 2001
Statut
Membre
Dernière intervention
28 mars 2005
-
Niveau expert .... ca me semble un peu abuser quand même :).


mais sinon, c'est très bien, et un peu de récursivité, ca fait pas de mal :-D
eldered
Messages postés
231
Date d'inscription
vendredi 21 mars 2003
Statut
Membre
Dernière intervention
22 avril 2007
-
Hum, peux tu commenter un peut la source, je n'y comprend pas grand chose, et pourrait tu expliquer le sens de chevaucher ? Merci ! ++
rawya86
Messages postés
1
Date d'inscription
vendredi 22 mai 2009
Statut
Membre
Dernière intervention
22 mai 2009
-
salut! c tré urgent j veu bien un code concernant
le dimensionnement ou l'acheminement optimal dans un réseau à commutation par paquet ou par circuit

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.