Existe-t-il une méthode générale pour évaluer l'optimalité d'un algorithme d'optimisation?

Existe-t-il une méthode générale pour évaluer l'optimalité d'un algorithme d'optimisation, par exemple un algorithme résolvant un problème par ailleurs NP-dur ou NP-complet?

La seule méthode que j'ai trouvée jusqu'à présent consiste à comparer les résultats de l'algorithme avec des solutions optimales déjà connues.

Sinon, existe-t-il des méthodes spécifiques pour certains problèmes particuliers?

EDIT Pour clarifier: Par optimalité, je veux dire à quel point le résultat est proche d'un résultat de solutions optimales.

Cela dépend du type de problème.

S'il existe un schéma d'approximation du temps polynomial (PTAS) pour le problème (par exemple, TSP euclidien), vous pouvez obtenir une solution arbitrairement proche de la solution optimale en temps polynomial. Cela signifie que pour chaque e > 0, il existe un algorithme de temps polynomial qui trouvera une solution approximative à votre problème, qui est garanti d'être à moins de (1+ e ) de la solution optimale. Dans ce cas, vous devez simplement comparer la complexité d'exécution / mémoire pour deux algorithmes pour les mêmes valeurs de e . Si un algorithme peut offrir les mêmes "garanties d'optimalité" que l'autre, mais à un coût de fonctionnement / mémoire inférieur, c'est probablement le meilleur algorithme.

Si le problème est APX, mais pas PTAS , c'est-à-dire s'il existe des algorithmes polynomiaux d'approximation du temps qui sont garantis pour produire des solutions qui sont dans un facteur constant de la solution optimale, alors vous pouvez comparer ce facteur constant. Celui avec le facteur le plus faible produira les meilleures solutions (mais souvent au prix de temps de fonctionnement / coûts de mémoire plus élevés)

Si le problème n'appartient à aucune de ces classes, je pense que le mieux que vous puissiez faire est de comparer leurs solutions pour un ensemble de problèmes aléatoires ou pour des problèmes avec des solutions optimales connues.

Je ne pense pas qu'il existe une manière générale de procéder, mais il existe certainement des méthodes pour le faire.

Prenons, par exemple, le problème SET-COVER. Pour ceux qui ne connaissent pas le problème est le suivant:

Étant donné un ensemble d'éléments B={1,2,...,m}et un certain nombre de sous-ensembles S_1, S_2, ..., S_ndont l'union est B. Vous essayez de trouver le nombre minimum de ces sous-ensembles de telle sorte que l'union est toujours B. Un exemple typique de ce problème dans le monde réel est celui où l'on vous donne une collection de quartiers et où vous essayez de trouver les endroits optimaux pour placer les écoles de telle sorte que chaque quartier soit desservi à moins d'une certaine distance dde l'école la plus proche. Dans ce cas, Best l'ensemble des quartiers et se S_xcompose de tous les ensembles au sein dde la ville x.

Vous prouvez que ce problème est NP-COMPLETE. Cependant, il existe une solution simple et gourmande où vous choisissez à plusieurs reprises l'ensemble S_iavec le plus grand nombre d'éléments découverts. Et vous pouvez prouver que cet algorithme fonctionne bien .

Si l'algorithme optimal est constitué d' kensembles, l'algorithme gourmand ne comprendra pas plus de k ln(n)ensembles où ln est le logarithme naturel.

Le problème de déterminer si un programme a une «performance d'optimalité» A ou une «performance d'optimalité» B pour à peu près n'importe quelle définition de «performance d'optimalité» est indécidable en général (preuve ci-dessous). Cela implique qu'aucune méthode unique ne peut toujours vous dire à quel point un algorithme est optimal.

Il existe cependant des méthodes qui sont souvent appliquées lors de l'analyse des algorithmes d'approximation. Souvent, les algorithmes d'approximation sont évalués par leurs garanties sur la distance entre sa solution et la solution optimale. Je vais donner un exemple de problème et d'approximation, que je prouverai en utilisant la méthode de la «borne inférieure», qui est une méthode très couramment utilisée pour prouver les ratios.

Le problème en question est le problème du «chargement des camions»: nous avons beaucoup de camions identiques (autant que nous le voulons), chacun capable de transporter une charge pesant au plus T. Nous avons n objets que nous souhaitons charger dans ces camions pour transport. Chaque objet i a un poids w_i, où w_i <= T (donc il n'y a pas d'articles qui ne peuvent pas tenir sur un camion même par eux-mêmes). Les articles ne peuvent pas être divisés en parties. Nous aimerions faire le plein de camions afin d'avoir le moins de camions possible. Ce problème est NP-complet.

Il existe un algorithme d'approximation très simple pour ce problème. Nous commençons simplement à charger un camion avec des articles, jusqu'à ce que le camion soit si plein que l'article suivant ne rentre pas. Nous prenons ensuite un autre camion et chargeons ce camion avec cet article qui ne convenait pas au camion précédent. Nous ne chargeons plus d'articles sur ce camion: au lieu de cela, nous prenons un nouveau camion, nous le remplissons à nouveau avec beaucoup d'articles jusqu'à ce qu'il ne rentre plus, remettons ce dernier article sur son propre camion et ainsi de suite.

