Heuristique (mathématiques) | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Au sens le plus large, l'heuristique est la psychologie de la découverte, abordée par différents mathématiciens. En algorithmique, une heuristique est une méthode de calcul qui fournit rapidement une solution réalisable, pas nécessairement optimale ou exacte, pour un problème d'optimisation difficile. On distingue en général plusieurs temps la prise en compte du problème (question, contexte : données, contraintes, acteurs, tenants et aboutissants) l'incubation, recherche de solution, rumination parfois très longue ; la méthode du problème résolu peut ici dégager les conditions nécessaires à respecter. l'illumination (ou découverte de solution) l'explicitation, qui descend dans les détails la validation (qui doit relancer le processus en cas d'échec) Pólya a abordé ces questions sous l'angle des mathématiques. Il distingue les niveaux opératoires, tactiques et stratégiques. Le premier regroupe des savoir-faire élémentaires, le dernier est le plus intuitif et le plus difficile. Mais l'expérience rend les niveaux inférieurs de plus en plus riches et efficaces. Une fois le problème bien cerné (question, contexte : données, contraintes, tenants et aboutissants), selon les cas c'est un problème connu (ou un cas particulier) ; c'est un problème qu'on peut ramener à une combinaison de problèmes plus simples ; c'est un problème ressemblant à un problème qu'on sait traiter. Le premier cas se produit d'autant plus souvent qu'on a plus d'expérience ; Le second cas correspond à une , et utilise le Le troisième cas est , fertile mais incertain, car les problèmes analogues ont souvent, mais pas toujours, des solutions analogues ; de plus, si l'analogie est trop lointaine, on peut devoir la fragmenter en plusieurs stades intermédiaires. Finalement, lorsqu'un plan d'action a été trouvé, on l'explicite pour le mettre en œuvre. Si le résultat n'est pas bon, on remet en cause la démarche. Si le résultat est correct, il est bon de voir si on peut faire mieux, plus efficace ou plus général, afin d'enrichir son expérience.

À propos de ce résultat

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.

Publications associées (12)

Personnes associées (5)

Concepts associés (23)

Cours associés (11)

Séances de cours associées (35)

MGT-530: Digitalization & sustainable logistics

In this course, we address quantitatively the operational aspects linked to the management of supply chains. Focusing on practical situations, focus will be paid on the optimization of logistics syste

MATH-600: Optimization and simulation

Master state-of-the art methods in optimization with heuristics and simulation. Work involves:

reading the material beforehand
class hours to discuss the material and solve problems
homework

CS-450: Advanced algorithms

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a reper

Couvre la planification avec des adversaires, des algorithmes de recherche heuristique et des stratégies pour les jeux avec le hasard, en soulignant l'importance des agents délibératifs.

Explore l'optimisation accélérée de l'ordre de jointage GPU dans les grands espaces de recherche, en tirant parti de la topologie graphique pour réduire les frais généraux de calcul.

Plonge dans le jeu de cordes, montrant les limites des tests exhaustifs et l'importance de l'heuristique dans la résolution de problèmes.

, , ,

Modern data analytical workloads often need to run queries over a large number of tables. An optimal query plan for such queries is crucial for being able to run these queries within acceptable time b

2022

Efficient GPU-accelerated Join Optimization for Complex Queries

Anastasia Ailamaki, Bikash Chandra, Srinivas Karthik Venkatesh, Riccardo Mancini

Analytics on modern data analytic and data warehouse systems often need to run large complex queries on increasingly complex database schemas. A lot of progress has been made on executing such complex

IEEE2022

Optimised Heat Pump Management for Increasing Photovoltaic Penetration into the Electricity Grid

Christophe Ballif, Lionel Benjamin Bloch, Jordan Holweger, Cristian Sanchez Perez

Advanced control of heat pumps with thermal storage and photovoltaics has recently been promoted as a promising solution to help decarbonise the residential sector. Heat pumps and thermal storage offe

2019

Algorithme de recherche best-first

La recherche best-first (littéralement : le meilleur en premier) est un algorithme de recherche qui parcourt un graphe en explorant le nœud le plus "prometteur" selon une règle spécifique. Judea Pearl décrit la recherche best-first comme l'estimation de la qualité d'un nœud n par une "fonction heuristique d'évaluation qui, en général, peut dépendre de la description de n, de l'état d'arrivée, des informations amassées par l'algorithme au moment de l'évaluation et, surtout, de connaissances supplémentaires à propos du problème".

Problème NP-complet

En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de l

Algorithme A*

En informatique, plus précisément en intelligence artificielle, l'algorithme de recherche A* (qui se prononce A étoile, ou A star en anglais) est un algorithme de recherche de chemin dans un graphe entre un nœud initial et un nœud final tous deux donnés. En raison de sa simplicité il est souvent présenté comme exemple typique d'algorithme de planification, domaine de l'intelligence artificielle.