Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | +
Algorithme de recherche

Introduction

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 (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un...) de ses entrées soit divisible en sous-ensemble (En mathématiques, un ensemble A est un sous-ensemble ou une partie d’un ensemble B, ou encore B est sur-ensemble de A, si tout élément du sous-ensemble A est aussi élément du...), 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 (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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 structures de données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.) 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 (La cuisine est l'ensemble des techniques de préparation des aliments en vue de leur consommation par les êtres humains (voir cuisinerie). La cuisine est diverse à travers le monde, fruit des ressources naturelles...). 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é (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri...) logarithmique (donc très avantageuse).

Complexité

Ces algorithmes sont au centre de questions importantes en complexité algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de...). Ils sont aussi très importants de par leurs vastes domaines d'application.

Recherche de solutions à des problèmes complexes

Pour des problèmes complexes, la recherche de solutions relève de l'intelligence artificielle (L'intelligence artificielle ou informatique cognitive est la « recherche de moyens susceptibles de doter les systèmes informatiques de capacités...).

  • On dit qu'un algorithme est de recherche par force (Le mot force peut désigner un pouvoir mécanique sur les choses, et aussi, métaphoriquement, un pouvoir de la volonté ou encore une vertu morale « cardinale »...) 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 (Le mot puissance est employé dans plusieurs domaines avec une signification particulière :) 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é.
  • 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ée par la connaissance même approximative de la direction dans laquelle se trouve l'objectif ou de sa distance.

Exemples

  • Algorithme de recherche (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...) de sous-chaîne
  • Algorithme de recherche de chemin (Pathfinding)
Source: Wikipédia publiée sous licence CC-BY-SA 3.0. Vous pouvez soumettre une modification à cette définition sur cette page.

La liste des auteurs de cet article est disponible ici.
Archives des News
  Juillet 2018
  Juin 2018
  Mai 2018
  Avril 2018
  Toutes les archives

Jeudi 19 Juillet 2018 à 00:00:10 - Physique - 0 commentaire
» ISOLDE produit des isotopes du chrome
Page générée en 0.058 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - Informations légales