Démonstration d'un algo glouton

**touftouf57** · 22/09/2010, 00h13

Bonjour,

Je suis mon cours, mais je ne pige pas la façon dont est prouvé que mon algo glouton est optimal.

Si je galère c'est que j'ai repris mes études, que j'ai quitté il y a 10 ans. Et que tout est noté en langage mathématiques. La traduction est plutôt difficile.

Je planche sur l'algo du choix d'activité (qui est apparemment un grand classique)

Le principe que j'ai compris est de dire que:
- mon algo A={a1,....,an} n'est pas optimale donc
- il existe une solution O qui est différente de A et qui est optimale
- On recherche un indice i ou la solution de O diffère de A donc
- si A est inclus dans O cela signifie que p>n et que O={a1,....an,on+1,.......oq} mais si on+1 est compatible avec an alors notre algo l'aurait pris et donc sa longueur ne serait pas n. --> contradiction

Jusque là le principe de démonstration est-il juste?

C'est concernant la suite ou on doit montrer une contradiction pour une valeur inférieure à n, que j'ai du mal.

Est-ce que quelqu'un peut m'expliquer, de façon simple, la méthode de démonstration d'un algo glouton.

Merci d'avance

**CedricMocquillon** · 23/09/2010, 15h08

http://en.wikipedia.org/wiki/Greedoid Pour un début de réponse sur la classe de problème résolvable par algorithme glouton.

Sinon pour ta démonstration ça parait un poil flou dis comme ça mais sinon c'est un bon principe de raisonner par l'absurde pour prouver l'optimalité.

Sinon pour prouver que ton algo n'est pas optimal, tu peux aussi trouver un contre exemple

**touftouf57** · 23/09/2010, 22h51

Envoyé par gorgonite

un peu... on n'est pas sûr faites-mes-devoirs.com

Excuse moi gorgonite, mais as-tu vu l'age que j'ai? je ne cherche pas à ce que l'on fasse mes devoirs. Je les fais moi même, je bosse pour moi, et pas pour obtenir des bonnes notes pour satisfaire mes parents.
Tu mes dis google, et bien avant de poster j'ai tout de même cherché de mon coté. Je ne cherche pas la solution à un problème, mais la méthode, par l'absurde, pour prouver que l'algo donnée est optimal ou pas.

Je vais avoir un partiel d'ici une semaine. Et il y a de forte chance que l'on nous demande de démontrer qu'un algo glouton donné est optimal (ou pas).

Donc ce n'est pas faites-mes-devoirs.com que je recherche, mais un conseil/une méthodologie de personnes expérimentées.

**pseudocode** · 24/09/2010, 12h01

Envoyé par touftouf57

Je vais avoir un partiel d'ici une semaine. Et il y a de forte chance que l'on nous demande de démontrer qu'un algo glouton donné est optimal (ou pas).

Donc ce n'est pas faites-mes-devoirs.com que je recherche, mais un conseil/une méthodologie de personnes expérimentées.

Un algo glouton (greedy) est optimal pour un problème si ce problème à une substructure optimale.

C'est à dire le prochain "meilleur choix" pour le problème global est le "meilleur choix" pour le sous-problème actuel.

**CedricMocquillon** · 24/09/2010, 12h38

gorgonite, il ne faut pas que tu te focalises uniquement sur le problème de rendre la monnaie, l'algorithme glouton est optimal pour un certain nombre de problèmes (cf. la cherche d'un plus court chemin dans un graphe quelconque avec des arcs de longeurs positives ou dans un graphe sans cycle avec longeurs quelconques avec l'algorithme de Dijkstra)

Comme l'a indiqué pseudocode un algorithme glouton est optimal si le problème peut être décomposé en sous-problèmes pour lesquels l'algorithme glouton est optimal. D'un point de vue plus théorique la matrice de contraintes de ces problèmes est un greedoïde (de même que l'on peut prouver qu'un algorithme de flot est optimal pour les problèmes dont la matrice de contrainte est totalement unimodulaire)

Au niveau de la définition de l'optimalité d'un algorithme, il est communément admis que l'on parle d'algorithme optimal si l'algorithme trouve pour toute instance donnée d'un problème la solution optimale au sens de la fonction objectif. Un algorithme est dit ensuite polynomial si sa complexité temporelle et spatiale sont bornée par un polynôme dépendant du nombre de variables et contraintes du problème.

On connait quelque fois des bornes inférieures sur la complexité temporelle d'un algorithme (par exemple O(n²) pour l'inversion de matrice) et si notre algorithme a une complexité égale à cette borne inférieure on sait que l'on ne pourra pas trouver de meilleur algorithme au sens de la complexité temporelle. Cependant ça reste des cas assez rare (je n'ai pas souvenir d'algorithme dont la complexité temporelle ait été démontrée optimale)

Pour en revenir au problème de touftouf57, trois alternatives s'offrent à lui:
1) démontrer que la matrice de contraintes est un greedoid (je ne connait pas précisément les proriétés à démontrer mais je pense pas que ce soit le plus facile à faire)
2) démontrer que son problème peut être décomposé en sous-problèmes pour lesquels l'algo glouton est optimal
3) démontrer par l'absurde que l'algorithme est optimal

Dans tout les cas, je te conseil touftouf57 de regarder la démonstration de l'optimalité de l'algorithme de Dijkstra, ça pourra peut être t'inspirer

Edit: J'ai oublié la principale méthode employée; en fait c'est assez rarer d'inventer un nouvel algorithme, la plupart du temps lorsqu'on est confronté à un nouveau problème, pour déterminer sa classe de complexité (Polynomial, NP-difficile au sens faible, NP-difficile au sens fort) on utilise la technique des réductions polynomiales. Dans ton cas c'est relativement simple: si tu arrives à montrer que tout instance de ton problème peut se transformer en temps polynomial en une instance du problème de plus court chemin alors ton problème est résolvable par un algorithme glouton.

**touftouf57** · 24/09/2010, 13h13

Merci à vous.
Je vais me pencher sur la démonstration de l'optimalité de l'algorithme de Dijkstra.

Je reviendrai vers vous si j'ai du mal à le saisir.