Qu'est-ce qu'un algorithme "naïf", et qu'est-ce qu'une solution" de forme fermée"?
J'ai quelques questions concernant la sémantique de la terminologie utilisée pour décrire des algorithmes.
Tout d'abord, qu'entend-on par algorithme "naïf"? En quoi cela diffère-t-il des autres solutions à un problème donné? Quelles autres formes les solutions peuvent-elles prendre?
Deuxièmement, j'ai entendu beaucoup de références à une solution de forme fermée. Je n'ai aucune idée de ce que cela signifie non plus - mais souvent, il apparaît en essayant de résoudre les relations de récurrence...
Merci pour votre temps
3 réponses
Un algorithme naïf est généralement la solution la plus évidente lorsqu'on pose un problème. Ce n'est peut-être pas un algorithme intelligent mais va probablement faire le travail (...finalement.)
par exemple. Essayez de rechercher un élément dans un tableau trié. Un algorithme naïf serait d'utiliser une recherche linéaire . Une Solution pas si naïve serait d'utiliser la recherche binaire.
Un meilleur exemple, serait dans le cas de la recherche de sous-chaîne L'algorithme naïf est beaucoup moins efficace que l'algorithme Boyer–Moore ou Knuth–Morris–Pratt
Une Solution de forme fermée est une Solution simple qui fonctionne instantanément sans boucles, fonctions, etc..
Par exemple: Algorithme itératif pour la somme des entiers de 1 À n
s= 0
for i in 1 to n
s = s + i
end for
print s
Forme Fermée (pour le même problème)
s = n * (n + 1 ) /2
L'algorithme naïf est un algorithme très simple, avec des règles très simples. Parfois, le premier qui vient à l'esprit. Il peut être stupide et très lent, il peut même ne pas résoudre le problème. Il peut parfois être le meilleur possible. Voici un exemple de problème et" naïf " algorithmes:
Problème: vous êtes dans un labyrinthe (en 2 dimensions). Trouver votre chemin. (signification: à un endroit avec un signe" EXIT":)
Algorithme naïf 1: Commencez à marcher et choisissez le bon dans chaque intersection que vous rencontrez (jusqu'à ce que vous trouviez "sortie").
Algorithme naïf 2: commencez à marcher et choisissez un aléatoire dans chaque intersection que vous rencontrez (jusqu'à ce que vous trouviez "EXIT").
Algorithme 1 ne sera même pas vous sortir de certains labyrinthes!
Algorithme 2 vous sortir de tous les labyrinthes (bien que ce soit plutôt difficile à prouver).
La forme fermée signifie que vous pouvez donner une expression comme solution, qui la résout sans récurrence / récursive. Ici, on doit remarquer qu'il n'est pas toujours possible de trouver une forme fermée.
Naïf signifie Juste que ce qu'il dit: une première solution stupide au problème, qui le résout, mais peut-être pas très efficace dans le temps/l'espace. Ce que l'on considère vraiment "naïf" dépend de l'orateur, du contexte et de la météo du lendemain. Souvent, il est utilisé pour distinguer un très solution sophistiquée (qui utilise une sorte de truc) de l'implémentation évidente.