Algorithme de recherche
654457
26153141
2008-02-13T10:17:51Z
DumZiBoT
280295
Robot : Passage au modèle {{ébauche}} : {{ébauche|informatique}} ; changement de type cosmétique
{{Voir homonymes|recherche (homonymie)}}
{{à illustrer}}
{{ébauche|informatique}}
En [[informatique]], un '''algorithme de recherche''' est un type d'[[Algorithmique|algorithme]] qui,
pour un domaine, un [[problème]] de ce domaine et des critères donnés, retourne en résultat un [[ensemble]] de solutions répondant au problème.
Supposons que l'[[ensemble]] de ses entrées soit divisible en sous-ensemble, par rapport à un critère donné, qui peut être, par exemple, une [[relation d'ordre]]. De façon générale, un tel algorithme vérifie un certain nombre de ces entrées et retourne en sortie une ou plusieurs des entrées visées.
L'ensemble de toutes les solutions potentielles dans le domaine est appelé ''espace de recherche''.
== Algorithmes de recherche classique ==
Sur des [[structure de données|structures de données]] usuelles comme les [[Liste (informatique)|listes]], les [[tableau (structure de données)|tables]] ou les [[Arbre (informatique)|arbres]], il existe des algorithmes ''bien connus'' que l'on peut facilement mettre en œuvre à la manière d'une recette de cuisine. Ces algorithmes exploitent les propriétés de la structure de données et du domaine.
Un exemple classique est la recherche [[Dichotomie|dichotomique]] où l'on divise en deux l'espace de recherche à chaque tentative ce qui donne une [[complexité]] [[logarithme|logarithmique]] (donc très avantageuse).
== Recherche de solutions à des problèmes complexes ==
Pour des problèmes complexes, la recherche de solutions relève de l'[[intelligence Artificielle]].
* On dit qu'un algorithme est de [[recherche par force brute]] lorsque toutes les entrées sont vérifiées une à une. Ce type de recherche peut s'avérer efficace si l'espace des solutions est d'une taille raisonnable vis à vis de la puissance de la machine utilisée pour le parcourir. Il s'agit donc d'une méthode à tenter en dernier recours s'il n'y a pas d'autre possibilités.
* On parle de recherche [[heuristique]]s lorsque des connaissances ou des propriétés supplémentaires permettent de rendre la recherche plus efficace. Ainsi, l'exploitation des symétries géométriques dans la résolution d'un puzzle permet de réduire fortement l'''espace de recherche''. De la même façon, une [[pathfinding|recherche de chemin]] peut être facilité par la connaissance même approximative de la direction dans laquelle se trouve l'objectif ou de sa distance.
== Complexité ==
Ces algorithmes sont au centre de questions importantes en [[complexité]] algorithmique. Ils ont aussi très importants de par leurs vastes domaines d'application.
== Exemples ==
* [[Algorithme de recherche de sous-chaîne]]
* [[Pathfinding|Algorithme de recherche de chemin (Pathfinding)]]
== Voir aussi ==
* [[Algorithme réparti]]
{{portail informatique}}
[[Catégorie:Algorithme de recherche]]
[[de:Suchverfahren]]
[[en:Search algorithm]]
[[fi:Hakualgoritmi]]
[[id:Algoritma pencarian]]
[[it:Algoritmo di ricerca]]
[[ja:検索]]
[[nl:Zoekalgoritme]]
[[pt:Algoritmo de busca]]
[[vi:Giải thuật tìm kiếm]]