Comment prouver que l'algorithme gourmand est correct

29

J'ai un algorithme gourmand que je soupçonne peut-être correct, mais je ne suis pas sûr. Comment vérifier si c'est correct? Quelles sont les techniques à utiliser pour prouver un algorithme gourmand correct? Existe-t-il des modèles ou des techniques communs?

J'espère que cela deviendra une question de référence qui pourra être utilisée pour indiquer aux débutants; d'où sa portée plus large que d'habitude. Veuillez prendre soin de donner des réponses générales, présentées de manière didactique, illustrées par au moins un exemple mais couvrant néanmoins de nombreuses situations. Merci!

DW
la source
Peut-on prouver qu'un algorithme gourmand est correct en utilisant un matroïde ou un greedoid?
zdm

Réponses:

24

En fin de compte, vous aurez besoin d'une preuve mathématique d'exactitude. Je vais aborder quelques techniques de preuve pour cela ci-dessous, mais avant de plonger dans cela, laissez-moi vous faire gagner du temps: avant de chercher une preuve, essayez des tests aléatoires.

Tests aléatoires

Dans un premier temps, je vous recommande d'utiliser des tests aléatoires pour tester votre algorithme. C'est incroyable à quel point c'est efficace: d'après mon expérience, pour les algorithmes gourmands, les tests aléatoires semblent être déraisonnablement efficaces. Passez 5 minutes à coder votre algorithme, et vous pourriez vous épargner une heure ou deux en essayant de trouver une preuve.

L'idée de base est simple: implémentez votre algorithme. De plus, implémentez un algorithme de référence que vous savez être correct (par exemple, un algorithme qui essaie de manière exhaustive toutes les possibilités et tire le meilleur parti). C'est bien si votre algorithme de référence est asymptotiquement inefficace, car vous ne l'exécuterez que sur de petites instances à problème. Ensuite, générez au hasard un million de petites instances de problème, exécutez les deux algorithmes sur chacun et vérifiez si votre algorithme candidat donne la bonne réponse dans chaque cas.

Empiriquement, si votre algorithme gourmand candidat est incorrect, vous le découvrirez souvent lors de tests aléatoires. S'il semble être correct dans tous les cas de test, vous devez passer à l'étape suivante: proposer une preuve mathématique de correction.

Preuves mathématiques d'exactitude

OK, nous devons donc prouver que notre algorithme gourmand est correct: qu'il génère la solution optimale (ou, s'il existe plusieurs solutions optimales qui sont également bonnes, qu'il génère l'une d'entre elles).

Le principe de base est intuitif:

Principe: Si vous ne faites jamais de mauvais choix, vous ferez OK.

Les algorithmes gourmands impliquent généralement une séquence de choix. La stratégie de preuve de base est que nous allons essayer de prouver que l'algorithme ne fait jamais un mauvais choix. Les algorithmes gourmands ne peuvent pas revenir en arrière - une fois qu'ils ont fait un choix, ils sont engagés et n'annuleront jamais ce choix - il est donc essentiel qu'ils ne fassent jamais un mauvais choix.

