Constraints and Search约束的有哪些信誉好的足球投注网站.pptVIP

Looking inside search Three key insights constrainedness “knife-edge” backbone structure 2+p-SAT Suggests branching heuristics also insight into branching mistakes Constrainedness knife-edge kappa against depth/n Constrainedness knife-edge Seen in other problem domains number partitioning, … Seen on “real” problems exam timetabling (alias graph colouring) Suggests branching heuristic “get off the knife-edge as quickly as possible” minimize or maximize-kappa heuristics must take into account branching rate, max-kappa often therefore not a good move! Minimize constrainedness Many existing heuristics minimize-kappa or proxies for it For instance Karmarkar-Karp heuristic for number partitioning Brelaz heuristic for graph colouring Fail-first heuristic for constraint satisfaction … Can be used to design new heuristics removing some of the “black art” Backbone Variables which take fixed values in all solutions alias unit prime implicates Let fk be fraction of variables in backbone l/n 4.3, fk vanishing (otherwise adding clause could make problem unsat) l/n 4.3, fk 0 discontinuity at phase boundary! Backbone Search cost correlated with backbone size if fk non-zero, then can easily assign variable “wrong” value such mistakes costly if at top of search tree Backbones seen in other problems graph colouring TSP … Can we make algorithms that identify and exploit the backbone structure of a problem? 2+p-SAT 2-SAT is polynomial (linear) but 3-SAT is NP-complete 2-SAT, unlike 3-SAT, has no backbone discontinuity Morph between 2-SAT and 3-SAT fraction p of 3-clauses fraction (1-p) of 2-clauses 2+p-SAT maps from P to NP p0, 2+p-SAT is NP-complete * Constrainedness Including slides from Toby Walsh Constraint satisfaction Constraint satisfaction problem (CSP) is a triple V,D,C where: V is set of variables Each X in V has set of values, D_X Usually assume finite domain {true,false}, {red,blue,green}, [0,10], … C is set of constraints Goal: find assignment of values to variab