1 Où en sommes-nous ? Algorithmes De recherche Backtrack rétrospectifs mixtes Prospectifs FC MAC Quick RFL … Backjumping Backmarking Nogood Recording Conflict

1

Où en sommes-nous ?Où en sommes-nous ?

AlgorithmesDe recherche

Backtrack

rétrospectifs

mixtes

ProspectifsFC MACQuickRFL…

Backjumping Backmarking

Nogood Recording Conflict Directed Backjumping

Dynamic Backtracking…

méthodes structurelles

Classes polynomiales

Réduction de l’espace de recherche

Ordres d’instanciation

CSPDynamiques

CSPStatiques

Compi-lation

VCSP


2

Forward CheckingForward Checking(I, i, a) I=I{(i, a)} supprimer de D toutes les valeurs incompatibles avec i=a sisi il n’existe pas de domaine vide alorsalors choisir choisir jI pour toutpour tout bDj fairefaire ForwardChecking(I, j, b) restaurer les domaines

Enjoliveurs Caisse

Pare-chocs

Capote

Caisse

Pare-chocs

Capote

Enjoliveurs

Forward CheckingAlgorithmes prospectifsAlgorithmes prospectifs

3

Forward Checking – sur les N-reinesAlgorithmes prospectifsAlgorithmes prospectifs

4

Algorithmes prospectifsAlgorithmes prospectifs

Enjoliveurs

Caisse

Pare-chocs

Capote

Enjoliveurs Caisse

Pare-chocs

Capote

BACKTRACKAC puis

BACKTRACK FC

5

Sur contraints

Seuil

Sous contraints

FC

Backtrack

Coût moyen d’une rechercheAlgorithmes prospectifsAlgorithmes prospectifs

6

MACMAC(I, i, a) I=I{(i, a)} supprimer et propager {(i, b) / ba} SiSi il n’existe pas de domaine vide AlorsAlors Choisir Choisir jI pour toutpour tout bDj fairefaire MAC(I, j, b) restaurer les domaines supprimer et propager (i, a)

Caisse

Pare-chocs

Capote

Enjoliveurs

Maintaining Arc ConsistencyAlgorithmes prospectifsAlgorithmes prospectifs

Enjoliveurs Caisse

Pare-chocs

Capote

Enjoliveurs Caisse

Pare-chocs

Capote

Enjoliveurs Caisse

Pare-chocs

Capote

Enjoliveurs Caisse

Pare-chocs

Capote

Enjoliveurs Caisse

Pare-chocs

Capote

Enjoliveurs Caisse

Pare-chocs

Capote

Enjoliveurs Caisse

Pare-chocs

Capote

Enjoliveurs Caisse

Pare-chocs

Capote

Enjoliveurs Caisse

Pare-chocs

Capote

Enjoliveurs Caisse

Pare-chocs

Capote

7

Algorithmes prospectifsAlgorithmes prospectifs

Enjoliveurs

Caisse

Pare-chocs

Capote

Enjoliveurs Caisse

Pare-chocs

Capote

BACKTRACKAC puis

BACKTRACK FC MAC

8

Sur contraints

Seuil

Sous contraints

MAC

FC

Backtrack


9

Quelle consistance locale maintenir pendant la recherche ?Algorithmes prospectifsAlgorithmes prospectifs

pour être rentable, la consistance locale doit avoir un bon rapport coût/puissance : on doit passer moins de temps à détecter qu’une branche ne même à aucune solution qu’à explorer cette branche

Il faut donc :-comparer la puissance des consistances locales-comparer le coût des consistances locales comparer le rapport coût/puissance

10

0.01

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Densité

0.01 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1D u r e t é

Les limites Tall avec n=40 et d=15

PC Forte

AC

PICRPC

Max-RPCSACSRPC

Max-RPCEnConsistanceglobale

Puissance des consistances localesAlgorithmes prospectifsAlgorithmes prospectifs