Qu'est-ce qui constituerait un bon choix? S'il n'y a qu'une seule solution optimale, il est facile de voir ce qui est un bon choix: tout choix identique à celui fait par la solution optimale. En d'autres termes, nous essaierons de prouver que, à n'importe quelle étape de l'exécution des algorithmes gourmands, la séquence de choix effectuée par l'algorithme jusqu'à présent correspond exactement à un préfixe de la solution optimale. S'il existe plusieurs solutions optimales tout aussi bonnes, un bon choix est celui qui est compatible avec au moins l'un des optima. En d'autres termes, si la séquence de choix de l'algorithme jusqu'à présent correspond à un préfixe de l'une des solutions optimales, tout va bien jusqu'à présent (rien ne s'est encore mal passé).

Pour simplifier la vie et éliminer les distractions, concentrons-nous sur le cas où il n'y a pas de liens: il existe une solution optimale unique et unique. Toutes les machines seront reportées au cas où il peut y avoir plusieurs optima tout aussi bons sans aucun changement fondamental, mais vous devez être un peu plus prudent sur les détails techniques. Commencez par ignorer ces détails et concentrez-vous sur le cas où la solution optimale est unique; cela vous aidera à vous concentrer sur l'essentiel.

Il existe un modèle de preuve très courant que nous utilisons. Nous travaillerons dur pour prouver la propriété suivante de l'algorithme:

Affirmation: Soit la solution issue de l'algorithme et O la solution optimale. Si S est différent de O , alors nous pouvons modifions O pour obtenir une autre solution O * qui est différent de O et strictement mieux que O .SOSOOOOO

Remarquez pourquoi cela est utile. Si l'affirmation est vraie, il s'ensuit que l'algorithme est correct. Il s'agit essentiellement d'une preuve par contradiction. Soit est identique à O, soit différent. S'il est différent, alors nous pouvons trouver une autre solution O qui est strictement meilleure que O - mais c'est une contradiction, car nous avons défini O comme étant la solution optimale et il ne peut y avoir de solution meilleure que cela. Nous sommes donc obligés de conclure que S ne peut pas être différent de O ; S doit toujours être égal à OSOOOOSOSO, c'est-à-dire que l'algorithme gourmand génère toujours la bonne solution. Si nous pouvons prouver la revendication ci-dessus, alors nous avons prouvé que notre algorithme est correct.

Bien. Alors, comment pouvons-nous prouver la réclamation? On pense à une solution comme un vecteur ( S 1 , , S n ) qui correspond à la séquence de n choix faite par l'algorithme, et de même, on pense à la solution optimale O comme un vecteur ( O 1 , , O n ) correspondant à la séquence de choix qui conduirait à O . Si S est différent de O , il doit exister un indice iS iS(S1,,Sn)nO(O1,,On)OSOi ; nous allons nous concentrer sur le plus petit tel i . Ensuite, nous ajusterons O en changeant O un peu dans la i ème position pour correspondre à S i , c'est-à-dire que nous ajusterons la solution optimale O en changeant le i ème choix en celui choisi par l'algorithme gourmand, puis nous montrerons que cela conduit à une solution encore meilleure. En particulier, nous définirons O comme quelque chose commeSiOiiOOiSiOiO

O=(O1,O2,,Oi1,Si,Oi+1,Oi+2,,On),

sauf que souvent nous devrons modifier légèrement la partie pour maintenir la cohérence globale. Une partie de la stratégie de preuve implique une certaine habileté à définir correctement O . Ensuite, la viande de la preuve sera en quelque sorte en utilisant des faits sur l'algorithme et le problème pour montrer que O est strictement meilleur que OOi+1,Oi+2,,OnOOO; c'est là que vous aurez besoin de quelques informations spécifiques au problème. À un moment donné, vous devrez vous plonger dans les détails de votre problème spécifique. Mais cela vous donne une idée de la structure d'une preuve de correction typique pour un algorithme gourmand.

Un exemple simple: sous-ensemble avec somme maximale

Cela pourrait être plus facile à comprendre en travaillant à travers un exemple simple en détail. Considérons le problème suivant:

Entrée: Un ensemble d'entiers, un entier k Sortie: Un ensemble S U de taille k dont la somme est la plus grande possibleUk
SUk

Il existe un algorithme naturel gourmand pour ce problème:

  1. Réglez .S:=
  2. Pour : i:=1,2,,k
    • xiUiUxiS

Des tests aléatoires suggèrent que cela donne toujours la solution optimale, alors prouvons formellement que cet algorithme est correct. Notez que la solution optimale est unique, nous n'aurons donc pas à nous soucier des liens. Prouvons la revendication décrite ci-dessus:

SU,kOSOOO

SOixiOiSOS={x1,,xk}ix1,,xi1OOO={x1,x2,,xi1,xi,xi+1,,xn}x1,,xi1,xi,,xnx1,,xixi>xjjixi>xiO=O{xi}{xi}OiOxiOOxixixixi>0OO

OOOO

Oxixi

DW
la source
C'est une vieille question, mais c'est le premier résultat dans Google pour moi. La ligne then we can tweak O to get another solution O∗ that is different from O and strictly better than Ome confond. S'il existe plusieurs solutions optimales, il est possible d'avoir S != Oet les deux restent optimales; nous pouvons modifier O pour qu'il ressemble davantage à S (créant O ∗) tout en étant aussi bon que (pas strictly better than) O.
citelao
@citelao, je suis désolé d'apprendre que cela vous a dérouté. Hélas, je ne sais pas comment l'expliquer plus clairement. Oui, il pourrait y avoir plusieurs solutions optimales, toutes avec la même valeur. C'est exact. Ce que vous avez écrit et ce que j'ai écrit sont tous deux valides; il n'y a pas de contradiction. La différence est que ce que vous avez écrit n'aide pas à prouver qu'un algorithme gourmand est correct; ce que j'ai écrit fait. Je ne peux que suggérer de relire ce que j'ai écrit et voir si vous pouvez comprendre en quoi ce que j'ai écrit est utile. Si cela n'aide pas, trouvez peut-être un article différent. Je me rends compte que c'est délicat et déroutant.
DW
1
Merci pour la réponse rapide! J'ai raté le point où vous vous concentrez à prouver l'algorithme s'il n'y en a qu'un a single, unique optimal solution. Puisque cette question vise à prouver que tout algorithme gourmand est correct, je voudrais fournir une réponse pour les cas où plusieurs solutions optimales peuvent exister. Cela fait un moment que je n'ai pas étudié tout cela, mais ce n'est pas suffisant pour prouver que vous pouvez échanger chaque élément O_i dans n'importe quelle solution optimale O qui diffère de l'alg. solution S avec S_i et ont toujours une solution O 'qui n'est pas pire que O?
citelao
@citelao, la technique s'applique également aux cas où il existe plusieurs solutions optimales. J'ai suggéré de me concentrer sur le cas où la solution optimale n'est unique que parce que, la première fois que vous voyez cela, il est plus facile de comprendre comment ces preuves fonctionnent dans ce contexte. Mais la même stratégie fonctionne même s'il existe plusieurs solutions optimales. Je suggère d'étudier cela, de vous assurer de comprendre comment cela fonctionne lorsqu'il existe une seule solution optimale, puis de l'appliquer au cas général. Je pense également que cela pourrait vous aider à étudier quelques exemples de preuves d'algorithmes gourmands.
DW
Pour répondre à votre dernière question, non, cela ne suffit pas. Cela ne prouve pas que S soit optimal. (Si vous exigez seulement que O 'ne soit pas pire que O, il y a des cas où S est sous-optimal mais il est possible de faire ce genre d'échange. Prouvant ainsi qu'il est possible d'atteindre un O' qui n'est pas pire que O ne le fait pas ne prouve rien sur le fait que S soit optimal et ne prouve pas que l'algorithme gourmand est correct. Je suggère d'étudier un peu plus la méthode décrite dans la réponse. C'est délicat. La preuve par contradiction est souvent difficile à comprendre.)
DW
14

Je vais utiliser l'algorithme de tri simple suivant comme exemple:

repeat:
  if there are adjacent items in the wrong order:
     pick one such pair and swap
  else
     break

Pour prouver l'exactitude, j'utilise deux étapes.

  • Je montre d'abord que l'algorithme se termine toujours.
  • Ensuite, je montre que la solution où elle se termine est celle que je veux.

Pour le premier point, je choisis une fonction de coût appropriée pour laquelle je peux montrer que l'algorithme l'améliore à chaque étape.

AA[i]A[j]A[i]>A[j]i<j

A[i]A[i+1]A[i],A[i+1]

Cela prouve que l'algorithme se termine finalement.

Le nombre d'inversions dans une liste triée est 0. Si tout se passe bien, l'algorithme réduira le nombre d'inversions à 0. Il suffit de montrer qu'il ne reste pas coincé dans un minimum local.

Je le prouve généralement par contradiction. Je suppose que l'algorithme s'est arrêté, mais la solution n'est pas correcte. Dans l'exemple, cela signifie que la liste n'est pas encore triée, mais qu'il n'y a aucun élément adjacent dans le mauvais ordre.

A[i]A[j]i<jA[i]>A[j]iji+1<jA[i]<A[i+1]A[i+1]<A[j]A[i]<A[j]

Cela prouve que l'algorithme ne s'arrête que lorsque la liste est triée. Et donc nous avons terminé.

adrianN
la source
Les techniques expliquées sont si générales qu'elles n'ont pratiquement rien de particulier à propos de l'algorithme gourmand, le sujet de cette question.
Apass.Jack