Quand dit-on que deux algorithmes sont «similaires»?

Je ne travaille pas en théorie, mais mon travail nécessite de lire (et de comprendre) des articles théoriques de temps en temps. Une fois que j'ai compris un (ensemble de) résultats, je discute de ces résultats avec des gens avec qui je travaille, dont la plupart ne fonctionnent pas aussi en théorie. Au cours d'une de ces discussions, la question suivante s'est posée:

Quand dit-on que deux algorithmes donnés sont "similaires"?

Qu'est-ce que j'entends par "similaire"? Disons que deux algorithmes sont réputés similaires si vous pouvez faire l'une des revendications suivantes dans un document sans dérouter / ennuyer aucun critique (de meilleures définitions sont les bienvenues):

Revendication 1. "L'algorithme , qui est similaire à l'algorithme B , résout également le problème X "$A$$B$$X$

Revendication 2. "Notre algorithme est similaire à l'algorithme "$C$

Permettez-moi de le rendre un peu plus précis. Supposons que nous travaillons avec des algorithmes de graphe. D'abord quelques conditions nécessaires pour que les deux algorithmes soient similaires:

1. Ils doivent résoudre le même problème.
2. Ils doivent avoir la même idée intuitive de haut niveau.

Par exemple, parler de traversée de graphe, traversée en largeur d'abord et en profondeur d'abord satisfait aux deux conditions ci-dessus; pour les calculs sur le chemin le plus court, l'amplitude en premier et l'algorithme de Dijkstra satisfont aux deux conditions ci-dessus (sur les graphiques non pondérés, bien sûr); etc.

Ces conditions sont-elles également suffisantes? Plus précisément, supposons que deux algorithmes remplissent les conditions nécessaires pour être similaires. Les appelleriez-vous en effet similaires, si

1. ils ont des performances asymptotiques différentes?
2. pour une classe particulière de graphes, un algorithme nécessite du temps tandis que l'autre nécessite O ( n une / 3 ) fois?$\Omega(n)$$O(n^{1/3})$
3. ils ont des conditions de terminaison différentes? (rappelez-vous, ils résolvent le même problème)
4. l'étape de prétraitement est différente dans les deux algorithmes?
5. la complexité de la mémoire est différente dans les deux algorithmes?

Edit: La question est clairement très dépendante du contexte et est subjective. J'espérais cependant que les cinq conditions ci-dessus permettront d'obtenir des suggestions. Je suis heureux de modifier davantage la question et de donner plus de détails, si nécessaire, pour obtenir une réponse. Merci!

Il est difficile de donner une définition même cohérente de "l'algorithme A est similaire à l'algorithme B". D'une part, je ne pense pas que "ils doivent résoudre le même problème" soit une condition nécessaire. Souvent, quand on dit dans un article que "l'algorithme du théorème 2 est similaire à l'algorithme B du théorème 1 ", l'algorithme A résout en fait un problème différent de celui de B , mais a quelques modifications mineures pour gérer le nouveau problème .$A$$2$$B$$1$$A$$B$

Même essayer de déterminer ce que signifie que deux algorithmes soient identiques est un problème intéressant et difficile. Voir l'article "Quand deux algorithmes sont-ils identiques?" http://research.microsoft.com/~gurevich/Opera/192.pdf

Plus souvent qu'autrement, cela signifie "Je ne veux pas écrire l'algorithme B en détail, car tous les détails intéressants sont presque identiques à ceux de l'algorithme A, et je ne veux pas dépasser la limite de 10 pages, et de toute façon le délai de soumission est de trois heures. "

Si vous voulez dire "similaire" dans le sens courant, je pense que la réponse de JeffE capture ce que certaines personnes veulent dire.

Sur le plan technique, cela dépend de ce qui vous intéresse. Si vous ne vous souciez que de la complexité temporelle asymptotique, la différence entre la récursivité et l'itération peut ne pas avoir d'importance. Si vous ne vous souciez que de la calculabilité, la différence entre une variable de compteur et une pile à un symbole n'a pas d'importance.

