Mostly solvable problems Mostly un-solvable problems Cost of solving Critical value of order parameter Order parameter Significant increase of cost around critical value In CSPs, order parameter is constraint tightness & ratio Algorithms compared around phase transitionġ0 Tests Fix n, a, p1 and Fix n, a, t and
Generate a list of n.(n-1)/2 tuples of all combinations of 2 nodes Choose e elements from above list as constraints to between the n nodes If the graph is not connected, throw away, go back to step 4, else proceed Generate a list of a2 tuples of all combinations of 2 values For each constraint, choose randomly a number of tuples from the list to guarantee tightness t for the constraintĩ Phase transition Vary parameters: Number of variables: n Domain size: a, d Constraint tightness: t = |forbidden tuples| / | all tuples | Proportion of constraints (a.k.a., constraint density, constraint probability): p1 = e / emax Issues: Uniformity Difficulty (phase transition) Solvability of instances (for incomplete search techniques)Ĩ Model B Input: n, a, t, p1 Generate n nodes Various models exist (use Model B) Models A, B, C, E, F, etc. Use real-world data (anecdotal evidence) Use benchmarks Solver competition benchmarks Use randomly generated problems Various models of random generators Guaranteed with a solution Uniform or structured Number of nodes visited (#NV) Every time you call label Number of Backtracks (#BT) Every un-assignment of a variable in unlabel Number of constraint check (#CC) Every time you call check(i,j) CPU time Be as honest and consistent as possible Optional: Some specific criterion for assessing the quality of the improvement proposed Presentation of values: Descriptive statistics of criterion: average (also, median, mode, max, min) (qualified) run-time distribution Solution-quality distributionĬomparing NV and/or CC Common assumptions: for finding all solutions static/same orderings Choueiry (Shu-we-ri) Avery Hall, Room 360Ģ Outline Evaluation of (deterministic) BT search algorithms CSP parameters Comparison criteria Theoretical evaluations Empirical evaluationsģ p1 = e / emax, e is number of constraintsĬSP parameters Binary: n,a,p1,t Non-binary: n,a,p1,k,t Number of variables: n Domain size: a, d Degree of a variable: deg Arity of the constraints: k Constraint tightness: Proportion of constraints (a.k.a., constraint density, constraint probability) p1 = e / emax, e is number of constraintsĤ Comparison criteria Presentation of values: Presentation on theme: "Evaluation of (Deterministic) BT Search Algorithms"- Presentation transcript:ġ Evaluation of (Deterministic) BT Search Algorithmsįoundations of Constraint Processing CSCE421/821, Fall 2016 All questions to Piazza Berthe Y.
0 kommentar(er)
