Algo glouton basé sur la programmation dynamique

Commenter

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

S'inscrire maintenant

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.

Du même auteur (Haldwin)