Algorithme de recherche

Un algorithme de recherche est tout algorithme qui permet de résoudre le problème de recherche, à savoir, pour récupérer des informations stockées dans une structure de données, ou calculées dans l'espace de recherche d'un domaine de problème, que ce soit avec des valeurs discrètes ou continues.

Les applications spécifiques des algorithmes de recherche comprennent:

1. Problèmes d’optimisation combinatoire

• Problème de l'itinéraire du véhicule, une forme de problème du plus court chemin
• Problème de la sac à dos : à partir d’un ensemble d’articles, chacun avec un poids et une valeur, déterminez le nombre d’articles à inclure dans une collection de manière à ce que le poids total soit inférieur ou égal à une limite donnée et que la valeur totale soit aussi élevée. comme possible.
• problème de planification infirmière

2. Problèmes rencontrés dans l’action satisfaite

• Problème de coloration de la carte
• Remplir un sudoku ou des mots croisés
• Dans la théorie des jeux et en particulier dans la théorie des jeux combinatoires, choisir le meilleur coup à faire (comme avec l’algorithme minmax)

• Trouver une combinaison ou un mot de passe parmi toutes les possibilités
• Factorisation d' un entier (un problème important en cryptographie)
• Optimiser un processus industriel, tel qu'une réaction chimique, en modifiant ses paramètres (comme la température, la pression et le pH)
• Récupérer un enregistrement d'une base de données
• Recherche de la valeur maximale ou minimale dans une liste ou un tableau
• Vérifier si une valeur donnée est présente dans un ensemble de valeurs

Les problèmes classiques de recherche décrits ci-dessus et de recherche sur le Web sont des problèmes de recherche d’informations, mais ils sont généralement étudiés comme des sous-champs distincts et sont résolus et évalués différemment. sont généralement axés sur le filtrage et trouvent les documents les plus pertinents pour les questions humaines. Les algorithmes de recherche classiques sont généralement évalués en fonction de la rapidité avec laquelle ils peuvent trouver une solution et de la garantie que cette solution est optimale ou non. Bien que les algorithmes de recherche d'informations doivent être rapides, la qualité du classement est plus importante, qu'il s'agisse de laisser de bons résultats ou non, de mauvais résultats.

L'algorithme de recherche approprié dépend souvent de la structure de données recherchée et peut également inclure une connaissance préalable des données. Certaines structures de base de données sont spécialement conçues pour rendre les algorithmes de recherche plus rapides ou plus efficaces, tels qu'un arbre de recherche, une carte de hachage ou un index de base de données. 

Les algorithmes de recherche peuvent être classés en fonction de leur mécanisme de recherche. Des algorithmes de recherche linéaire sélectionnent chaque enregistrement de celui associé à une clé cible de manière linéaire.  Les recherches binaires ou à demi-intervalles ciblent à plusieurs reprises le centre de la structure de recherche et divisent l'espace de recherche en deux. Les algorithmes de recherche de comparaison améliorent la recherche en supprimant successivement les enregistrements sur la base des comparaisons des clés jusqu'à ce que l'enregistrement cible soit trouvé et puisse être appliqué à des structures de données dans un ordre défini.  Les algorithmes de recherche numérique fonctionnent sur la base des propriétés des chiffres dans les structures de données utilisant des clés numériques.  Enfin, hachant cartes directement clés pour les enregistrements à partir d'un hachage fonction.  Les recherches en dehors d'une recherche linéaire nécessitent que les données soient triées d'une manière ou d'une autre.

Les algorithmes sont souvent évalués en fonction de leur complexité de calcul ou de leur temps d'exécution théorique maximal. Les fonctions de recherche binaire, par exemple, ont une complexité maximale de O (log n) ou un temps logarithmique. Cela signifie que le nombre maximal d'opérations nécessaires pour trouver la cible de recherche est une fonction logarithmique de la taille de l'espace de recherche.