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.
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 et qui exploitent les propriétés de la structure de données .
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). Deux autres exemples sont la recherche séquentielle et la recherche par interpolation.
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é.
On parle de recherche heuristique 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.
Ces algorithmes sont au centre de questions importantes en complexité algorithmique.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
L'objectif de ce cours est d'introduire les étudiants à la pensée algorithmique, de les familiariser avec les fondamentaux de l'Informatique et de développer une première compétence en programmation (
Through a combination of lectures, seminar, and practical workshops, this course serves as an introduction to critical digital humanities and algorithmic critique, and is specifically tailored for res
Dans une première partie, nous étudierons d’abord comment résoudre de manière très concrète un problème au moyen d’un algorithme, ce qui nous amènera dans un second temps à une des grandes questions d
Dans une première partie, nous étudierons d’abord comment résoudre de manière très concrète un problème au moyen d’un algorithme, ce qui nous amènera dans un second temps à une des grandes questions d
L'apprentissage automatique (en anglais : machine learning, « apprentissage machine »), apprentissage artificiel ou apprentissage statistique est un champ d'étude de l'intelligence artificielle qui se fonde sur des approches mathématiques et statistiques pour donner aux ordinateurs la capacité d'« apprendre » à partir de données, c'est-à-dire d'améliorer leurs performances à résoudre des tâches sans être explicitement programmés pour chacune. Plus largement, il concerne la conception, l'analyse, l'optimisation, le développement et l'implémentation de telles méthodes.
vignette|Diagramme de recherche séquentielle La recherche séquentielle ou recherche linéaire est un algorithme pour trouver une valeur dans une liste. Elle consiste simplement à considérer les éléments de la liste les uns après les autres, jusqu'à ce que l'élément soit trouvé, ou que toutes les cases aient été lues. Elle est aussi appelée recherche par balayage. La recherche séquentielle consiste à prendre les éléments de la liste les uns après les autres, jusqu'à avoir trouvé la cible, ou avoir épuisé la liste.
En informatique, plus précisément en intelligence artificielle et en théorie des jeux, l’élagage alpha-bêta (abrégé élagage αβ) est une technique permettant de réduire le nombre de nœuds évalués par l'algorithme minimax. Il est utilisé dans des programmes informatiques qui jouent à des jeux à 2 joueurs, comme les échecs ou les dames. L'algorithme minimax effectue une exploration complète de l'arbre de recherche jusqu'à un niveau donné. L'élagage alpha-beta permet d'optimiser grandement l'algorithme minimax sans en modifier le résultat.
We introduce an algorithm to reconstruct a mesh from discrete samples of a shape's Signed Distance Function (SDF). A simple geometric reinterpretation of the SDF lets us formulate the problem through a point cloud, from which a surface can be extracted wit ...
2024
, ,
In this paper, we study sampling from a posterior derived from a neural network. We propose a new probabilistic model consisting of adding noise at every pre- and post-activation in the network, arguing that the resulting posterior can be sampled using an ...
Bristol2024
, ,
This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...