11 1E-3

AC7

n=200, d=30 et densité=15%

PC forte

1E-2

1E-1

1E0

1E+1

1E+2

1E+3

1E+4

1E+5

1.11 sec

50 60 70 80 90 99403020101

12h 40min

dureté

SRPC2

3h 53min

39min 43sec

SAC6

RPC2

2.44 secMax-RPC18.63 sec

Temps cpu(sec.)

Pentium II266 Mhz

64 Mo

Coût des consistances localesAlgorithmes prospectifsAlgorithmes prospectifs

12

Sur contraints

Seuil

Sous contraints

Quick

MAC

FC

Backtrack


1364

QuickMAC7ps

Dureté

Temps cpu(en secondes) n=200, d=20, 3 voisins, dom/deg

1E-379 94

1E-2

1E-1

1E0

1E+1

1E+2

1E+33.11 min

22 sec

?

Des problèmes exceptionnellement coûteux…Algorithmes prospectifsAlgorithmes prospectifs

146464

QuickMAC7ps

dureté

Temps cpu requis maximum sur 1200 CN générés (en secondes)n=200, d=20, 3 voisins, dom/deg

1E-27979 9494

1E-1

1E0

1E+2

1E+3

1E+4

1E+675 h

49 min

1E+1

1E+5

44 h

15 h

15 s.

1h 29

>12 jours

Des problèmes exceptionnellement coûteux…Algorithmes prospectifsAlgorithmes prospectifs

15



Backtrack

rétrospectifs

mixtes








CSPDynamiques

CSPStatiques

Compi-lation

VCSP


16

Heuristiques sur l’ordre d’instanciationHeuristiques sur l’ordre d’instanciation

Si on s’engouffre dans un branche sans solutions, on peut passerénormément de temps avant de s’en apercevoir

Les premiers choix sont particulièrement importants car on doitpotentiellement faire davantage de backtracks avant de revenir sur eux

Il vaut mieux commencer par instancier les variables les plus Contraintes : -Celles qui ont un petit domaine-Celles qui sont impliquées dans de nombreuses contraintes-Celles qui sont impliquées dans les contraintes les plus dures-… Il vaut mieux commencer par affecter la valeur la plus prometteuse:-Celle qui a le plus de supports-Celle qui a le plus de supports chemin consistants-…

L’ordre sur les variables a plus d’impact que l’ordre sur les valeurs

17


4040 6060 8080 100100 120120 140140 160160

3CL+DomDom + Deg

Dom/Deg

3CL+DomDom + Deg

Dom/Deg1E-11E-1

1E-01E-0

1E+11E+1

1E+21E+2

Temps cpu (en sec.) de FC au seuil pour n de 40 à 160 et D=15Temps cpu (en sec.) de FC au seuil pour n de 40 à 160 et D=15

1E-21E-2

18


4040 6060 8080 100100 120120 140140 160160

1E-11E-1

1E-01E-0

1E+11E+1

1E+21E+2

Temps cpu (en sec.) Quick au seuil pour n de 40 à 160 et D=15Temps cpu (en sec.) Quick au seuil pour n de 40 à 160 et D=15

1E-21E-2

3CL+DomDom + Deg

Dom/Deg

3CL+DomDom + Deg

Dom/Deg

19



Backtrack

rétrospectifs

mixtes








CSPDynamiques

CSPStatiques

Compi-lation

VCSP


20

Une classe polynomialeUne classe polynomiale

Si le graphe des contraintes ne contient pas de cycles, on peut résoudre le CSP sans Backtrack

S’il n’y a pas de cycles : - on réalise la consistance d’arc- la recherche sera sans Backtrack

C’est la principale classe polynomiale mais il y a d’autres classesOù l’on peut constater un nombre limiter de backtracks

21

Uilisation de la structure du graphe : coupe cyclesUilisation de la structure du graphe : coupe cyclesPropriété : Un réseau de contraintes acyclique peut être résolu sans backtracks

