INSTRUCTIONS AU MODÈLE - Répondre sans outil externe ni Internet. - Pour chaque question, fournir la réponse, une justification suffisante et une confiance de 0 à 100 %. - Ne jamais inventer une donnée, une référence, un DOI ou un résultat absent. - Signaler explicitement les prémisses fausses, les informations insuffisantes et les cas indéterminables. - Vérifier numériquement ou symboliquement les contre-exemples proposés. - Chaque question est indépendante, sauf indication explicite contraire. Q062 — Dans un CSP binaire sur un arbre, expliquer pourquoi un passage de cohérence approprié suivi d’une affectation ordonnée permet de trouver une solution sans backtracking.
Merci pour cette question portant sur la théorie des contraintes. Voici mon analyse. ## Réponse Dans un réseau de contraintes binaires dont le graphe de contraintes est un arbre, on peut garantir une solution sans backtracking en appliquant d'abord un passage de cohérence d'arc, puis en affectant les variables dans un ordre approprié. ### Justification **Première étape : cohérence d'arc.** On applique l'algorithme de cohérence d'arc (par exemple AC-3) sur tout le réseau. Après ce passage, pour chaque contrainte binaire reliant deux variables X et Y, toute valeur du domaine de X possède au moins un support dans le domaine de Y, et réciproquement. Autrement dit, plus aucune valeur n'est isolée par une contrainte. **Deuxième étape : affectation ordonnée.** On choisit une racine quelconque de l'arbre, puis on ordonne les variables selon un parcours en profondeur depuis la racine, les parents avant les enfants. On affecte alors les variables dans cet ordre. À chaque étape, on choisit pour la variable courante une valeur qui satisfait la contrainte avec son parent, déjà affecté. La cohérence d'arc garantit qu'une telle valeur existe toujours. **Pourquoi cela fonctionne sans backtracking.** La propriété clé est que, dans un arbre, chaque variable n'a qu'un seul chemin vers la racine. Lorsqu'on affecte une variable, elle n'est contrainte que par son parent, déjà fixé, et par ses enfants, pas encore affectés. La cohérence d'arc assure que, quelle que soit la valeur choisie pour le parent, il existe au moins une valeur pour l'enfant satisfaisant la contrainte. Comme les sous-arbres sont indépendants entre eux, aucune contrainte ne reliant deux branches différentes, le choix fait pour une branche ne peut jamais invalider une autre branche. Aucun retour en arrière n'est donc nécessaire : chaque choix local est définitivement sûr. Il convient de préciser que ce résultat suppose que le réseau est binaire, c'est-à-dire que les contraintes portent sur deux variables au plus, et que le graphe de contraintes est bien un arbre, c'est-à-dire connexe et acyclique. Si le graphe contenait des cycles, la cohérence d'arc seule ne suffirait plus et un backtracking pourrait devenir nécessaire. ### Confiance **92 %.** Ce résultat est un théorème classique et bien établi de la théorie des réseaux de contraintes, associé notamment aux travaux fondateurs de Freuder sur les réseaux sans backtracking. Ma confiance n'est pas de 100 % car je l'énonce de mémoire, sans pouvoir vérifier ici la formulation exacte de la source, mais le raisonnement structurel est solide et vérifiable.
Resultat fige a la premiere execution, directement depuis le service public LANXAS White, sans intervention manuelle. Cette page est permanente et peut etre re-consultee pour verification.