Navigation : << CSP-1-Fondamentaux | Index | CSP-3-Avance >>
Ce notebook explore les techniques de propagation de contraintes qui permettent de reduire l’espace de recherche avant et pendant la resolution d’un CSP. Au lieu de simplement verifier les contraintes après chaque assignation (backtracking), ces techniques eliminent proactivement les valeurs impossibles des domaines.
A la fin de ce notebook, vous saurez : 1. Distinguer les niveaux de consistance : noeud, arc, chemin 2. Implementer l’algorithme AC-3 pour la consistance d’arc 3. Integrer le Forward Checking avec le backtracking 4. Combiner AC-3 et backtracking dans l’algorithme MAC 5. Comparer experimentalement Backtracking, FC et MAC
Voir les notebooks App-6 (Minesweeper) et App-7 (Wordle) pour des applications utilisant la consistance d’arc.
Dans le notebook précédent (CSP-1), nous avons vu que le backtracking detecte les conflits au moment de l’assignation. Cependant, il ne tire pas pleinement parti de la structure des contraintes : il attend de tenter une assignation pour decouvrir un conflit.
Idee cle : au lieu d’attendre passivement, on peut propager les consequences de chaque assignation pour eliminer des valeurs impossibles dans les domaines des autres variables. C’est la propagation de contraintes.
| Approche | Cout de propagation | Reduction de l’espace | Quand l’utiliser |
|---|---|---|---|
| Backtracking pur | Aucun | Minimale | Petits problemes |
| Forward Checking | Faible | Moderee | Problemes moyens |
| AC-3 seul | Modere | Forte | Pre-traitement |
| MAC (AC-3 + BT) | Eleve | Maximale | Problemes difficiles |
La consistance peut etre assuree a différents niveaux, du plus simple au plus fort :
\[\text{Node Consistency} \subset \text{Arc Consistency} \subset \text{Path Consistency} \subset \text{k-Consistency}\]
Plus le niveau est fort, plus l’elagage est important, mais plus le cout de propagation est eleve.
# Imports pour tout le notebook
import sys
import copy
import time
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
import numpy as np
from collections import deque
# Helpers partages de la serie Search
sys.path.insert(0, '..')
from search_helpers import draw_csp_graph, benchmark_table, plot_benchmark
%matplotlib inline
print("Imports OK")Imports OKNous reutilisons la classe CSP définie dans le notebook précédent, avec quelques méthodes supplementaires pour la propagation.
class CSP:
"""Probleme de Satisfaction de Contraintes (CSP).
Represente un CSP binaire avec variables, domaines, voisins
et une fonction de contrainte.
"""
def __init__(self, variables, domains, neighbors, constraint_func):
self.variables = variables
self.domains = {v: list(d) for v, d in domains.items()}
self.neighbors = neighbors
self.constraint_func = constraint_func
self.n_assigns = 0
self.n_backtracks = 0
def consistent(self, var, val, assignment):
"""Verifie si (var=val) est consistant avec l'assignation partielle."""
for other_var in self.neighbors[var]:
if other_var in assignment:
if not self.constraint_func(var, val, other_var, assignment[other_var]):
return False
return True
def is_complete(self, assignment):
"""Verifie si toutes les variables sont assignees."""
return len(assignment) == len(self.variables)
def is_solution(self, assignment):
"""Verifie si l'assignation est une solution (complete et consistante)."""
if not self.is_complete(assignment):
return False
for var in self.variables:
if not self.consistent(var, assignment[var], assignment):
return False
return True
def reset_counters(self):
"""Reinitialise les compteurs."""
self.n_assigns = 0
self.n_backtracks = 0
def copy_domains(self):
"""Retourne une copie profonde des domaines."""
return {v: list(d) for v, d in self.domains.items()}
def get_arcs(self):
"""Retourne la liste de tous les arcs (Xi, Xj) du CSP."""
arcs = []
for var in self.variables:
for neighbor in self.neighbors[var]:
arcs.append((var, neighbor))
return arcs
def get_constraints_list(self):
"""Retourne la liste des paires (var1, var2) de contraintes (sans doublons)."""
constraints = []
seen = set()
for var in self.variables:
for neighbor in self.neighbors[var]:
pair = tuple(sorted([var, neighbor]))
if pair not in seen:
seen.add(pair)
constraints.append(pair)
return constraints
print("Classe CSP definie.")Classe CSP definie.Definissons également les problemes de reference que nous utiliserons tout au long du notebook : la coloration de l’Australie et les N-Reines.
# === Problemes de reference ===
# --- Coloration de l'Australie ---
australia_vars = ['WA', 'NT', 'SA', 'Q', 'NSW', 'V', 'T']
australia_domains = {v: ['Rouge', 'Vert', 'Bleu'] for v in australia_vars}
australia_neighbors = {
'WA': ['NT', 'SA'],
'NT': ['WA', 'SA', 'Q'],
'SA': ['WA', 'NT', 'Q', 'NSW', 'V'],
'Q': ['NT', 'SA', 'NSW'],
'NSW': ['Q', 'SA', 'V'],
'V': ['SA', 'NSW'],
'T': []
}
def different_values(var1, val1, var2, val2):
"""Contrainte : deux variables voisines doivent avoir des valeurs differentes."""
return val1 != val2
def make_australia_csp():
"""Cree une nouvelle instance du CSP de coloration de l'Australie."""
return CSP(australia_vars, australia_domains,
australia_neighbors, different_values)
# --- N-Reines ---
def make_nqueens_csp(n):
"""Cree un CSP pour le probleme des N-Reines."""
variables = list(range(n))
domains = {col: list(range(n)) for col in variables}
neighbors = {col: [c for c in variables if c != col] for col in variables}
def queens_constraint(c1, r1, c2, r2):
if r1 == r2:
return False
if abs(c1 - c2) == abs(r1 - r2):
return False
return True
return CSP(variables, domains, neighbors, queens_constraint)
# --- Visualisation N-Reines ---
def draw_queens(solution, n, title="Solution N-Reines"):
"""Visualise la solution du probleme des N-Reines."""
fig, ax = plt.subplots(figsize=(max(5, n * 0.7), max(5, n * 0.7)))
for row in range(n):
for col in range(n):
color = '#F0D9B5' if (row + col) % 2 == 0 else '#B58863'
rect = plt.Rectangle((col, n - 1 - row), 1, 1,
facecolor=color, edgecolor='black')
ax.add_patch(rect)
if solution:
for col, row in solution.items():
ax.text(col + 0.5, n - 1 - row + 0.5, 'Q',
ha='center', va='center', fontsize=max(8, 24 - n),
fontweight='bold', color='darkred')
ax.set_xlim(0, n)
ax.set_ylim(0, n)
ax.set_aspect('equal')
ax.set_xticks(range(n))
ax.set_yticks(range(n))
ax.set_xticklabels(range(n))
ax.set_yticklabels(range(n - 1, -1, -1))
ax.set_xlabel('Colonne')
ax.set_ylabel('Ligne')
ax.set_title(title, fontsize=13, fontweight='bold')
plt.tight_layout()
return fig
# Heuristique MRV (rappel de CSP-1)
def select_mrv(csp, assignment, domains):
"""Heuristique MRV : choisir la variable avec le moins de valeurs viables."""
unassigned = [v for v in csp.variables if v not in assignment]
return min(unassigned, key=lambda v: len(domains[v]))
print("Problemes de reference et utilitaires definis.")Problemes de reference et utilitaires definis.La consistance de noeud (node consistency) est la forme la plus simple de propagation. Elle ne concerne que les contraintes unaires – celles qui portent sur une seule variable.
Une variable \(X_i\) est node-consistent si et seulement si toutes les valeurs de son domaine \(D_i\) satisfont les contraintes unaires portant sur \(X_i\).
\[\text{Node-consistent}(X_i) \iff \forall v \in D_i, \text{les contraintes unaires sur } X_i \text{ sont satisfaites pour } v\]
| Variable | Domaine initial | Contrainte unaire | Domaine après NC |
|---|---|---|---|
| \(X\) | \(\{1, 2, 3, 4, 5\}\) | \(X > 2\) | \(\{3, 4, 5\}\) |
| \(Y\) | \(\{a, b, c\}\) | \(Y \neq a\) | \(\{b, c\}\) |
| \(Z\) | \(\{1, 2, 3\}\) | (aucune) | \(\{1, 2, 3\}\) (inchange) |
def node_consistency(domains, unary_constraints):
"""Applique la consistance de noeud.
Args:
domains: dict variable -> liste de valeurs
unary_constraints: dict variable -> fonction(valeur) -> bool
Returns:
domains modifies (en place)
"""
for var, constraint in unary_constraints.items():
if var in domains:
domains[var] = [v for v in domains[var] if constraint(v)]
return domains
# Exemple : variable X dans {1,2,3,4,5} avec X > 2
example_domains = {
'X': [1, 2, 3, 4, 5],
'Y': ['a', 'b', 'c'],
'Z': [1, 2, 3]
}
unary = {
'X': lambda v: v > 2,
'Y': lambda v: v != 'a'
}
print("Avant node consistency :")
for var, dom in example_domains.items():
print(f" {var}: {dom}")
node_consistency(example_domains, unary)
print("\nApres node consistency :")
for var, dom in example_domains.items():
print(f" {var}: {dom}")Avant node consistency :
X: [1, 2, 3, 4, 5]
Y: ['a', 'b', 'c']
Z: [1, 2, 3]
Apres node consistency :
X: [3, 4, 5]
Y: ['b', 'c']
Z: [1, 2, 3]Sortie obtenue : les domaines de X et Y sont reduits par les contraintes unaires, Z reste inchange.
| Variable | Avant | Après | Valeurs eliminees |
|---|---|---|---|
| X | {1,2,3,4,5} | {3,4,5} | 1, 2 (ne satisfont pas X > 2) |
| Y | {a,b,c} | {b,c} | a (ne satisfait pas Y != a) |
| Z | {1,2,3} | {1,2,3} | aucune (pas de contrainte unaire) |
Points cles : 1. La consistance de noeud est triviale a realiser : un simple filtrage lineaire 2. Elle est toujours appliquee en premier, avant toute autre forme de propagation 3. En pratique, les contraintes unaires sont souvent déjà integrees dans les domaines initiaux
Limitation : la consistance de noeud ne regarde pas les relations entre variables. Pour cela, il faut passer a la consistance d’arc.
La consistance d’arc (arc consistency) est le niveau de propagation le plus utilise en pratique. Elle considere les contraintes binaires entre paires de variables.
Un arc \((X_i, X_j)\) est arc-consistent si pour chaque valeur \(a \in D_i\), il existe au moins une valeur \(b \in D_j\) telle que la contrainte entre \(X_i\) et \(X_j\) est satisfaite.
\[\text{Arc-consistent}(X_i, X_j) \iff \forall a \in D_i, \exists b \in D_j : C(X_i = a, X_j = b)\]
Un CSP est arc-consistent si tous ses arcs sont arc-consistants.
AC-3 (Arc Consistency Algorithm #3) maintient une file d’arcs a traiter. Pour chaque arc \((X_i, X_j)\) : 1. Pour chaque valeur \(a\) de \(D_i\), verifier s’il existe un support dans \(D_j\) 2. Si une valeur \(a\) n’a aucun support, la retirer de \(D_i\) 3. Si \(D_i\) a ete modifie, ajouter a la file tous les arcs \((X_k, X_i)\) pour \(k \neq j\)
Implementons d’abord la fonction revise qui traite un arc unique, puis l’algorithme AC-3 complet.
def revise(csp, xi, xj, domains):
"""Rend l'arc (Xi, Xj) arc-consistent.
Retire de domains[xi] les valeurs qui n'ont aucun support dans domains[xj].
Returns:
True si domains[xi] a ete modifie, False sinon.
"""
revised = False
to_remove = []
for val_i in domains[xi]:
# Chercher un support : au moins une valeur de Xj compatible
has_support = False
for val_j in domains[xj]:
if csp.constraint_func(xi, val_i, xj, val_j):
has_support = True
break
if not has_support:
to_remove.append(val_i)
revised = True
for val in to_remove:
domains[xi].remove(val)
return revised
def ac3(csp, domains=None, arcs=None, verbose=False):
"""Algorithme AC-3 : rend le CSP arc-consistent.
Args:
csp: le CSP
domains: domaines courants (modifies en place). Si None, utilise csp.domains.
arcs: arcs initiaux a traiter. Si None, tous les arcs du CSP.
verbose: afficher la trace.
Returns:
True si le CSP est encore soluble (aucun domaine vide),
False si un domaine est devenu vide (echec).
"""
if domains is None:
domains = csp.domains
# Initialiser la file avec tous les arcs
if arcs is None:
queue = deque(csp.get_arcs())
else:
queue = deque(arcs)
n_revisions = 0
while queue:
xi, xj = queue.popleft()
if revise(csp, xi, xj, domains):
n_revisions += 1
if verbose:
print(f" REVISE({xi}, {xj}) -> D({xi}) = {domains[xi]}")
if len(domains[xi]) == 0:
if verbose:
print(f" ECHEC : domaine de {xi} vide !")
return False # Domaine vide : echec
# Ajouter les arcs (Xk, Xi) pour tous les voisins Xk != Xj
for xk in csp.neighbors[xi]:
if xk != xj:
queue.append((xk, xi))
if verbose:
print(f" AC-3 termine : {n_revisions} revisions effectuees.")
return True # Tous les domaines sont non vides
print("Fonctions revise() et ac3() definies.")Fonctions revise() et ac3() definies.Appliquons AC-3 a la coloration de l’Australie et observons les reductions de domaines. Rappelons que chaque variable commence avec le domaine {Rouge, Vert, Bleu}.
# AC-3 sur la coloration de l'Australie (domaines complets)
csp_aus = make_australia_csp()
domains_aus = csp_aus.copy_domains()
print("Domaines AVANT AC-3 :")
for var in australia_vars:
print(f" {var:>3} : {domains_aus[var]}")
print("\nExecution de AC-3 :")
result = ac3(csp_aus, domains_aus, verbose=True)
print(f"\nResultat : {'Consistant' if result else 'Echec'}")
print("\nDomaines APRES AC-3 :")
for var in australia_vars:
print(f" {var:>3} : {domains_aus[var]}")Domaines AVANT AC-3 :
WA : ['Rouge', 'Vert', 'Bleu']
NT : ['Rouge', 'Vert', 'Bleu']
SA : ['Rouge', 'Vert', 'Bleu']
Q : ['Rouge', 'Vert', 'Bleu']
NSW : ['Rouge', 'Vert', 'Bleu']
V : ['Rouge', 'Vert', 'Bleu']
T : ['Rouge', 'Vert', 'Bleu']
Execution de AC-3 :
AC-3 termine : 0 revisions effectuees.
Resultat : Consistant
Domaines APRES AC-3 :
WA : ['Rouge', 'Vert', 'Bleu']
NT : ['Rouge', 'Vert', 'Bleu']
SA : ['Rouge', 'Vert', 'Bleu']
Q : ['Rouge', 'Vert', 'Bleu']
NSW : ['Rouge', 'Vert', 'Bleu']
V : ['Rouge', 'Vert', 'Bleu']
T : ['Rouge', 'Vert', 'Bleu']Sortie obtenue : AC-3 ne reduit aucun domaine sur la coloration australienne sans assignation prealable.
| Variable | Domaine avant | Domaine après | Reduction |
|---|---|---|---|
| WA, NT, … | {R, V, B} | {R, V, B} | Aucune |
Pourquoi ? Pour chaque valeur de chaque variable, il existe toujours un support dans les voisins (car 3 couleurs pour une contrainte != laisse toujours 2 choix possibles). AC-3 ne peut rien eliminer.
Lecon : AC-3 sur les domaines initiaux n’est pas toujours utile. Sa puissance apparait surtout après une assignation, quand les domaines commencent a se reduire.
Observons ce qui se passe quand on fixe WA = Rouge, puis qu’on applique AC-3.
# AC-3 apres assignation WA = Rouge
csp_aus2 = make_australia_csp()
domains_aus2 = csp_aus2.copy_domains()
# Simuler l'assignation WA = Rouge en reduisant le domaine
domains_aus2['WA'] = ['Rouge']
print("Domaines apres WA = Rouge :")
for var in australia_vars:
print(f" {var:>3} : {domains_aus2[var]}")
print("\nExecution de AC-3 :")
result2 = ac3(csp_aus2, domains_aus2, verbose=True)
print(f"\nResultat : {'Consistant' if result2 else 'Echec'}")
print("\nDomaines APRES AC-3 :")
for var in australia_vars:
print(f" {var:>3} : {domains_aus2[var]}")Domaines apres WA = Rouge :
WA : ['Rouge']
NT : ['Rouge', 'Vert', 'Bleu']
SA : ['Rouge', 'Vert', 'Bleu']
Q : ['Rouge', 'Vert', 'Bleu']
NSW : ['Rouge', 'Vert', 'Bleu']
V : ['Rouge', 'Vert', 'Bleu']
T : ['Rouge', 'Vert', 'Bleu']
Execution de AC-3 :
REVISE(NT, WA) -> D(NT) = ['Vert', 'Bleu']
REVISE(SA, WA) -> D(SA) = ['Vert', 'Bleu']
AC-3 termine : 2 revisions effectuees.
Resultat : Consistant
Domaines APRES AC-3 :
WA : ['Rouge']
NT : ['Vert', 'Bleu']
SA : ['Vert', 'Bleu']
Q : ['Rouge', 'Vert', 'Bleu']
NSW : ['Rouge', 'Vert', 'Bleu']
V : ['Rouge', 'Vert', 'Bleu']
T : ['Rouge', 'Vert', 'Bleu']Sortie obtenue : AC-3 propage l’assignation WA = Rouge et reduit les domaines des voisins directs de WA, c’est-a-dire NT et SA (2 revisions effectuees, cf. la sortie ci-dessus). Les autres variables (Q, NSW, V) restent inchangees.
| Variable | Domaine avant AC-3 | Domaine après AC-3 | Explication |
|---|---|---|---|
| WA | {Rouge} | {Rouge} | Fixe par l’assignation |
| NT | {R, V, B} | {V, B} | Voisin de WA : Rouge retire |
| SA | {R, V, B} | {V, B} | Voisin de WA : Rouge retire |
| Q | {R, V, B} | {R, V, B} (inchange) | Voisin de NT/SA, mais garde un support pour chaque couleur |
| NSW, V | {R, V, B} | {R, V, B} (inchange) | Idem : aucune valeur n’y perd son dernier support |
Points cles : 1. L’assignation de WA se propage a ses voisins directs NT et SA (Rouge retire). 2. En general, reduire NT et SA pourrait declencher d’autres reductions (effet de cascade), mais seulement si la reduction supprime le dernier support d’une valeur chez un voisin. Ici NT = {V, B} et SA = {V, B} laissent un support a chaque couleur de Q/NSW/V : la cascade s’arrete des le premier niveau (2 revisions). 3. T (Tasmanie) reste inchangee car elle n’a aucun voisin.
Observation : AC-3 après une assignation fait au moins le travail du Forward Checking (reduction des voisins directs) et peut aller plus loin par cascade. Sur cette instance, la propagation s’arrete des le premier niveau, faute de support supprime en aval.
Visualisons l’etat du graphe de contraintes avant et après l’application de AC-3.
# Visualisation avant et apres AC-3
fig, axes = plt.subplots(1, 2, figsize=(16, 7))
constraints_list = csp_aus2.get_constraints_list()
# Avant AC-3 : domaines initiaux apres assignation WA=Rouge
domains_before = {v: ['Rouge', 'Vert', 'Bleu'] for v in australia_vars}
domains_before['WA'] = ['Rouge']
for ax, doms, title in [
(axes[0], domains_before, "Avant AC-3 (WA=Rouge fixe)"),
(axes[1], domains_aus2, "Apres AC-3")
]:
try:
import networkx as nx
G = nx.Graph()
G.add_nodes_from(australia_vars)
for c in constraints_list:
G.add_edge(c[0], c[1])
pos = nx.spring_layout(G, seed=42)
colors = []
for v in G.nodes():
if len(doms[v]) == 1:
colors.append('#90EE90') # Assigne / domaine singleton
elif len(doms[v]) < 3:
colors.append('#FFD700') # Domaine reduit
else:
colors.append('#ADD8E6') # Domaine complet
nx.draw(G, pos, ax=ax, with_labels=True, node_color=colors,
node_size=900, font_size=10, font_weight='bold',
edge_color='gray', width=1.5)
for v in G.nodes():
x, y = pos[v]
dom_str = str(doms[v])
if len(dom_str) > 25:
dom_str = f"|D|={len(doms[v])}"
ax.text(x, y - 0.15, dom_str, ha='center', fontsize=7,
bbox=dict(boxstyle='round,pad=0.2', facecolor='wheat', alpha=0.5))
ax.set_title(title, fontsize=12, fontweight='bold')
except ImportError:
ax.text(0.5, 0.5, "NetworkX requis", ha='center', va='center')
# Legende
legend_items = [
mpatches.Patch(facecolor='#90EE90', edgecolor='black', label='Singleton (assigne)'),
mpatches.Patch(facecolor='#FFD700', edgecolor='black', label='Domaine reduit'),
mpatches.Patch(facecolor='#ADD8E6', edgecolor='black', label='Domaine complet'),
]
fig.legend(handles=legend_items, loc='lower center', ncol=3, fontsize=10)
plt.suptitle("Propagation AC-3 sur la coloration de l'Australie",
fontsize=14, fontweight='bold')
plt.tight_layout(rect=[0, 0.06, 1, 0.95])
plt.show()
Sortie obtenue : la comparaison visuelle montre l’effet de AC-3 sur cette instance.
Points cles : 1. Les noeuds verts (singleton) representent les variables dont le domaine est reduit a une seule valeur 2. Les noeuds jaunes montrent les variables dont le domaine a ete partiellement reduit 3. Sur cette instance, l’assignation de WA reduit directement NT et SA (Rouge retire) ; la propagation s’arrete la, car NT = {V, B} et SA = {V, B} laissent encore un support a Q, NSW et V. AC-3 peut propager plus loin sur d’autres instances, quand une reduction supprime le dernier support d’une valeur chez un voisin et declenche de nouvelles revisions.
Résultat important : dans certains cas, AC-3 seul peut resoudre le CSP completement (quand tous les domaines deviennent des singletons). Sinon, il faut combiner AC-3 avec le backtracking.
Testons sur un exemple ou AC-3 suffit a trouver la solution : un petit CSP fortement contraint.
# Exemple ou AC-3 seul resout le CSP
# 3 variables, 2 couleurs, contraintes d'inegalite
# A -- B -- C (chemin lineaire)
small_vars = ['A', 'B', 'C']
small_domains = {'A': ['R', 'V'], 'B': ['R', 'V'], 'C': ['R', 'V']}
small_neighbors = {'A': ['B'], 'B': ['A', 'C'], 'C': ['B']}
csp_small = CSP(small_vars, small_domains, small_neighbors, different_values)
# Fixer A = R
doms_small = csp_small.copy_domains()
doms_small['A'] = ['R']
print("Domaines apres A = R :")
for v in small_vars:
print(f" {v}: {doms_small[v]}")
print("\nExecution de AC-3 :")
ac3(csp_small, doms_small, verbose=True)
print("\nDomaines finaux :")
for v in small_vars:
print(f" {v}: {doms_small[v]}")
all_singleton = all(len(doms_small[v]) == 1 for v in small_vars)
print(f"\nTous les domaines sont des singletons : {all_singleton}")
if all_singleton:
solution = {v: doms_small[v][0] for v in small_vars}
print(f"Solution trouvee par AC-3 seul : {solution}")Domaines apres A = R :
A: ['R']
B: ['R', 'V']
C: ['R', 'V']
Execution de AC-3 :
REVISE(B, A) -> D(B) = ['V']
REVISE(C, B) -> D(C) = ['R']
AC-3 termine : 2 revisions effectuees.
Domaines finaux :
A: ['R']
B: ['V']
C: ['R']
Tous les domaines sont des singletons : True
Solution trouvee par AC-3 seul : {'A': 'R', 'B': 'V', 'C': 'R'}Sortie obtenue : sur ce petit CSP (chemin lineaire A-B-C, 2 couleurs), AC-3 resout completement le problème après la première assignation.
| Étape | Action | Domaines |
|---|---|---|
| Initial | A = R | A:{R}, B:{R,V}, C:{R,V} |
| REVISE(B,A) | R retire de B | A:{R}, B:{V}, C:{R,V} |
| REVISE(C,B) | V retire de C | A:{R}, B:{V}, C:{R} |
Quand AC-3 suffit-il ? AC-3 seul peut resoudre un CSP quand : 1. Le graphe de contraintes est un arbre (pas de cycles) 2. Les domaines sont suffisamment petits par rapport aux contraintes
Theoreme : pour un CSP dont le graphe de contraintes est un arbre, la consistance d’arc garantit la resolution en \(O(ed^2)\). Pour les graphes avec cycles, il faut généralement combiner AC-3 avec la recherche.
Visualiser le fonctionnement d’AC-3 permet de comprendre comment les domaines sont reduits progressivement.
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
from IPython.display import HTML, display
from collections import deque
class AC3Animator:
"""
Animateur pour visualiser le deroulement de l'algorithme AC-3.
Capture les etats intermediaires pour animation.
"""
def __init__(self):
self.states = []
self.arc_processed = 0
self.values_pruned = 0
def capture_state(self, domains, queue_size, current_arc=None, pruned=None):
"""Capture l'etat courant pour l'animation."""
domains_copy = {v: list(d) for v, d in domains.items()}
self.states.append({
'domains': domains_copy,
'queue_size': queue_size,
'arc': current_arc,
'pruned': pruned or []
})
def animate(self, variable_names=None, title="Animation AC-3"):
"""Cree une animation du processus AC-3."""
if not self.states:
print("Aucun etat capture pour l'animation.")
return None
fig, axes = plt.subplots(1, 2, figsize=(14, 6))
n_vars = len(self.states[0]['domains'])
if variable_names is None:
variable_names = list(self.states[0]['domains'].keys())
def update(frame):
ax1, ax2 = axes
ax1.clear()
ax2.clear()
state = self.states[frame]
domains = state['domains']
positions = range(n_vars)
colors = plt.cm.Set3(range(n_vars))
for i, var in enumerate(variable_names):
domain = domains.get(var, [])
ax1.bar(i, len(domain), color=colors[i], edgecolor='black')
ax1.text(i, len(domain) + 0.1, f"{len(domain)}", ha='center', fontsize=10)
ax1.set_xticks(positions)
ax1.set_xticklabels(variable_names)
ax1.set_ylabel("Taille du domaine")
ax1.set_xlabel("Variable")
ax1.set_ylim(0, max(len(d) for state in self.states for d in state['domains'].values()) + 1)
arc_info = state['arc']
arc_str = f" - Arc: {arc_info}" if arc_info else ""
ax1.set_title(f"Etape {frame+1}/{len(self.states)}{arc_str}")
queue_sizes = [s['queue_size'] for s in self.states[:frame+1]]
ax2.plot(range(len(queue_sizes)), queue_sizes, 'b-o', linewidth=2)
ax2.fill_between(range(len(queue_sizes)), queue_sizes, alpha=0.3)
ax2.axvline(x=frame, color='r', linestyle='--', alpha=0.5)
ax2.set_xlabel("Iteration")
ax2.set_ylabel("Taille de la file")
ax2.set_title("Evolution de la file d'arcs")
ax2.grid(True, alpha=0.3)
if state['pruned']:
ax2.text(0.5, 0.95, f"Valeurs elaguees: {state['pruned']}",
transform=ax2.transAxes, ha='center', va='top',
fontsize=10, color='red')
return axes
anim = FuncAnimation(fig, update, frames=len(self.states),
interval=500, blit=False, repeat=True)
plt.tight_layout()
return HTML(anim.to_jshtml())
def revise_animated(domains, xi, xj, csp):
"""Fonction REVISE pour AC-3 anime."""
revised = False
to_remove = []
for vi in domains[xi]:
has_support = False
for vj in domains[xj]:
if csp.constraint_func(xi, vi, xj, vj):
has_support = True
break
if not has_support:
to_remove.append(vi)
revised = True
for v in to_remove:
domains[xi].remove(v)
return revised
def ac3_with_animation(csp, animator=None):
"""
AC-3 avec capture d'etats pour animation.
"""
if animator is None:
animator = AC3Animator()
domains = {v: list(csp.domains[v]) for v in csp.variables}
queue = deque()
for var in csp.variables:
for neighbor in csp.neighbors[var]:
queue.append((var, neighbor))
animator.capture_state(domains, len(queue))
while queue:
xi, xj = queue.popleft()
if revise_animated(domains, xi, xj, csp):
pruned = [v for v in csp.domains[xi] if v not in domains[xi]]
animator.capture_state(domains, len(queue), (xi, xj), pruned)
if len(domains[xi]) == 0:
return False, domains, animator
for xk in csp.neighbors[xi]:
if xk != xj:
queue.append((xk, xi))
else:
animator.capture_state(domains, len(queue), (xi, xj))
return True, domains, animator
print("Animateur AC-3 pret.")Animateur AC-3 pret.Exemple d’animation AC-3 sur la carte d’Australie
# Exemple d'animation AC-3 sur la carte d'Australie
print("=== Animation AC-3 sur la coloration d'Australie ===\n")
# Utiliser le CSP de l'Australie deja defini
au_csp = make_australia_csp()
# Executer AC-3 avec animation
animator = AC3Animator()
success, domains, animator = ac3_with_animation(au_csp, animator)
print(f"AC-3 reussi : {success}")
print(f"Domaines reduits :")
for var, dom in domains.items():
print(f" {var} : {dom}")
# Afficher une image statique de l'evolution
fig, ax = plt.subplots(figsize=(10, 6))
queue_sizes = [s['queue_size'] for s in animator.states]
ax.plot(queue_sizes, 'b-o', linewidth=2, markersize=4)
ax.fill_between(range(len(queue_sizes)), queue_sizes, alpha=0.3)
ax.set_xlabel("Etape de l'algorithme")
ax.set_ylabel("Taille de la file d'arcs")
ax.set_title("Evolution de la file d'arcs pendant AC-3")
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
print(f"\nNombre d'etats captures : {len(animator.states)}")=== Animation AC-3 sur la coloration d'Australie ===
AC-3 reussi : True
Domaines reduits :
WA : ['Rouge', 'Vert', 'Bleu']
NT : ['Rouge', 'Vert', 'Bleu']
SA : ['Rouge', 'Vert', 'Bleu']
Q : ['Rouge', 'Vert', 'Bleu']
NSW : ['Rouge', 'Vert', 'Bleu']
V : ['Rouge', 'Vert', 'Bleu']
T : ['Rouge', 'Vert', 'Bleu']
Nombre d'etats captures : 19Comparaison AC-3 vs AC-4
# Comparaison AC-3 vs AC-4
print("=== Comparaison AC-3 vs AC-4 ===\n")
# Tableau comparatif
comparison_data = {
'Critere': ['Complexite pire cas', 'Espace memoire', 'Implementation', 'Revisions inutiles', 'Cas d\'usage'],
'AC-3': ['O(e * d^3)', 'O(e)', 'Simple', 'Possible', 'Generaliste, facile a implementer'],
'AC-4': ['O(e * d^2)', 'O(e * d^2)', 'Complexe', 'Evitees', 'Gros CSP avec beaucoup de revisions']
}
print("| Critere | AC-3 | AC-4 |")
print("|---------|------|------|")
for i, critere in enumerate(comparison_data['Critere']):
print(f"| {critere} | {comparison_data['AC-3'][i]} | {comparison_data['AC-4'][i]} |")
print("\n**Explications** :")
print("- **e** = nombre d'arcs dans le graphe de contraintes")
print("- **d** = taille maximale des domaines")
print("- AC-3 : O(e*d^3) au pire cas (Mackworth 1977) ; pas de meilleure borne 'amortie' standard")
print("- AC-4 : O(e*d^2) au pire cas (Mohr & Henderson 1986), optimal pour l'arc-consistance")
print("\n**AC-4** utilise des structures de donnees supplementaires pour :")
print("1. Compter le nombre de supports pour chaque valeur")
print("2. Eviter de re-reviser des arcs qui n'ont pas change")
print("\nCependant, AC-4 a une overhead memoire et implementation plus complexe.")=== Comparaison AC-3 vs AC-4 ===
| Critere | AC-3 | AC-4 |
|---------|------|------|
| Complexite pire cas | O(e * d^3) | O(e * d^2) |
| Espace memoire | O(e) | O(e * d^2) |
| Implementation | Simple | Complexe |
| Revisions inutiles | Possible | Evitees |
| Cas d'usage | Generaliste, facile a implementer | Gros CSP avec beaucoup de revisions |
**Explications** :
- **e** = nombre d'arcs dans le graphe de contraintes
- **d** = taille maximale des domaines
- AC-3 : O(e*d^3) au pire cas (Mackworth 1977) ; pas de meilleure borne 'amortie' standard
- AC-4 : O(e*d^2) au pire cas (Mohr & Henderson 1986), optimal pour l'arc-consistance
**AC-4** utilise des structures de donnees supplementaires pour :
1. Compter le nombre de supports pour chaque valeur
2. Eviter de re-reviser des arcs qui n'ont pas change
Cependant, AC-4 a une overhead memoire et implementation plus complexe.Benchmark simplifie : nombre de revisions d’arcs
# Benchmark simplifie : nombre de revisions d'arcs
def benchmark_ac3_vs_simple(csp, iterations=10):
"""Compare le nombre de revisions d'arcs entre AC-3 et une version naive."""
def run_ac3(csp):
domains = {v: list(csp.domains[v]) for v in csp.variables}
queue = deque()
revisions = 0
for var in csp.variables:
for neighbor in csp.neighbors[var]:
queue.append((var, neighbor))
while queue:
xi, xj = queue.popleft()
revisions += 1
if revise(csp, xi, xj, domains):
if len(domains[xi]) == 0:
return False, revisions
for xk in csp.neighbors[xi]:
if xk != xj:
queue.append((xk, xi))
return True, revisions
total_revisions = 0
for _ in range(iterations):
_, rev = run_ac3(csp)
total_revisions += rev
return total_revisions / iterations
# Benchmark sur la carte d'Australie
au_csp_bench = make_australia_csp()
avg_revisions = benchmark_ac3_vs_simple(au_csp_bench)
print(f"\nBenchmark AC-3 sur l'Australie :")
print(f" Nombre moyen de revisions d'arcs : {avg_revisions:.1f}")
print(f" Nombre d'arcs initial : {sum(len(au_csp_bench.neighbors[v]) for v in au_csp_bench.variables)}")
Benchmark AC-3 sur l'Australie :
Nombre moyen de revisions d'arcs : 18.0
Nombre d'arcs initial : 18Quand utiliser AC-3 ? - La plupart des cas pratiques - Implementation simple et maintenable - Quand la memoire est une contrainte
Quand utiliser AC-4 ? - Très gros CSP avec beaucoup de revisions redondantes - Quand la complexite pire cas est critique - Implementation avec des structures de données persistantes
En pratique : AC-3 est souvent suffisant et est l’algorithme par defaut dans la plupart des solveurs CSP (y compris OR-Tools).
AC-3 n’est pas le seul algorithme pour etablir la consistance d’arc. Voici une comparaison avec AC-4, une alternative optimisee pour certains cas.
Notre AC-3 maison (section 3) est un algorithme de propagation : il réduit les domaines mais n’assigne rien. Un solveur industriel comme Choco-solver intègre natement cette propagation dans la recherche : à chaque décision, les domaines sont filtrés avant l’exploration. Le jumeau .NET de ce notebook (CSP-2-Consistency-CSharp) montre exactement cette cellule avec Choco via le pont IKVM ; ici nous la rejouons avec pychoco (binding Python officiel du même moteur Choco) — les deux jumeaux atteignent le même solveur de production.
Nous reprenons le modèle de la cellule « AC-3 après assignation » : Australie, 3 couleurs, WA = 1 (Rouge) fixé.
import time
import pychoco
# Australie via Choco (pychoco) : meme modele que la section 4 du jumeau C#
choc_model = pychoco.Model("Australie AC-3 via Choco")
choc_vars = {v: choc_model.intvar(1, 3, name=v) for v in australia_vars}
for v1 in australia_vars:
for v2 in australia_neighbors[v1]:
choc_model.arithm(choc_vars[v1], "!=", choc_vars[v2]).post()
# Assigner WA = 1 (Rouge) -- equivalent a notre AC-3 custom de la cellule precedente
choc_model.arithm(choc_vars["WA"], "=", 1).post()
t0 = time.perf_counter()
choc_solver = choc_model.get_solver()
solved = choc_solver.solve()
choco_ms = (time.perf_counter() - t0) * 1000.0
color_names = {1: "Rouge", 2: "Vert", 3: "Bleu"}
print(f"Choco solveur : solved = {bool(solved)}, solutions trouvees = {choc_solver.get_solution_count()}")
if solved:
print()
print("Assignation trouvee par Choco :")
for v in australia_vars:
val = choc_vars[v].get_value()
print(f" {v:<4} = {val} ({color_names[val]})")
print(f"Temps : {choco_ms:.2f} ms (runtime machine-dep, cf. regle #9434 -- non fige en prose)")Choco solveur : solved = True, solutions trouvees = 1
Assignation trouvee par Choco :
WA = 1 (Rouge)
NT = 3 (Bleu)
SA = 2 (Vert)
Q = 1 (Rouge)
NSW = 3 (Bleu)
V = 1 (Rouge)
T = 1 (Rouge)
Temps : 0.40 ms (runtime machine-dep, cf. regle #9434 -- non fige en prose)Sortie obtenue : Choco résout l’Australie en un seul appel solve() — la propagation (filtrage des domaines après WA = 1, équivalente à notre AC-3 de la cellule précédente) et la recherche sont intégrées : pas de file d’arcs à gérer, le solveur applique ses propagateurs à chaque décision.
Parité lib-vs-lib : le jumeau C# exécute le même modèle (7 IntVar 1..3, arithm != sur les adjacences, WA = 1) via Choco 4.10.17/IKVM et obtient aussi une solution valide équivalente — même moteur (Choco), deux bindings (.NET/IKVM et Python/pychoco). L’assignation exacte des autres variables peut différer de notre AC-3 maison comme du jumeau : toutes sont des solutions valides du même modèle.
Ce que notre AC-3 maison apporte : la transparence — on voit la file d’arcs, les révisions, le fixpoint. Choco apporte l’industrialisation — propagation optimisée, heuristiques, recherche mondiale. Les deux notebooks gardent le socle from-scratch (tranche 1) et le pont industriel (tranche 2).
Le Forward Checking (FC) est une technique qui integre la propagation de contraintes directement dans le backtracking. L’idee est simple :
Quand on assigne \(X_i = v\), on retire immediatement les valeurs incompatibles des domaines des voisins non assignes de \(X_i\).
| Backtracking pur | Forward Checking |
|---|---|
| Verifie la consistance seulement avec les variables déjà assignees | En plus, propage vers les variables non assignees |
| Detecte les echecs au moment de l’assignation | Detecte les echecs plus tot (domaine vide) |
| Ne modifie pas les domaines | Reduit les domaines dynamiquement |
def forward_checking(csp, var, val, assignment, domains):
"""Propage l'assignation var=val vers les voisins non assignes.
Retire des domaines des voisins les valeurs incompatibles.
Returns:
removals: liste de (variable, valeur) retirees, pour restauration.
success: True si aucun domaine n'est devenu vide.
"""
removals = []
for neighbor in csp.neighbors[var]:
if neighbor not in assignment:
for nval in domains[neighbor][:]:
if not csp.constraint_func(var, val, neighbor, nval):
domains[neighbor].remove(nval)
removals.append((neighbor, nval))
if len(domains[neighbor]) == 0:
return removals, False # Domaine vide : echec
return removals, True
def restore_domains(domains, removals):
"""Restaure les valeurs retirees lors du forward checking."""
for var, val in removals:
domains[var].append(val)
def backtracking_fc(csp, assignment=None, domains=None, verbose=False):
"""Backtracking avec Forward Checking et heuristique MRV."""
if assignment is None:
assignment = {}
domains = csp.copy_domains()
if csp.is_complete(assignment):
return assignment
var = select_mrv(csp, assignment, domains)
for val in list(domains[var]):
csp.n_assigns += 1
if csp.consistent(var, val, assignment):
assignment[var] = val
if verbose:
indent = " " * len(assignment)
print(f"{indent}{var} = {val}")
# Forward checking : propager vers les voisins
removals, success = forward_checking(csp, var, val, assignment, domains)
if success:
result = backtracking_fc(csp, assignment, domains, verbose)
if result is not None:
return result
# Restaurer les domaines et desassigner
restore_domains(domains, removals)
del assignment[var]
csp.n_backtracks += 1
return None
print("Backtracking avec Forward Checking defini.")Backtracking avec Forward Checking defini.Observons pas a pas comment le Forward Checking reduit les domaines au fur et a mesure des assignations.
# Trace detaillee du Forward Checking
def fc_trace(csp, verbose=True):
"""Forward Checking avec trace des domaines a chaque etape."""
assignment = {}
domains = csp.copy_domains()
steps = []
def solve(depth):
if csp.is_complete(assignment):
return True
var = select_mrv(csp, assignment, domains)
for val in list(domains[var]):
csp.n_assigns += 1
if csp.consistent(var, val, assignment):
assignment[var] = val
removals, success = forward_checking(csp, var, val, assignment, domains)
if verbose:
indent = " " * depth
status = "OK" if success else "ECHEC (domaine vide)"
print(f"{indent}Assigner {var} = {val} [{status}]")
if success:
# Afficher les domaines restants
unassigned = [v for v in csp.variables if v not in assignment]
for u in unassigned:
print(f"{indent} D({u}) = {domains[u]}")
if success:
if solve(depth + 1):
return True
restore_domains(domains, removals)
del assignment[var]
return False
found = solve(0)
return assignment if found else None
# Executer sur la coloration de l'Australie
csp_fc = make_australia_csp()
print("Forward Checking - Coloration de l'Australie")
print("=" * 55)
sol_fc = fc_trace(csp_fc)
print(f"\nSolution : {sol_fc}")
print(f"Assignations : {csp_fc.n_assigns}")Forward Checking - Coloration de l'Australie
=======================================================
Assigner WA = Rouge [OK]
D(NT) = ['Vert', 'Bleu']
D(SA) = ['Vert', 'Bleu']
D(Q) = ['Rouge', 'Vert', 'Bleu']
D(NSW) = ['Rouge', 'Vert', 'Bleu']
D(V) = ['Rouge', 'Vert', 'Bleu']
D(T) = ['Rouge', 'Vert', 'Bleu']
Assigner NT = Vert [OK]
D(SA) = ['Bleu']
D(Q) = ['Rouge', 'Bleu']
D(NSW) = ['Rouge', 'Vert', 'Bleu']
D(V) = ['Rouge', 'Vert', 'Bleu']
D(T) = ['Rouge', 'Vert', 'Bleu']
Assigner SA = Bleu [OK]
D(Q) = ['Rouge']
D(NSW) = ['Rouge', 'Vert']
D(V) = ['Rouge', 'Vert']
D(T) = ['Rouge', 'Vert', 'Bleu']
Assigner Q = Rouge [OK]
D(NSW) = ['Vert']
D(V) = ['Rouge', 'Vert']
D(T) = ['Rouge', 'Vert', 'Bleu']
Assigner NSW = Vert [OK]
D(V) = ['Rouge']
D(T) = ['Rouge', 'Vert', 'Bleu']
Assigner V = Rouge [OK]
D(T) = ['Rouge', 'Vert', 'Bleu']
Assigner T = Rouge [OK]
Solution : {'WA': 'Rouge', 'NT': 'Vert', 'SA': 'Bleu', 'Q': 'Rouge', 'NSW': 'Vert', 'V': 'Rouge', 'T': 'Rouge'}
Assignations : 7La trace montre comment les domaines se reduisent a chaque assignation.
Mécanisme observe : 1. Quand une variable est assignee, les domaines de ses voisins sont immediatement reduits 2. Si un domaine devient vide, on detecte l’echec sans recurser plus profondement 3. Les domaines sont restaures lors du backtrack
Comparaison avec le backtracking pur :
| Aspect | Backtracking pur | Forward Checking |
|---|---|---|
| Detection d’echec | A l’assignation suivante | Immediatement (domaine vide) |
| Cout par assignation | \(O(\text{voisins assignes})\) | \(O(\text{voisins} \times \vert D\vert)\) |
| Noeuds explores | Plus | Moins |
Intuition : le Forward Checking “regarde un coup d’avance” en verifiant que chaque voisin a encore au moins une valeur viable.
Le MAC (Maintaining Arc Consistency) va plus loin que le Forward Checking en executant AC-3 après chaque assignation, au lieu de simplement verifier les voisins directs.
| Aspect | Forward Checking | MAC |
|---|---|---|
| Propagation | 1 niveau (voisins directs) | Cascade complete (AC-3) |
| Detection d’echec | Domaine vide chez un voisin | Domaine vide n’importe ou |
| Cout | \(O(\text{deg} \times d)\) par assignation | \(O(e \cdot d^3)\) par assignation |
| Elagage | Modere | Maximal |
L’avantage est que la propagation en cascade peut detecter des echecs bien plus tot que le Forward Checking.
def backtracking_mac(csp, assignment=None, domains=None):
"""Backtracking avec Maintaining Arc Consistency (MAC) et MRV."""
if assignment is None:
assignment = {}
domains = csp.copy_domains()
if csp.is_complete(assignment):
return assignment
var = select_mrv(csp, assignment, domains)
for val in list(domains[var]):
csp.n_assigns += 1
if csp.consistent(var, val, assignment):
assignment[var] = val
# Sauvegarder les domaines pour restauration
saved_domains = {v: list(d) for v, d in domains.items()}
# Reduire le domaine de var a {val}
domains[var] = [val]
# Executer AC-3 sur les arcs affectes
arcs = [(neighbor, var) for neighbor in csp.neighbors[var]
if neighbor not in assignment]
success = ac3(csp, domains, arcs=arcs)
if success:
result = backtracking_mac(csp, assignment, domains)
if result is not None:
return result
# Restaurer les domaines et desassigner
for v in domains:
domains[v] = saved_domains[v]
del assignment[var]
csp.n_backtracks += 1
return None
print("Backtracking MAC defini.")Backtracking MAC defini.Pour comparer equitablement, reimplementons le backtracking simple avec MRV mais sans propagation.
def backtracking_simple(csp, assignment=None, domains=None):
"""Backtracking simple avec heuristique MRV, sans propagation."""
if assignment is None:
assignment = {}
domains = csp.copy_domains()
if csp.is_complete(assignment):
return assignment
var = select_mrv(csp, assignment, domains)
for val in list(domains[var]):
csp.n_assigns += 1
if csp.consistent(var, val, assignment):
assignment[var] = val
result = backtracking_simple(csp, assignment, domains)
if result is not None:
return result
del assignment[var]
csp.n_backtracks += 1
return None
print("Backtracking simple (reference) defini.")Backtracking simple (reference) defini.Comparons les trois approches sur le problème des 8-Reines, en mesurant le nombre d’assignations et de backtracks.
# Comparaison sur 8-Reines
n = 8
solvers = [
("Backtracking + MRV", backtracking_simple),
("Forward Checking + MRV", backtracking_fc),
("MAC + MRV", backtracking_mac),
]
results_8q = []
print(f"Comparaison sur le probleme des {n}-Reines")
print("=" * 65)
print(f"{'Algorithme':<25} {'Assigns':>10} {'Backtracks':>12} {'Temps (ms)':>12}")
print("-" * 65)
for name, solver in solvers:
csp = make_nqueens_csp(n)
start = time.time()
sol = solver(csp)
elapsed = (time.time() - start) * 1000
results_8q.append({
'algorithm': name,
'assigns': csp.n_assigns,
'backtracks': csp.n_backtracks,
'time_ms': elapsed,
'solution_found': sol is not None
})
found_str = 'Oui' if sol is not None else 'Non'
print(f"{name:<25} {csp.n_assigns:>10} {csp.n_backtracks:>12} {elapsed:>12.2f}")
print("=" * 65)Comparaison sur le probleme des 8-Reines
=================================================================
Algorithme Assigns Backtracks Temps (ms)
-----------------------------------------------------------------
Backtracking + MRV 876 105 0.54
Forward Checking + MRV 67 59 0.31
MAC + MRV 20 12 0.65
=================================================================Sortie obtenue : les trois algorithmes trouvent une solution, mais avec des nombres d’assignations et de retours-arriere tres differents (valeurs deterministes, reproductibles par re-execution) :
| Algorithme | Assignations | Backtracks | Tendance |
|---|---|---|---|
| Backtracking + MRV | 876 | 105 | Detecte les conflits tard, apres assignation |
| Forward Checking + MRV | 67 | 59 | Detecte 1 coup d’avance (domaines futurs) |
| MAC + MRV | 20 | 12 | Propagation complete d’arc-consistance |
Points cles : 1. FC reduit fortement les retours-arriere (105 -> 59) en detectant tot les domaines futurs vides. 2. MAC va encore plus loin (20 assignations seulement) en restaurant l’arc-consistance a chaque pas. 3. Le gain en assignations se paie par un cout par noeud plus eleve (la propagation) : l’arbitrage complet cout/noeud vs elagage est detaille dans le benchmark suivant (tailles croissantes).
# Visualisation de la solution trouvee par MAC
csp_show = make_nqueens_csp(n)
sol_show = backtracking_mac(csp_show)
draw_queens(sol_show, n, f"8-Reines resolues par MAC ({csp_show.n_assigns} assignations)")
plt.show()
Sortie obtenue : le problème des 8-Reines est resolu avec seulement 20 assignations par MAC.
| Aspect | Valeur | Signification |
|---|---|---|
| Assignations | 20 | Très efficace vs 876 pour BT pur |
| Solution | Valide | Toutes les reines sont placees sans conflits |
| Temps | < 1 ms | Resolution quasi instantanee |
Points cles : 1. MAC trouve une solution en explorant très peu de branches 2. Chaque reine est placee sur une ligne et colonne différente 3. La propagation elimine rapidement les placements impossibles 4. La solution respecte toutes les contraintes diagonales
Observation : sur les 8-Reines, MAC reduit le nombre d’assignations d’un facteur de ~40x par rapport au backtracking simple (876 → 20).
Comparons les trois approches sur des problemes de taille croissante pour observer comment les performances evoluent avec la difficulte.
# Benchmark sur N-Reines de taille croissante
sizes = [4, 8, 12]
all_benchmarks = []
print("Benchmark : BT vs FC vs MAC sur N-Reines")
print("=" * 75)
print(f"{'N':>3} {'Algorithme':<25} {'Assigns':>10} {'Backtracks':>12} {'Temps (ms)':>12}")
print("-" * 75)
for n in sizes:
for name, solver in solvers:
csp = make_nqueens_csp(n)
start = time.time()
sol = solver(csp)
elapsed = (time.time() - start) * 1000
all_benchmarks.append({
'n': n,
'algorithm': name,
'assigns': csp.n_assigns,
'backtracks': csp.n_backtracks,
'time_ms': elapsed,
'solution_found': sol is not None
})
print(f"{n:>3} {name:<25} {csp.n_assigns:>10} {csp.n_backtracks:>12} {elapsed:>12.2f}")
print("-" * 75)
print("=" * 75)Benchmark : BT vs FC vs MAC sur N-Reines
===========================================================================
N Algorithme Assigns Backtracks Temps (ms)
---------------------------------------------------------------------------
4 Backtracking + MRV 26 4 0.03
4 Forward Checking + MRV 8 4 0.03
4 MAC + MRV 5 1 0.07
---------------------------------------------------------------------------
8 Backtracking + MRV 876 105 0.55
8 Forward Checking + MRV 67 59 0.32
8 MAC + MRV 20 12 0.62
---------------------------------------------------------------------------
12 Backtracking + MRV 3066 249 2.08
12 Forward Checking + MRV 120 108 0.76
12 MAC + MRV 51 39 2.54
---------------------------------------------------------------------------
===========================================================================Pour comprendre l’impact de la propagation de contraintes, visualisons les résultats sous forme de graphiques en barres. Cette representation permet de comparer visuellement l’efficacite des trois approches (Backtracking, Forward Checking, MAC) a chaque taille de problème.
Ce que nous allons observer : - La reduction du nombre d’assignations quand on ajoute de la propagation - Comment l’ecart entre les approches grandit avec la taille du problème - Le compromis entre le cout par noeud et le nombre de noeud explores
# Visualisation des benchmarks
fig, axes = plt.subplots(1, 3, figsize=(18, 5))
algo_names = ["Backtracking + MRV", "Forward Checking + MRV", "MAC + MRV"]
algo_colors = ['#2196F3', '#4CAF50', '#FF9800']
for idx, n in enumerate(sizes):
ax = axes[idx]
data_n = [b for b in all_benchmarks if b['n'] == n]
assigns = [b['assigns'] for b in data_n]
names = [b['algorithm'].replace(' + MRV', '') for b in data_n]
bars = ax.bar(range(len(names)), assigns, color=algo_colors, edgecolor='black')
ax.set_xticks(range(len(names)))
ax.set_xticklabels(names, rotation=20, ha='right', fontsize=9)
ax.set_ylabel('Assignations')
ax.set_title(f'{n}-Reines', fontweight='bold', fontsize=13)
for bar, val in zip(bars, assigns):
ax.text(bar.get_x() + bar.get_width() / 2, bar.get_height(),
str(val), ha='center', va='bottom', fontsize=9)
plt.suptitle('Impact de la propagation sur le nombre d\'assignations (N-Reines)',
fontsize=14, fontweight='bold')
plt.tight_layout()
plt.show()
Sortie obtenue : le benchmark (cellule precedente) mesure, pour chaque taille N, le nombre d’assignations et de retours-arriere des trois approches. Les valeurs committées sont deterministes (verifiees par re-execution) :
| N | BT (assigns) | FC (assigns) | MAC (assigns) | Ratio BT/MAC (assigns) |
|---|---|---|---|---|
| 4 | 26 | 8 | 5 | 5,2x |
| 8 | 876 | 67 | 20 | 43,8x |
| 12 | 3066 | 120 | 51 | 60,1x |
Lecture (assignations) : sur le nombre d’assignations, MAC elague massivement - jusqu’a 60x moins que le backtracking naif a N=12. L’ecart grandit avec la taille : de 5,2x (N=4) a 60,1x (N=12). Le Forward Checking reduit deja fortement les assignations (13x a 26x moins que BT) pour un cout par noeud bien inferieur a MAC.
Analyse du compromis cout/noeud vs elagage :
| Aspect | Backtracking | Forward Checking | MAC |
|---|---|---|---|
| Cout par noeud | Faible | Modere | Eleve (AC-3 complet a chaque pas) |
| Noeuds explores | Beaucoup | Moderement | Peu |
| Temps observes (N=12) | lent (~2 ms) | le plus rapide (~0,7 ms) | le plus lent (~3 ms) |
Points cles : 1. L’ecart d’assignations entre les approches grandit avec la taille du probleme. 2. Pour les petits problemes (N=4), la difference est negligeable : les trois methodes se resolvent en une poignee d’assignations. 3. Sur les assignations (efficacite de la recherche), MAC domine nettement : 51 assignations contre 3066 pour le backtracking a N=12. 4. Mais le plus d’elagage ne signifie pas le plus rapide : chaque noeud MAC execute une propagation d’arc-consistance complete (couteuse). Sur les temps observes, MAC est en fait le plus lent des trois des N=8, tandis que le Forward Checking est le plus rapide (meilleur compromis cout/elagage). C’est le compromis fondamental : MAC explore peu de noeuds mais les paie cher ; BT en explore beaucoup mais tres peu cher ; FC est le point d’equilibre pratique.
Quand FC suffit vs quand MAC est necessaire : si le graphe de contraintes a un faible degre (peu de voisins), FC est souvent suffisant et plus rapide. Pour les graphes denses (comme N-Reines ou chaque variable est contrainte par toutes les autres), MAC apporte un elagage supplementaire significatif - utile quand le cout d’exploration des noeuds domine le cout de propagation (instances beaucoup plus grandes, ou contraintes plus lourdes a evaluer).
Lien : voir les notebooks App-6 (Minesweeper) et App-7 (Wordle) pour des applications concretes utilisant la consistance d’arc.
# Graphique de synthese : evolution du ratio d'amelioration
fig, ax = plt.subplots(figsize=(10, 6))
for algo, color, marker in zip(algo_names, algo_colors, ['o', 's', '^']):
data = [b for b in all_benchmarks if b['algorithm'] == algo]
ns = [b['n'] for b in data]
assigns = [b['assigns'] for b in data]
ax.plot(ns, assigns, f'-{marker}', color=color, linewidth=2,
markersize=10, label=algo.replace(' + MRV', ''), markeredgecolor='black')
ax.set_xlabel('N (taille du probleme)', fontsize=12)
ax.set_ylabel('Nombre d\'assignations', fontsize=12)
ax.set_title('Evolution des performances avec la taille du probleme',
fontsize=14, fontweight='bold')
ax.legend(fontsize=11)
ax.grid(True, alpha=0.3)
ax.set_xticks(sizes)
plt.tight_layout()
plt.show()
Considerez le CSP suivant avec 3 variables :
| Variable | Domaine | Contraintes |
|---|---|---|
| \(X\) | \(\{1, 2, 3\}\) | \(X < Y\) |
| \(Y\) | \(\{1, 2, 3\}\) | \(X < Y\), \(Y \neq Z\) |
| \(Z\) | \(\{1, 2, 3\}\) | \(Y \neq Z\) |
Question : Executez AC-3 a la main. Pour chaque arc traite, indiquez : - L’arc considere - Les valeurs retirees (le cas echeant) - Les arcs ajoutes a la file
Verifiez votre reponse avec le code ci-dessous.
print("Exercice a completer - Comparaison AC-3 vs AC-4")Exercice a completer - Comparaison AC-3 vs AC-4L’arc-consistance est le niveau que les solveurs utilisent au quotidien, mais elle a une limite que cette section met en évidence : elle ne propage que sur des contraintes binaires prises une à une. Les deux notions qui suivent montent d’un cran — et l’exercice 2 vous demandera d’en implémenter la première.
Ce qu’elle retire. AC-3 retire des valeurs des domaines ; la consistance de chemin (path consistency) retire des paires \((X_i = a, X_j = c)\) de l’ensemble des combinaisons permises entre deux variables. On ne raisonne plus sur une variable isolée, mais sur un triplet \((X_i, X_m, X_j)\) : la paire \((a, c)\) n’est conservée que s’il existe une valeur intermédiaire \(b \in D_m\) telle que \((X_i = a, X_m = b)\) et \((X_m = b, X_j = c)\) sont toutes deux consistantes.
\[\text{paire } (a, c) \text{ conservée} \iff \exists b \in D_m : C(X_i = a, X_m = b) \land C(X_m = b, X_j = c)\]
Le principe de la file de révision. Comme AC-3, PC-2 travaille par file de chemins à réviser : dès qu’une paire \((a, c)\) est éliminée, les chemins qui en dépendaient sont ré-insérés dans la file, jusqu’à atteindre un point fixe. La différence avec AC-3 tient à l’objet révisé : une paire de valeurs, non plus une valeur isolée.
Complexité. \(O(n^3 d^3)\) : les \(n^3\) chemins et le produit \(O(d^3)\) des paires vérifiées (cf. la ligne « Path Consistency » du tableau récapitulatif). C’est le prix d’un niveau de consistance plus fort — et la raison pour laquelle on n’y recourt que lorsque l’arc-consistance ne suffit pas à trancher.
Un exemple minimal où AC-3 ne coupe rien et PC-2 coupe. Prenons trois variables \(A, B, C\), domaines \(\{0, 1\}\), et les trois contraintes d’inégalité \(A \neq B\), \(B \neq C\), \(A \neq C\) : le triangle à 2-couleurs. Ce CSP est insatisfiable (on ne peut pas 2-colorer un triangle). AC-3 n’y retire rien : chaque valeur de chaque variable a un support chez chaque voisin. Tout est arc-consistant, et pourtant aucune solution n’existe. C’est PC-2 qui détecte le problème : pour le chemin \(A \to B \to C\), la paire \((A=0, C=0)\) exige un \(b\) tel que \(0 \neq b\) et \(b \neq 0\) — impossible. Toutes les paires \((A, C)\) succombent de la même façon, la contrainte \(A \neq C\) n’a plus de paire valide, et l’incohérence globale est révélée. AC-3 comme solveur se trompe sur ce cas ; PC-2 le rattrape — le lien direct avec la cellule « AC-3 peut-il résoudre un CSP seul ? » (section 3).
La consistance de chemin n’est qu’un maillon d’une hiérarchie de consistance de force croissante, esquissée dès l’introduction (l’inclusion \(\text{Node} \subset \text{Arc} \subset \text{Path} \subset \text{k}\)) :
| Niveau | Ce qui est garanti | Algorithme |
|---|---|---|
| Node (\(k=1\)) | chaque valeur satisfait les contraintes unaires | filtrage unaire |
| Arc (\(k=2\)) | chaque valeur a un support chez chaque voisin | AC-3 |
| Path (\(k=3\)) | chaque paire de valeurs a un support intermédiaire | PC-2 |
| k-Consistency (\(k\) quelconque) | généralisation aux \(k\) variables | — |
La forte k-consistance. Au niveau \(k\), on demande que toute affectation cohérente de \((k-1)\) variables puisse être étendue à une \(k\)-ième variable. La « forte » k-consistance va plus loin : elle exige que le CSP soit \(i\)-consistant pour tout \(i \le k\). Chaque niveau est plus fort que le précédent — mais aussi plus coûteux à établir.
Le point de bascule pratique. Le tableau récapitulatif du notebook en donne l’indice : la complexité de la k-consistance est exponentielle en \(k\). Même le saut de l’arc-consistance (\(O(e d^3)\)) à la consistance de chemin (\(O(n^3 d^3)\)) est déjà lourd ; pour \(k \ge 4\) le coût devient vite hors de portée. C’est pourquoi les solveurs réels (OR-Tools, Choco) s’arrêtent en pratique à l’arc-consistance et confient le reste à l’exploration (backtracking/MAC) et aux contraintes globales (AllDifferent, etc.) plutôt que d’enforcer une consistance d’ordre supérieur : le gain d’élagage ne compense plus un coût exponentiel.
Intuition. Plus le niveau de consistance est fort, plus on élimine tôt — mais chaque niveau supérieur paye un prix qui croît en flèche. Ce notebook s’arrête à AC-3/MAC précisément parce que c’est le point d’équilibre entre élagage exploitable et coût raisonnable.
La consistance de chemin (path consistency) est le niveau au-dessus de la consistance d’arc. Un chemin \((X_i, X_j, X_k)\) est path-consistent si pour toute assignation consistante \((X_i = a, X_k = c)\), il existe une valeur \(b \in D_j\) telle que \((X_i = a, X_j = b)\) et \((X_j = b, X_k = c)\) sont toutes deux consistantes.
Question : Completez l’implementation de path_consistency ci-dessous.
# Exercice 2 : Path Consistency
def path_consistency(csp, domains):
"""Applique la consistance de chemin.
Pour chaque triplet (Xi, Xm, Xj) ou Xm est un voisin commun,
verifie que chaque paire (a, c) dans Di x Dj a un support dans Dm.
A COMPLETER : implementer l'algorithme.
Returns:
True si le CSP est encore soluble, False sinon.
"""
# A COMPLETER
# Pour chaque paire de variables (Xi, Xj) liees par une contrainte :
# Pour chaque variable Xm intermediaire (voisin commun de Xi et Xj) :
# Pour chaque (a, c) dans Di x Dj :
# Verifier qu'il existe b dans Dm tel que
# constraint(Xi, a, Xm, b) ET constraint(Xm, b, Xj, c)
# Sinon, retirer (a, c) des paires possibles
pass
print("Exercice 2 : implementer path_consistency")Exercice 2 : implementer path_consistencyUn Sudoku 4x4 utilise les chiffres 1 a 4 dans une grille 4x4 divisee en 4 blocs 2x2. Les règles sont les mêmes que le 9x9 : chaque chiffre apparait exactement une fois par ligne, colonne et bloc.
Question : modelisez un Sudoku 4x4 comme CSP et comparez FC et MAC en termes d’assignations et de backtracks.
# Exercice 3 : Sudoku 4x4 comme CSP
def make_sudoku4_csp(grid):
"""Cree un CSP pour un Sudoku 4x4.
Args:
grid: liste de 16 valeurs (0 = case vide, 1-4 = valeur fixee)
par lignes : [g[0][0], g[0][1], g[0][2], g[0][3], g[1][0], ...]
A COMPLETER
"""
# Variables : (ligne, colonne) pour chaque case
# variables = [(i, j) for i in range(4) for j in range(4)]
# Domaines : {1,2,3,4} pour les cases vides, {valeur} pour les fixees
# domains = ...
# Voisins : meme ligne, meme colonne ou meme bloc 2x2
# neighbors = ...
# Contrainte : valeurs differentes
# return CSP(variables, domains, neighbors, different_values)
pass
# Grille de test
# . 2 | . .
# 4 . | . 1
# ----+----
# . . | 4 .
# . . | 2 .
# grid_4x4 = [0,2,0,0, 4,0,0,1, 0,0,4,0, 0,0,2,0]
# A COMPLETER : creer le CSP, resoudre avec FC et MAC, comparer
print("Exercice 3 : comparer FC et MAC sur Sudoku 4x4")Exercice 3 : comparer FC et MAC sur Sudoku 4x4Comparer le forward checking et larc consistency sur un CSP de coloration.
Indice : Mesurez le nombre de domaines reduits et le temps de resolution.
# Exercice : Comparaison des techniques de consistance
# TODO etudiant : Comparer le forward checking et larc consistency sur un CSP de coloration
# Indice : Mesurez le nombre de domaines reduits et le temps de resolution
result = None # TODO etudiant : remplacer par votre implementation
print("Exercice a completer : Comparaison des techniques de consistance")Exercice a completer : Comparaison des techniques de consistanceImplementer la stratégie MRV (Minimum Remaining Values) pour le choix de variable.
Indice : Choisissez la variable avec le plus petit domaine restant.
# Exercice : Heuristiques de variable ordering
# TODO etudiant : Implementer la strategie MRV (Minimum Remaining Values) pour le choix de variable
# Indice : Choisissez la variable avec le plus petit domaine restant
result = None # TODO etudiant : remplacer par votre implementation
print("Exercice a completer : Heuristiques de variable ordering")Exercice a completer : Heuristiques de variable ordering| Niveau | Definition | Complexite | Puissance d’elagage |
|---|---|---|---|
| Node Consistency | Chaque valeur satisfait les contraintes unaires | \(O(nd)\) | Faible |
| Arc Consistency (AC-3) | Chaque valeur a un support chez chaque voisin | \(O(ed^3)\) | Moderee a forte |
| Path Consistency | Chaque paire (a,c) a un support intermediaire | \(O(n^3 d^3)\) | Forte |
| k-Consistency | Generalisation a k variables | Exponentielle en k | Maximale |
| Algorithme | Propagation | Detection d’echec | Meilleur cas d’usage |
|---|---|---|---|
| Backtracking + MRV | Aucune | A l’assignation | Petits problemes |
| Forward Checking | 1 niveau (voisins) | Domaine vide chez un voisin | Problemes moyens |
| MAC | Cascade (AC-3) | Domaine vide n’importe ou | Problemes difficiles |
| Problème | BT (assigns) | FC (assigns) | MAC (assigns) | Gagnant |
|---|---|---|---|---|
| 4-Reines | petit | similaire | similaire | Tous equivalents |
| 8-Reines | moyen | reduit | très reduit | MAC |
| 12-Reines | grand | moyen | petit | MAC nettement |
Le prochain notebook CSP-3-Avance abordera : - Les contraintes globales (AllDifferent, etc.) et leur propagation specialisee - La recherche locale pour les CSP (Min-Conflicts) - Les CSP d’optimisation (COP) - Les decompositions de graphes pour les problemes structures
Ce notebook a couvert les techniques fondamentales de propagation de contraintes pour les CSP : la consistance de noeud (contraintes unaires), la consistance d’arc avec l’algorithme AC-3, le Forward Checking (propagation 1 niveau) et le MAC (propagation complete en cascade). Les benchmarks sur les N-Reines ont montre que MAC reduit le nombre d’assignations d’un facteur 40x par rapport au backtracking pur, confirmant que l’overhead de propagation est largement compense par la reduction de l’espace explore.
Ces techniques constituent le socle des solveurs CSP industriels comme OR-Tools. Le prochain notebook CSP-3-Avance etendra ces concepts aux contraintes globales (AllDifferent), a la recherche locale (Min-Conflicts) et aux problemes d’optimisation (COP), avec des applications directes en ordonnancement et planification.