Méthode du coupe cycle :Instancier d’abord un ensemble de variables tel qui si on déconnecte ces variables on obtient un réseau de contraintes acyclique

4411

22 33

5566 11

55

Résolution sans retourarrières

Difficulté :- Si le coupe cycle est de grande taille, l ’intérêt est limité- Limite les heuristiques sur l ’ordre d ’instanciation- On ne sait pas trouver rapidement un coupe cycle de taille minimal

22

Uilisation de la structure du graphe : cons. adaptativeUilisation de la structure du graphe : cons. adaptative

4411

22 33

5566

Un graphe des contraintes est ordonné s’il possède un ordre total sur les sommets.La largeur d’un sommet dans un graphe ordonné est le nombre d’arc reliant ce sommet aux sommets précédents. La largeur d’un ordre est la largeur la plus grande parmi celles des sommets

33

55

66

44

22

11

largeur(3, )=3 11

22

44

33

55

66

largeur(2, )=1

largeur(3, )=2

La largeur d’un graphe est le minimum des largeurs sur tous les ordres possibles

largeur()=3 largeur()=2largeur=2

largeur(2, )=1

23

Uilisation de la structure du graphe : cons. adaptativeUilisation de la structure du graphe : cons. adaptative

4411

22 33

5566

33

55

66

44

22

11

Un ordre d’instanciation garantit une recherche sans retour arrière si le niveau de K-consistance forte est supérieur à la largeur de cet ordre.

Un réseau est k-consistant ssi toute instanciation de longueur (k-1) peut être étenduà n’importe quelle kième variable (2-Consistance consistance d’arc)

Avec un ordre de largeur 2, la 3-consistance forte est nécessaire. Problèmes : - la réalisation de la k-consistance exige un temps exponentiel en k.- la réalisation de la k-consistance peut entraîner l ’ajout de contraintes (k-1)-aires et donc modifier la largeur de l ’ordre (et même du graphe).

Consistance adaptative : adapter le niveau de k-consistance à chaque sommet.- On considère les sommets dans l ’ordre inverse- Soit k la largeur du sommet ; on réalise la (k+1)-consistance entre les sommets qui le précède dans l ’ordre et lui même. L’ordre est backtrack-free

Problèmes :- la complexité de la k-consistance.- l’ordre d’instanciation est statique.

24



Backtrack

rétrospectifs

mixtes








CSPDynamiques

CSPStatiques

Compi-lation

VCSP


25

==

==

Besoin d’interactivité

CSP DynamiquesCSP Dynamiques

CSP Statiques : L’ensemble des contraintes ne change pas

- trouver une solution / toutes les solutions

Problèmes intrinsèquement dynamiques : - emplois du temps, scheduling, design, ...

Si le CSP est sur-contraint Optimisation- trouver une solution optimale vis-à-vis d’un critère sur les contraintes

Rarement satisfaisant

26

++

==

++

==

==

++

==

==

++

==

==

==

--

==

-- ++

====

++

Maintien d’une consistance localeCSP DynamiquesCSP Dynamiques

27

++

==

++

==

==

++

==

==

++

==

++

====

++


1ère Solution : -Pour supprimer une contrainte,on repart du réseau sans contraintes

On doit pouvoir faire mieux !

++

==

==

==

++

++

==

==

==

++

++==

28

++

==

++

==

==

++

==

==

++

==

++

====

++


2ème Solution : -On mémorise l’état du réseauAvant chaque ajout On ne repart pas toujours De zéro

On doit pouvoir faire mieux !

==

==

==

++

++

==

==

==

++

++==

29

==


3ème Solution : utiliser un système de justifications

==

==

++

==

++

++==

==

==

--

30

==

==


--

==

On remet les valeurs justifiées par la contrainte supprimée

==

On propage les valeurs remises

==

