Planification Et Problèmes Np-difficiles Flashcards
(48 cards)
Problème de planification
Modéliser un problème de planification
Graphe d’états (aussi appelé graphe états-transitions)
- Les sommets du graphe sont les états
- Les arcs correspondent aux transitions possibles entre états, et sont étiquetés par les actions
Graphe orienté ou non selon que les transitions sont symétriques ou non
Quels algorithmes utiliser pour…
Déterminer s’il existe un plan d’actions?
Chercher le plan d’action minimisant le nombre d’actions ?
Chercher le plan d’action minimisant la somme des coûts ?
Compter le nombre de plans d’actions différents possibles?
En général, le graphe d’états est trop gros pour pouvoir être construit
Construire le graphe au fur et à mesure de la recherche du chemin
Heuristique
Règle empirique, permettant de résoudre “approximativement” un problème -> sans garantie sur la qualité de la solution, mais rapide
Adaptons Dijkstra pour chercher le plan d’action le moins coûteux
Algorithme A*
1 fermés ← ∅ ; ouverts ← {einit } ; g[einit ] ← 0
2 tant que ouverts 6 = ∅ faire
3 Soit ei l’état de ouverts minimisant g[ei ] + h[ei ]
4 si ei ∈ F alors retourne (g[ei ], π);
5 pour tout a ∈ actions(ei ) faire
6 ej ← t(ei , a)
7 /* Ne pas ignorer les états fermés ! */
8 si g[ei ] + cout(a) < g[ej ] alors
9 g[ej ] ← g[ei ] + cout(a)
10 π[ej ] ← ei
11 si ej 6 ∈ ouverts alors Ajouter ej ds ouverts;
12 Retirer ei de ouverts et l’ajouter dans fermés
13 retourne Pas de plan !Changement de terminologie entre Dijkstra et A* :
- Sommets gris –> Etats ouverts (open, fringe, frontier)
- Sommets noirs –> Etats fermés (closed)
- Sommets blancs –> Etats ni ouverts ni fermés
(g[ei ] = ∞ pour tout état ei ni ouvert ni fermé)
Condition pour que A* retourne une solution optimale
h doit être admissible
Une heuristique est admissible si
∀e ∈ E, h(e) ≤ minf ∈F δ(e, f )
Condition pour que chaque arc soit relâché au plus une fois
h doit être cohérente
Une heuristique est cohérente si
∀ei ∈ E, ∀a ∈ actions(ei ) : h(ei ) ≤ cout(a) + h(t(ei , a))
Si h n’est pas admissible
A* trouve un chemin sous-optimal en
développant moins d’états
Weighted A* (WA*)
1 Fonction WA*(E, F , A, e_init , actions, t, h, w)
2 fermés ← ∅ ; ouverts ← {e_init } ; g[e_init ] ← 0
3 tant que gris 6 = ∅ faire
4 Soit ei l’état de ouverts minimisant g[ei ] + w ∗ h[ei ]
5 si ei ∈ F alors retourne (g[ei ], π);
6 pour tout a ∈ actions(ei ) faire
7 ej ← t(ei , a)
8 si g[ei ]+cout(a) < g[ej ] alors
9 g[ej ] ← g[ei ] + cout(a)
10 π[ej ] ← ei
11 si ej 6 ∈ ouverts alors Ajouter ej dans ouverts;
12 Retirer ei de ouverts et l’ajouter dans fermés
13 retourne Pas de plan !Le paramètre w
permet de choisir un compromis entre qualité et durée (w + => durée - mais qualité - w)
Anytime Weighted A* (AWA*)
1 Fonction AWA*(E, F , A, einit , actions, t, h, w)
2 fermés ← ∅ ; ouverts ← {einit } ; g[einit ] ← 0 ; borne ← ∞
3 tant que ouverts 6 = ∅ faire
4 Soit ei l’état de ouverts minimisant g[ei ] + w ∗ h[ei ]
5 pour tout a ∈ actions(ei ) faire
6 ej ← t(ei , a)
7 si g[ei ]+cout(a) < g[ej ] alors
8 g[ej ] ← g[ei ] + cout(a)
9 π[ej ] ← ei
10 si ej ∈ F alors borne ← g[ej ] ; Afficher borne ;
11 sinon si g[ej ] + h[ej ] < borne alors Ajouter ej dans ouverts;
12 Retirer ei de ouverts et l’ajouter dans fermés
13 retourne borne
Spécification d’un problème
Paramètres en entrée (avec éventuellement préconditions) et en sortie
Postrelation entre les valeurs des paramètres en entrée et en sortie
Instance d’un problème
Valuation des paramètres en entrée satisfaisant les préconditions
Algorithme pour un problème P
Séquence d’instructions élémentaires permettant de calculer les valeurs des paramètres en sortie
à partir des valeurs des paramètres en entrée, pour toute instance de P
SAT
Satisfiabilité d’une formule booléenne (SAT)
Spécification du problème :
Entrées : une formule booléenne F définie sur un ensemble X de n variables
Sortie : un boolean B
Précondition : F est sous forme normale conjonctive (CNF)
Postrelation : F est satisfiable ⇔ B = vrai
Complexité d’algorithme
Estimation des ressources nécessaires à l’exécution d’un algorithme
- en temps = du nombre d’instructions élémentaires
- en espace = de l’espace mémoire utilisé
NB : dépendante de la taille n des paramètres en entrée