Cet algorithme est une soi-disant approximation 2 du problème: il utilise au plus deux fois plus de camions que la solution optimale aurait besoin. Le «tout au plus» est crucial: nous pourrions avoir de la chance et trouver la solution optimale, mais au moins nous ne ferons pas trop de mal.

Pour le prouver, nous définissons d'abord une borne inférieure sur le nombre optimal de camions dont nous avons besoin. Pour cela, imaginez que nous sommes autorisés à couper des articles en pièces: nous pourrions alors remplir facilement chaque camion mais le dernier complètement. Le nombre de camions dont nous aurions besoin si nous le faisions est une limite inférieure pour le nombre de camions dont nous avons besoin pour la question initiale: dans le «meilleur» cas, la solution optimale remplit toujours chaque camion complètement, auquel cas le nombre de camions est égal, mais si les solutions optimales laissent des camions non remplis, alors il ne peut avoir besoin que de plus de camions.

Nous regardons maintenant notre algorithme d'approximation. Notez qu'à chaque étape, nous remplissons (partiellement) deux camions. Notez également que, selon le fonctionnement de l'algorithme, les articles du premier camion et l'article du deuxième camion ne peuvent pas tenir ensemble dans le premier camion, leur somme est donc au moins T. Cela signifie qu'à chaque étape, nous chargeons au moins un plein valeur de camion d'articles sur deux camions. Maintenant, comparez ceci à notre borne inférieure: dans ce cas, nous chargeons un camion plein d'articles sur un seul camion. En d'autres termes, notre algorithme d'approximation calcule (en temps linéaire) une solution qui ressemble beaucoup à notre «solution» de limite inférieure, mais utilise deux camions au lieu d'un. Par conséquent, nous utilisons au plus deux fois plus de camions que l'algorithme optimal, car nous utilisons au plus deux fois plus de camions que notre limite inférieure sur l'algorithme optimal.

Cet algorithme donne une approximation à facteur constant: elle est au plus 2 fois plus mauvaise que la solution optimale. Quelques exemples d'autres mesures: au plus C plus que la solution optimale (erreur additive, assez rare), au plus c log n fois aussi mauvais que la solution optimale, au plus cn fois aussi mauvais que la solution optimale, au plus c 2 ^ (dn) fois aussi mauvais que la solution optimale (très mauvais; par exemple, le TSP général n'admet que des algorithmes avec ce genre de garanties).

Bien sûr, si vous voulez être sûr que le facteur que vous prouvez est le meilleur facteur que vous pouvez prouver, vous devriez essayer de trouver des cas dans lesquels la solution proposée par votre algorithme est en effet aussi mauvaise que possible.

Notez également que nous utilisons parfois des algorithmes d'approximation sur des problèmes qui ne sont pas NP-difficiles.

J'ai appris cela (parmi bien d'autres) dans le cours d'algorithmes d'approximation de mon université.

Preuve d'indécidabilité: soit P un problème et A et B des algorithmes d'approximation pour P où A et B n'ont pas la même `` optimalité '' pour une définition sensible de `` l'optimalité '', et où le temps d'exécution de A et B est à la fois oméga (1) (strictement plus lent que le temps constant, c'est-à-dire qu'ils deviennent plus lents pour les instances plus importantes) et où A et B s'arrêtent toujours.

Soit D un programme qui prétend pouvoir calculer ce qui suit: étant donné un programme C calculant une approximation pour P, décidez s'il est aussi bon que A ou aussi bon que B pour des entrées suffisamment grandes (vous pouvez donc l'utiliser pour catégoriser les programmes en fonction de leur optimalité).

Nous pouvons alors utiliser D pour résoudre le problème d'arrêt. Soit E un programme et F une entrée pour ce programme. Nous utiliserons D pour décider si E s'arrêtera sur l'entrée F.

Nous concevons un programme G qui fait ce qui suit: étant donné une entrée S pour le problème P, il exécute E sur F et A sur S en parallèle: il exécute E pendant un certain temps, puis A, puis encore E et ainsi de suite. Si E s'arrête sur F, il arrête d'exécuter A et exécute à la place B sur S et renvoie le résultat de B. Si A s'arrête avant qu'E s'arrête, il renvoie le résultat de A.

L'utilisation de D sur G décide maintenant si E s'arrête sur F: si E s'arrête sur F, alors pour des entrées suffisamment grandes S, E s'arrête sur F avant que A s'arrête sur S (car le temps qu'il faut à E pour s'arrêter ne dépend pas de la taille de l'entrée, contrairement à A). D rapporte donc que G a les caractéristiques d'optimalité de B. Si E ne s'arrête pas sur F, D rapportera que G a les caractéristiques d'optimalité de A.