Outline Optimal csPs Review of a Conflict-directed A* Generating the Best Kernel Intelligent Tree Expansion Extending to Multiple Solutions Performance Comparison 3/17/2004 copyright Brian Williams, 2002 Constraint Satisfaction Problem CSP=<X, DX,C> variables X with domain Dx Constraint C(X) Dx >True, False] Find X in Dxst C(X)is True RG.B Dififerent-color constrain copyright Brian Williams, 20023/17/2004 copyright Brian Williams, 2002 3 Outline • Optimal CSPs ƒ Review of A* ƒ Conflict-directed A* ƒ Generating the Best Kernel ƒ Intelligent Tree Expansion ƒ Extending to Multiple Solutions ƒ Performance Comparison 3/17/2004 copyright Brian Williams, 2002 4 Constraint Satisfaction Problem CSP = <X, DX,C> ƒ variables X with domain DX ƒ Constraint C(X): DX → {True,False} Find X in DX s.t. C(X) is True R,G,B R, G G Different-color constraint V1 V2 V3