$A$$M$$\mathit{sem}: A \to M$$\mathit{sem}(P)$$P$$M$$M$$M$$\mathit{sem}(P)$$\mathit{sem}(Q)$

$M$$(M, \sqsubseteq)$$x \sqsubseteq y$$x$$y$$M$$\sqsubseteq$$\mathit{sem}(P) \sqsubseteq \mathit{sem}(Q)$$P$$Q$$P$$Q$

$M$

Plus généralement, je demanderais: de quoi vous souciez-vous (en termes intuitifs), quels sont les objets mathématiques représentant ces propriétés intuitives, comment puis-je mapper des algorithmes à ces objets et quelle est la structure de cet espace? Je demanderais également si l'espace des objets jouit d'une structure suffisante pour admettre une notion de similitude. C'est l'approche que j'adopterais du point de vue de la sémantique du langage de programmation. Je ne sais pas si vous trouvez cette approche attrayante, étant donné les cultures très différentes de la pensée en informatique.

Dans le sens de la réponse de Jeff, deux algorithmes sont similaires si l'auteur de l'un d'eux s'attend à ce que l'auteur de l'autre revoie son article.

Mais en plaisantant, dans la communauté de la théorie, je dirais que le problème que l'algorithme A résout est plutôt tangentiel pour savoir s'il est "similaire" à l'algorithme B, qui pourrait résoudre un problème complètement différent. A est similaire à B s'il "fonctionne" en raison de la même idée théorique principale. Par exemple, l'idée principale dans les deux algorithmes est-elle que vous pouvez projeter les données dans un espace dimensionnel beaucoup plus bas, préserver les normes avec le lemme de Johnson-Lindenstrauss, puis faire une recherche par force brute? Ensuite, votre algorithme est similaire aux autres algorithmes qui le font, quel que soit le problème que vous résolvez. Il existe un petit nombre de techniques algorithmiques robustes qui peuvent être utilisées pour résoudre une grande variété de problèmes, et je pense que ces techniques forment les centres de gravité de nombreux ensembles d'algorithmes "similaires".

Question très intéressante, et très beau papier Ryan!

Je suis définitivement d'accord avec l'idée que faire une évaluation de la similitude globale entre les algorithmes est principalement un jugement de valeur subjectif. Bien que d'un point de vue technique, il existe un certain nombre de fonctionnalités qui sont étroitement observées pour décider de la similitude des algorithmes, en fin de compte, c'est aussi une question de goût personnel. J'essaierai de fournir une description de l'importance des deux faces d'une même pièce tout en faisant référence aux points particuliers de votre question:

D'un point de vue technique:

1. Ryan a déjà souligné que les deux algorithmes doivent résoudre le même problème . On pourrait aller encore plus loin et généraliser cette notion en disant qu'il suffit généralement de prouver qu'il existe une transformation polynomiale de la même instance compréhensible par l'algorithme A pour que l'algorithme B puisse la gérer. Cependant, ce serait en fait très faible. Je préfère penser la similitude dans un sens plus fort.
2. Cependant, je ne m'attendrais jamais à ce que deux algorithmes équivalents aient la même idée intuitive --- bien que, encore une fois, il s'agit d'une définition qui n'est pas facile à saisir. Plus encore, il arrive souvent que des algorithmes jugés similaires ne suivent pas la logique principale. Considérez par exemple certains algorithmes de tri qui, cependant, sont nés de différentes manières suivant des idées différentes. À titre d'exemple extrême, considérons les algorithmes génétiques qui sont généralement considérés par la communauté mathématique comme des processus stochastiques (et donc équivalents selon eux) qui sont ensuite modélisés et analysés d'une manière tout à fait différente.
3. $N$$^*$$(N^2-1)$les bases de données de modèles additifs développeraient en fait le même nombre de nœuds dans le même ordre exactement, ce qui rend les deux algorithmes (et leurs heuristiques) strictement équivalents au sens fort, tandis que la première approche n'a pas de prétraitement et la seconde a une surcharge importante avant de commencer à résoudre une instance particulière. Cependant, dès que vos bases de données de modèles envisagent des interactions plus simulées, il y a un énorme écart de performances entre elles, de sorte qu'il s'agit définitivement d'idées / d'algorithmes différents.
4. En fait, je pense que la plupart des gens jugeraient les algorithmes en fonction de leur objectif et de leurs performances . Par conséquent, la performance asymptotique est une bonne mesure pour raisonner sur la similitude entre les programmes. Cependant, gardez à l'esprit que cette performance n'est pas nécessairement le cas typique, de sorte que si deux algorithmes ont la même performance asymptotique mais se comportent différemment dans la pratique, vous concluriez probablement qu'ils sont différents. La preuve solide à cet égard serait que les deux algorithmes ont les mêmes performances à la fois en temps et en mémoire (et cela, comme l'a dit Suresh, fait que DFS et BFS semblent différents). Dans le cas où cette affirmation ne vous semble pas convaincante, veuillez vous référer à l'excellent (et très recommandé livre): Programmation de l'Universpar Seth Lloyd. À la page 189, il fait référence à une liste avec plus de 30 mesures de complexité qui peuvent être utilisées pour considérer les algorithmes comme différents.

