Arc-Consistency (AC3) et un défi?

Question

En appliquant des algorithmes de cohérence d'arc (AC3) sur un problème de satisfaction de contraintes, si le domaine d'une variable est vide, quelle est la prochaine étape?

1) halt. 

2) do backtrack. 

3) start from another initial state. 

4) it depends on that we are in which step. 

Solution (4). Je pense que (1) est vrai parce que cela signifie que nous ne pouvons pas trouver une affectation cohérente et arrêter. Quelqu'un peut-il décrire pourquoi (4) est vrai?

Answer 1

Avec le particular algorithm que vous utilisez, si le domaine d'une variable se rétracte jusqu'à ce qu'il soit vide, cela signifie que le problème de contrainte n'a pas de solution. Par conséquent, l'algorithme doit s'arrêter dans l'état d'échec.