Algorithmes de recherche

Algorithmes de recherche

Algorithme de recherche

Page d'aide sur l'homonymie Pour les articles homonymes, voir recherche (homonymie).

En informatique, un algorithme de recherche est un type d'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.

Sommaire

Algorithmes de recherche classique

Sur des structures de données usuelles comme les listes, les tables ou les 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 dichotomique où l'on divise en deux l'espace de recherche à chaque tentative ce qui donne une complexité 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 heuristiques 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 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

Voir aussi

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Algorithme de recherche ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithmes de recherche de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Algorithmes de recherche de sous-chaîne — Algorithme de recherche de sous chaîne Un algorithme de recherche de sous chaine est un type d algorithme de recherche qui a pour objectif de trouver une chaîne de caractères à l intérieur d une autre. Un tel algorithme fournit la position du… …   Wikipédia en Français

  • Recherche De Chemin — Chemins équivalents allant de A à B dans un environnement à deux dimensions La recherche de chemin, couramment appelée pathfinding, est un problème de l intelligence artificielle qui se rattache plus généralement au domaine de la planification et …   Wikipédia en Français

  • Recherche par force brute — Recherche exhaustive La recherche exhaustive ou recherche par force brute, est un terme qui s applique à une catégorie de méta algorithmes. C est une technique extrêmement simple, mais très générale, qui consiste à énumérer tous les candidats… …   Wikipédia en Français

  • Algorithmes — Algorithmique « Algorithme » redirige ici. Pour la notion d algorithme en sport, voir algorithme (sport). On désigne par algorithmique l’ensemble des activités logiques qui relèvent des algorithmes ; en particulier, en informatique …   Wikipédia en Français

  • Recherche de chemin — Chemins équivalents allant de A à B dans un environnement à deux dimensions La recherche de chemin, couramment appelée pathfinding, est un problème de l intelligence artificielle qui se rattache plus généralement au domaine de la planification et …   Wikipédia en Français

  • Recherche plein texte — Pour les articles homonymes, voir Recherche (homonymie) et Plein texte. La recherche (en) plein texte (appelée aussi recherche en texte intégral[1] ou recherche de texte libre) est une technique de recherche textuelle dans un document… …   Wikipédia en Français

  • Recherche locale — En informatique, la recherche locale est une métaheuristique utilisée pour résoudre des problèmes d optimisation difficiles. La recherche locale peut être utilisée sur des problèmes de recherche d une solution maximisant un critère parmi un… …   Wikipédia en Français

  • Recherche exhaustive — La recherche exhaustive ou recherche par force brute, est un terme qui s applique à une catégorie de méta algorithmes. C est une technique extrêmement simple, mais très générale, qui consiste à énumérer tous les candidats possibles, jusqu à… …   Wikipédia en Français

  • Recherche operationnelle — Recherche opérationnelle La recherche opérationnelle (aussi appelée aide à la décision) peut être définie comme l ensemble des méthodes et techniques rationnelles d analyse et de synthèse des phénomènes d organisation utilisables pour élaborer de …   Wikipédia en Français

  • Algorithmes De Connexité Basés Sur Des Pointeurs — Les algorithmes de connexité suivants permettent de déterminer rapidement si deux sommets d un graphe non orienté sont reliés par un chemin ou non, en créant un tableau de pointeurs qui implémente en fait une forêt d arbres. Chaque arbre créé par …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”