Alors, qu'est-ce qui rend les algorithmes similaires / différents? À mon avis (et c'est purement spéculatif), la principale différence concerne ce qu'ils vous suggèrent. Beaucoup, beaucoup (beaucoup!) D'algorithmes ne diffèrent que par quelques détails techniques lorsqu'ils servent au même but, de sorte que le cas typique est différent pour différentes plages d'entrée. Cependant, la plus grande de toutes les différences est (à mes yeux) ce qu'elles vous suggèrent. Les algorithmes ont des capacités différentes et donc leurs propres forces et faiblesses. Si deux algorithmes semblent identiques, mais peuvent être étendus de différentes manières pour faire face à différents cas, je conclurais qu'ils sont différents. Souvent, cependant, deux algorithmes se ressemblent beaucoup, de sorte que vous les considéreriez comme étant identiques ... jusqu'à ce que quelqu'un arrive en faisant une distinction clé et soudain, ils sont complètement différents!

Désolé, ma réponse a été si longue à la fin ...

À votre santé,

Toute mention de similitude sans définir de métrique de similitude n'est pas bien définie. Il existe de nombreuses façons dont deux algorithmes peuvent être similaires:

Quicksort et Mergesort résolvent des problèmes très similaires, mais ils utilisent différents algorithmes pour ce faire. Ils ont une complexité algorithmique similaire (bien que leurs performances les plus défavorables et leur utilisation de la mémoire puissent varier). Quicksort et Mergesort sont tous deux similaires à Bubblesort, mais Bubblesort a des mesures de performances très différentes. Si vous ignorez les statistiques de complexité, Quicksort, Mergesort et Bubblesort sont tous dans la même classe d'équivalence. Cependant, si vous vous souciez de la complexité algorithmique, Quicksort et Mergesort sont beaucoup plus similaires les uns aux autres que Bubblesort.

La programmation dynamique de Smith-Waterman et la comparaison de séquences HMM tentent de résoudre le problème de l'alignement de deux séquences. Cependant, ils prennent différentes entrées. Smith-Waterman prend deux séquences en entrée et les comparaisons de séquences HMM prennent un HMM et une séquence en entrée. Les deux alignements de séquence de sortie. En termes d'idées motivantes, les deux sont similaires à la distance d'édition de Levenshtein , mais seulement à un niveau très élevé.

Voici quelques critères par lesquels deux algorithmes peuvent être appelés similaires:

1. Types d'entrée / sortie
2. Complexité algorithmique / mémoire
3. Hypothèses sur les types d'entrées (par exemple, uniquement les nombres positifs ou la stabilité en virgule flottante)
4. Relations imbriquées (par exemple, certains algorithmes sont des cas particuliers d'autres)

La décision critique sur la signification de la similitude demeure. Parfois, vous vous souciez de la complexité d'un algorithme, parfois non. Comme la définition de la similitude dépend du contexte de la discussion, le terme «algorithme similaire» n'est pas bien défini.