On vérifie la consistance locale des valeurs remises

31



Backtrack

rétrospectifs

mixtes








CSPDynamiques

CSPStatiques

Compi-lation

VCSP


32

Exemple montrant le thrashingLe thrashingRecherche rétrospectiveRecherche rétrospective

6655

11

22 33

44

33

Le thrashingRecherche rétrospectiveRecherche rétrospective

6655

11

22 33

44

11 22 33 44 6655

Exemple montrant le thrashing

Initiation à la Programmation Logique avec Contraintes

Dynamic BacktrackingChaque échec sur le choix d’une valeur est expliqué par les précédents choix qui entre en conflit. Si toutes les valeurs d’un domaine ont été testées sans succès, l’explication de cet échec est l’union des explications des valeurs du domaine et on revient sur l’instanciation la plus récente de cette explication.

Conflict directed BackJumping (CBJ)Idem mais lors d’un saut on supprime également les instanciations intermédiaires.

35

Dynamic Backtracking [Ginsberg, 93]Dynamic Backtracking [Ginsberg, 93]

- Instancier i à a Ajout de Ci:(i=a)

- Explication d’une information I = ensemble de contraintes tel que I demeure vérifiée tant que ces contraintes figurent dans le système

11 22 33 44 55

C25 expl(5 )=C2

C15 expl(5 )=C1

C25 expl(5 )=C2

expl(D5=)={C1 ,C2}

6655

11

22 33

44

36

Conflict Directed BackjumpingConflict Directed Backjumping

6655

11

22 33

44

11 22 33 44 6655

Réduction partielleRéduction partielledu thrashingdu thrashing

37

Dynamic BacktrackingDynamic Backtracking

6655

11

22 33

44

11 22 33 44 6655

33 44 22

- Plus une réparation qu’un saut- Plus une réparation qu’un saut

- Additif sur les sous-problèmes - Additif sur les sous-problèmes indépendantsindépendants

- Compense « automatiquement »- Compense « automatiquement » certaines lacunes de l’heuristi-certaines lacunes de l’heuristi- que sur l’ordre d’instanciationque sur l’ordre d’instanciation

38

Dynamic BacktrackingDynamic Backtracking

33

- Compense « automatiquement »- Compense « automatiquement » certaines lacunes de l’heuristi-certaines lacunes de l’heuristi- que sur l’ordre d’instanciationque sur l’ordre d’instanciation

6644

77 99

8855

2211

55

9977

6644

88

39

Les explicationsLes explications

Le coût spatial des explications est en O(n2d) pour un CNde n variables ayant d pour taille maximale des domaines mais l’espace requis en moyenne est loin de ce pire cas

Le coût spatial des explications est en O(n2d) pour un CNde n variables ayant d pour taille maximale des domaines mais l’espace requis en moyenne est loin de ce pire cas

Les explications permettent également - de posséder une explication des retraits ce qui peut être précieux pour la mise au point- le traitement des problèmes sur-contraints et la résolution interactive

Les explications permettent également - de posséder une explication des retraits ce qui peut être précieux pour la mise au point- le traitement des problèmes sur-contraints et la résolution interactive

40

Deux grandes familles d’améliorationsDeux grandes familles d’améliorations

MAC-DBTMAC-DBTMAC-DBTMAC-DBT

DBTDBTDBTDBT

MAC-CBJMAC-CBJMAC-CBJMAC-CBJ

MACMACMACMAC

FCFCFCFC

BTBTBTBT

CBJCBJCBJCBJ

FC-CBJFC-CBJFC-CBJFC-CBJ

FC-DBTFC-DBTFC-DBTFC-DBT

Reche

rche

en

Avant Recherche en Arrière

Documents

1 Où en sommes-nous ? Algorithmes De recherche Backtrack rétrospectifs mixtes Prospectifs FC MAC Quick RFL … Backjumping Backmarking Nogood Recording Conflict