# Semantic Web in BioInformatics - McMaster University

CSP: Definition, Creation, and Algorithms Mr. Tianbing Lin [email protected] Dr. Goodwin Scott University of Windsor Outline Introduction of Constraint Satisfaction Problem Algorithms: Backtracking, Forward Checking, Back Jump, Dynamic Backtracking Evaluation: Random CSP, N-Queen Experimental Result Question? 2 20/2/9

Introduction of CSP Given a set of variables X={x1, x2xn} and a finite set Di of possible values (its domain) for every variable. Given some constraints restricting the values How to assign values for all the variables so that all the constraints are satisfied? 3 20/2/9 Introduction of CSP: N-Queen Variables:

Q1, Q2, Q3, Q4 Domain: {1, 2, 3, 4} Constraints: Qi<>Qj: Not in the same row |Qi-Qj|<>|i-j|: Not in diagonal Extentional Constraints: (Q1, Q2): {(1,3), (1,4), (2, 4), (3,1), (4, 1), (4, 2)} (Q1, Q3): 4 20/2/9 Introduction of CSP: Graph Coloring Paint the graph with different colors 3 Color?

5 20/2/9 Algorithms: Overview Systematic Algorithms: Backtracking, Forward Checking Search the whole solution space systematically In most cases, slow Heuristical Algorithms: Hill-climbing, Simulated

Annealing, Genetic Algorithm 6 In some cases, fast Might not get solution at all. 20/2/9 Algorithms: Backtracking 7 20/2/9 Algorithms: Forward Checking 8

20/2/9 Algorithms: Back Jumping if we find all the values of Variable C are invalid because they are conflict with the value of Variable A, then we don't need to change the value of B to check C again. We can directly jump to another value of Variable A, skip other values of B (under A1 value). N-Queen problem can not demonstrate this algorithm. 9 20/2/9 Algorithms: Dynamic Backtracking

When we back jump to A from C, we reset value of B. Do we really have to reset B, if its not conflict with A or C? We dynamically change the order of variables: Before, A->B->C. Now: B->A->C 10 20/2/9 Algorithms: Dynamic Backtracking Example of Graph Coloring:

Weve finished painting the 3 slides in the north and 2 slides in the south. We dont need to change the value of south slides. 11 20/2/9 Evaluation: N-Queen N-Queen is a nature test scheme. Normally a PC can solve 30-Queen problem in reasonable time using above algorithms. Drawback: Every assignment create (almost) same number of no-good for other variables.

12 20/2/9 Evaluation: Random CSP Randomized constraints can be created according number of variables, average number of constraints, average tightness. Use average solving time to compare different algorithms. 13 20/2/9 Experimental Results

Overal l Compari son f or one sol ut i on 70000 60000 Mi l l i seconds 50000 40000 30000 20000 BackTracki ng Forward Check

Back J ump Dynamic Backtracki ng 76 73 70 67 64 61 58 55

52 49 46 43 40 37 34 31 28

25 22 19 16 13 10 7 4 14 0

1 10000 20/2/9 Experimental Results: Sort by Variable Number 6000 5000 4000 3000 2000

1000 0 13 14 15 Back Tr acki ng 15 16 For war d Check Back J ump Dynami c Backt r ack

20/2/9 Experimental Results: Sort by Tightness Sor t By Ti ght ness ( Al l Sol ut i on) 90000 80000 70000 Mi l l i seconds 60000 50000 40000 30000 20000 10000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

Back Tr acki ng 16 For war d Check Back J ump 20/2/9 Considering Tightness 17 Constraint density cant assure the tightness of the CSP . For example, we have CSP A and CSP B (domain size: 3, 3 variables):

Density of Constraint 1 and Density of Constraint 2 are 33.3%. Solution is empty, so the tightness is 0/27 20/2/9 Considering Tightness 18 Density of Constraint 1 and Density of Constraint 2 are 33.3%, Can have 9 solutions{(1, 1, 1) (1, 1, 2) (1, 1, 3) (2, 1, 1) (2, 1, 2) (2, 1, 3) (3, 1, 1) (3, 1, 2) (3, 1, 3)}, which means the tightness is 9/27=33%. 20/2/9

Considering Tightness The smallest constraint density of all the constraints is the maximum value of tightness the CSP can have. The exact value of the tightness depends on the relation of the constraint tables. 19 20/2/9 Reference

20 [1] Bartk, R., Constraint Programming: In Pursuit of the Holy Grail, in Proceedings of the Week of Doctoral Students (WDS99), Part IV, MatFyzPress, Prague, June 1999, pp. 555-564. [2] Malek Mouhoub, class notes of Artificial Intelligence. [3] Prosser, P., Binary constraint satisfaction problems: Some are harder than others, Proceedings ECAI-94 (11th European Conference on Artificial Intelligence) [4] White, S, Enhancing Knowledge Acquisition with Constraint Technology, PhD Thesis, University of Aberdeen [5] Pedro Meseguer, CSP: Constraint Programming [6] Joe Culberson and Toby Walsh , Tightness of Constraint Satisfaction Problems

[7] Peter van Beek and Rina Dechter, Constraint Tightness and Looseness versus Local and Global Consistency 20/2/9 Thank you Question? 21 20/2/9

## Recently Viewed Presentations

• Find percent yield if an experiment yielded 132.4 grams of carbon dioxide. C2H4 + 3 O2 2 CO2 + 2 H2O Products Percent Yield Theoretical Yield Maximum amount of product Calculation Balanced Equation Given mass Molar Mass Mole Ratios Actual...
• Maya, Aztec, and Inca Civilizations Pre-Columbian Society in North and South America ... Farmed potatoes on terraces God-kings = intermediaries b/t heaven and earth Social Hierarchy Aristocrats lived privileged lives (fine foods, embroidered clothes, and large ears spools) Inca often...
• Watson and . Raynor. were never able to see if they could remove the fear response. Little Albert may well have had a fear or furry animals for ever more. When we move onto the treatments section of this topic...
• Anomaly Detection. Lecture Notes for Chapter 9. Introduction to Data Mining, 2nd Edition. by. Tan, Steinbach, Karpatne, Kumar. With additional slides and modifications by Carolina Ruiz, WPI
• Steven W. Evans, Christine Brady, Lee Kern, Christiana Andrews and the CARS Research Team Criteria Applied to Students Participating in Pilot We have parent BASC and CPS data for 32 participating students at two sites Met neither criteria - 2...
• A humanist is an idealist who is interested in and motivated by concerns about the broader human condition and the quality of people's lives. ... Many Marxist theorists since Marx have tried to explain why there was no collapse of...
• Pauli Exclusion Principle: at most two electrons can be assigned to any one atomic orbital and these two electrons must have opposite spins ms ml l n * In IS last Tuesday, you were tracing the history of atomic models...
• I needed an activity that effectively explored plate motion, but that was more interactive than a worksheet calculating spreading rates from magnetic anomalies How I used the EET Chapter Students were first introduced to the different ways of measuring plate...