INF4230 – Intelligence Artificielle Algorithme A*
– Ajout d'une heuristique. • A* et les heuristiques sont à la base de beaucoup de travaux en IA: – Recherche de
Chapitre 8 : Introduction aux méthodes heuristiques
Méta-heuristiques : algorithmes d'optimisation (généralement de type Méthode heuristique en programmation dynamique : Algorithme A?.
Intelligence Artificielle Heuristique
Algorithmes et recherches heuristiques. Recherche meilleur d'abord. Recherche gloutonne. L'algorithme A?. Algorithmes de recherche locale.
Les méthodes de résolution approchées pour le Programmation en
2 Les algorithmes approchés : heuristiques Définition 2 : Un algorithme de résolution Heuristique est un algorithme qui fournit une solution réalisable ...
Méta-heuristiques
Les algorithmes génétiques reprennent ces mécanismes pour définir une méta- heuristique de résolution de problèmes d'optimisation combinatoire. L'idée est.
Algorithmes gloutons Problèmes doptimisation. Problèmes d
sous-problèmes) : heuristique de choix. Algorithmes gloutons – Stéphane Grandcolas – p.6. Algorithmes gloutons. Un algorithme glouton construit une solution
Algorithmes heuristiques et exacts pour le probleme de lensemble
Algorithmes heuristiques et exacts pour le probl`eme de l'ensemble dominant connexe minimum par. Sofiane Soualah. Département d'informatique et de recherche
Les Méthodes Hybrides en Optimisation Combinatoire:Algorithmes
28 avr. 2006 2.1 – Heuristique gloutonne pour le KP. 2.2.2 Calcul de bornes supérieures et élément critique. Calculer des bornes supérieures ou inférieures ( ...
Heuristique DSATUR
des exemples d'application nous aborderons le problème du temps de calcul de certains algorithmes
Coopération méta heuristique et logique floue pour le
Pour cela nous utilisons une approche pour la génération de base de r`egles floues et une optimisation automatiques au moyen d'algorithme génétique et d'un PSO
[PDF] INF4230 – Intelligence Artificielle Algorithme A* - GDAC
une heuristique est une méthode (~algorithme) qui calcule rapidement (ex: en temps constant linéaire ou polynomiale) une solution pouvant être approximative
[PDF] Intelligence Artificielle Heuristique - Université Paris Cité
Algorithmes et recherches heuristiques Recherche meilleur d'abord Recherche gloutonne L'algorithme A? Algorithmes de recherche locale
[PDF] Chapitre 8 : Introduction aux méthodes heuristiques
Quelques méthodes heuristiques 1 Algorithme A? 2 Recuit simulé 3 Algorithmes génétiques 4 Algorithme de colonies de fourmis
[PDF] Heuristiques
Dans cet algorithme la file contient des chemins issus de la racine à chaque étape on défile le chemin le plus prioritaire et on l'étend par les différentes
[PDF] Algorithmes de recherche heuristique - Free
Les algorithmes de recherche aveugle ou "non-informés" – n'exploitent aucune information présente dans l'arbre de recherche pour optimiser la recherche
[PDF] Cours des Méthodes de Résolution Exactes Heuristiques et
1 1 1 Introduction Si les méthodes de résolution exactes permettent d'obtenir une En optimisation combinatoire une heuristique est un algorithme ap-
[PDF] Algorithmes Heuristiques et Techniques dApprentissage
6 mai 2010 · Chapitre 1 Introduction 1 1 Probl`emes difficiles et algorithmes heuristiques Une instance d'un probl`eme d'optimisation combinatoire est
[PDF] Algorithmes de recherche informés - Irif
Les heuristiques • Algorithmes de recherche locale 1 Cours Intelligence Artificielle 2005-2006 Peter Habermehl Recherche meilleur d'abord
[PDF] Algorithmes Heuristiques et Evolutionnistes - Université de Lille
24 juil 2022 · 1! 4 2 Algorithme R8 : Introduction aux principes intéressons aux méthodes de résolution appliquées au format existant des formes
Algorithmes Et Recherches Heuristiques PDF - Scribd
Elise Bonzon (Université Paris Descartes) Intelligence artificielle Licence 3 Informatique 1 / 23 Algorithmes et recherches heuristiques
C'est quoi la méthode heuristique ?
La méthode heuristique repose sur une évaluation quasi continue, principalement formative. L'acquisition des notions est évaluée lors des observations de l'enseignant. L'évaluation s'appuie sur des critères explicites et partagés avec les élèves.Comment calculer l'heuristique ?
Cet algorithme utilise une heuristique qui calcule pour chaque nœud n le coût chemin g(n) depuis l`état initial jusqu'au nœud n. Le coût chemin g(n) est une fonction croissante le long d`un chemin : chacune n dans E, s dans Successeurs(n), g(n) <= g(s).Comment savoir si une heuristique est admissible ?
L'heuristique admissible Dans la science informatique, en particulier dans les algorithmes liés à pathfinding, une fonction heuristique est dite admissible si elle surestime jamais le coût pour atteindre l'objectif, à savoir que le coût qu'il estime pour atteindre l'objectif ne dépasse pas le coût le plus bas possible- h1 et h2 admissible implique pour tout noeud n h1(n) ? h?(n) et h2(n) ? h?(n). Donc pour tout noeud n on a max(h1(n),h2(n)) ? h?(n) donc max(h1,h2) est admissible.
INF4230 - Intelligence Artificielle
Recherche heuristique /
Algorithme A*
Hiver 2017
Sommaire
Rappels :
Agents.
Résolution de problème par recherche.
Espace d'Ġtats.
Recherche informée.
Recherche "meilleur en premier».
Algorithme A*.
Heuristiques.
Propriétés de A*.
INF4230 - Intelligence artificielle 2
Rappel : Agents rationnels
Agent :
Perçoit son environnement.
Agit dans son environnement
Se fait une représentation du monde (modèle).Mesure de performance.
(Modèle PEAS).Un agent a une fonction f: P* AE A .
INF4230 - Intelligence artificielle 3
Rappel : Environnements
Complètement observable vs partiellement
observable.Déterministe vs stochastique.
Épisodique vs séquentiel.
Statique vs dynamique.
Discret vs continu.
Agent unique vs multi-agent.
Quasi synonymes : environnement et monde
(world).INF4230 - Intelligence artificielle 4
Rappel : Paradigme de résolution de problème La fonction f d'un agent peut ġtre implĠmentĠe ă l'aide du paradigme ͨrĠsolution de problğmes par recherche». Construction d'un modğle du monde ă l'aide des données sensorielles provenant des capteurs. Un graphe est Ġtendu ă partir de l'Ġtat initial Les décisions séquentielles sont sélectionnées à l'aide d'une recherche dans un graphe.INF4230 - Intelligence artificielle 5
Rappel : Types de problème
Déterministe + Complètement observable AE problème àL'agent sait tout et peut simuler ses actions.
Non déterministe et/ou observabilité partielle AE problème de contingence. Solution = Plan contingent; Alternance recherche et exécution. Non observable AE problème sans capteurs ou problème de conformance (conformant planning). L'agent n'a aucune idĠe de son enǀironnement. Espace d'Ġtats inconnu AE problğme d'edžploration.INF4230 - Intelligence artificielle 6
Rappel : Agent basé sur des buts
INF4230 - Intelligence artificielle 7
Exemple 1 - Agent sur une carte
v0 v3 v2 v1 v4 v6 v5 2 3 1 1 7 2 4 4 4Monde:
Villes et routes.
Problème posé (état_initial, but):
v0: ville de départ (état initial) v6: destination (but)INF4230 - Intelligence artificielle 8
Exemple 2 - Jeu de taquin (puzzle)
1 2 3 4 5 7 6 8 8 1 3 4 5 7 6 2 ? 1 2 3 4 5 7 6 8 1 2 3 4 5 7 6 8 1 2 3 4 5 7 6 8 1 2 3 4 5 7 6 8 1 2 3 4 5 7 6 8 1 2 3 4 5 7 6 8Nord Sud Ouest Nord Est
INF4230 - Intelligence artificielle 9
RECHERCHE INFORMÉE
INF4230 - Intelligence artificielle 10
Algorithme Meilleur en premier
(Best-First-Search)La définition varie selon les auteurs :
Dans le livre de Norvig et Russell :
"Greedy Best-First-Searchͩ т ͨBest-First-Search» "Greedy Best-First-Search» (GBFS) est une recherche locale у hill climbing (chapitre 4). "Best-First-Search» est une recherche globale. Idée = choisir le prochain état qui "semble» le plus près du but (meilleur).Ce choix est fait par une (fonction) heuristique.
INF4230 - Intelligence artificielle 11
Dans divers domaines, dont en informatique,
une heuristique est une méthode (~algorithme) qui calcule rapidement (ex: en temps constant, linéaire ou polynomiale) une solution pouvant être approximative et incomplète à un problème généralement trop complexe.INF4230 - Intelligence artificielle 12
Algorithme de recherche en IA /
Fonction heuristique
Estimation de la distance (coût restant) entre unétat n et un but g.
Le but g peut être implicite.
Généralement notée h ou h(n).
h(n) : estime le coût restant pour atteindre le butExemple de fonctions heuristiques pour la
navigation dans sur une carte : Distance euclidienne (aussi appelĠe ă ǀol d'oiseau).Distance de Manhattan (ville quadrillée).
INF4230 - Intelligence artificielle 13
Greedy Best-First-Search
Algorithme :
1.GBFS(n) :
2. tant que n ne satisfait pas le but
3. S Å Successeurs(n)
4. n' Å choisir n' dans S ayant le plus petit h(n')
5. si n' с n alors CHEC
6. n Å n'
INF4230 - Intelligence artificielle 14
Exemple de GBFS sur une carte
52e rue
51e rue
50e rue
10 th Ave9e ave
8e ave
7e ave
6e ave
5e ave
4e ave
3e ave
2e ave
S G53e rue
(Adaptée d'une illustration par Henry Kautz, U. of Washington)INF4230 - Intelligence artificielle 15
Best-First-Search
Algorithme :
1.BFS(n0) :
2. open Å {n}
4. n Å choisir dans open qui minimise h(n)
5. si n satisfait le but, alors retourner solution
6. ajouter successeurs(n) dans open
INF4230 - Intelligence artificielle 16
Exemple de GBFS sur une carte
52e rue
51e rue
50e rue
10 th Ave9e ave
8e ave
7e ave
6e ave
5e ave
4e ave
3e ave
2e ave
S G53e rue
(Adaptée d'une illustration par Henry Kautz, U. of Washington)INF4230 - Intelligence artificielle 17
Algorithme A*
A* est une edžtension de l'algorithme de Dijkstra. A* et les heuristiques sont à la base de beaucoup de travaux en IA:Recherche de meilleures heuristiques.
Heuristiques indépendantes du problème.
Pour décrire A*, on décrit un algorithme
générique très simple, dont A* est un cas particulier.INF4230 - Intelligence artificielle 18
Variables importantes : open et closed
open : présent dans le graphe. closed : c'est ă dire ă l'intĠrieur de la frontiğre dĠlimitĠe par open.INF4230 - Intelligence artificielle 19
Une fonction f(n) donne ou estime la qualité de la meilleure par n, et arriǀant dans un Ġtat n' satisfaisant le but g.INF4230 - Intelligence artificielle 20
Définition de la fonction f(n)
Par contre on connaît la distance optimale dans la partie explorée entre le Ainsi, on peut séparer f(n) en deux parties: f(n) = g(n) + h(n) la partie déjà explorée. satisfaisant le but. h(n) est une fonction heuristique.INF4230 - Intelligence artificielle 21
Algorithme générique de recherche dans un grapheAlgorithme rechercheDansGraphe(n0)
1.open ÅCréer un ensemble ordonnées par f(n) // vide au départ
2.closed Å Créer un ensemble // vide au départ
3.insérer n0 dans open
4.while (true) // la condition de sortie (exit) est déterminée dans la boucle
5.si open
6.n1 = noeud au début de open avec le plus petit f(n)
7.enlever n1 de open closed
8.si n1 est le but, sortir de la boucle avec succès en retournant le chemin;
9.pour chaque noeud successeur n2 de n1
10.Initialiser la valeur g(n2) = g(n1) + coût de la transition (n1,n2)
11.mettre parent(n2) = n1
12.si open ou closed*
f(n2)14.insèrer n2 dans open
INF4230 - Intelligence artificielle 22
Exemple A* avec recherche dans une ville
v0 v3 v2 v1 v4 v6 v5 9 2 3 2 2 5 0 2 3 1 1 7 2 4 4 4 h(v0) c(v0,v1)Routes entre les villes :
v0: ville de départ v6: destination h: distance à vol C: distance réelle entre deux ville 1. (v0, 9, void)Contenu de closed à la sortie
(noeud, f) : (v4,6), (v3,7), (v2,5), (v1,5), (v0,9)Contenu de open à chaque
itération (état, f, parent) :2. (v1,5,v0) (v2,6,v0), (v3,7,v0)
3. (v2,6,v0) (v3,7,v0), (v5,12,v1)
4. (v3,7,v0),(v4,9,v2),(v5,12,v1)
5. (v2,5,v3),(v4,6,v3),(v5,12,v1)
6. (v4,6,v3),(v5,12,v1)
7. (v6,7,v4), (v5,12,v1)
8. Solution: v0,v3,v4,v6
INF4230 - Intelligence artificielle 23
Exemple de recherche avec A*
52e rue
51e rue
50e rue
10 th Ave9e ave
8e ave
7e ave
6e ave
5e ave
4e ave
3e ave
2e ave
S G53e rue
f=6+2 f=1+7 f=7+3 (Illustration par Henry Kautz, U. of Washington)INF4230 - Intelligence artificielle 24
Non-optimalité de Best-First Search
52e rue
51e rue
50e rue
10 e ave9e ave
8e ave
7e ave
6e ave
5e ave
4e ave
3e ave
2e ave
S G53e rue
Solution par Best-first-Search
Solution optimale par A*
(Illustration par Henry Kautz, U. of Washington)INF4230 - Intelligence artificielle 25
Démos
Simulation des algorithmes :
A*, Recherche en profondeur, largeur, meilleur en premier http://ericbeaudry.ca/INF4230/demos/search/ (Applet Java)INF4230 - Intelligence artificielle 26
JEU DE TAQUIN
INF4230 - Intelligence artificielle 27
Jeu de taquin
État: configuration légale du jeu
État initial: configuration initiale
État final (but): configuration gagnante
Transitions (fonction successeur)
1 2 3 4 5 7 6 8 8 1 3 4 5 7 6 2 1 2 3 4 5 7 6 8 1 2 3 4 5 7 6 8 . . . Nord 1 2 3 4 5 7 6 8 Est Ouest SudINF4230 - Intelligence artificielle 28
Heuristiques pour jeu de taquin
quotesdbs_dbs44.pdfusesText_44[PDF] structure fonctionnelle d'un système automatisé
[PDF] méthodes heuristiques d'optimisation
[PDF] définition d'un système automatisé de production
[PDF] méthodes heuristiques et métaheuristique d'optimisation
[PDF] méthode heuristique optimisation
[PDF] système automatisé de production sap
[PDF] les métaheuristiques en optimisation combinatoire
[PDF] système automatisé de production pdf
[PDF] système automatisé de production ppt
[PDF] cours aide soignante module 1 pdf
[PDF] qcm module 1 aide soignante gratuit
[PDF] cours aide soignante module 2
[PDF] module 1 aide soignante résumé
[PDF] les 8 modules aide soignante