# 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

• Poetry Meter and Rhyme. What is Poetic Meter? Poetic meter is a generally regular pattern of stressed and unstressed syllables. ... Step 2: If possible, identify the type of foot used most often in each line (iamb, trochee, spondee, anapest,...
• 1 John 4:3 KJV "And every spirit that confesseth not that Jesus Christ is come in the flesh is not of God: and this is that spirit of antichrist, whereof ye have heard that it should come; and even now...
• Reassess the casualty in Tactical Field Care - remove it if it is not needed unless the casualty is in shock. ... volunteers are given mind-altering substances like ketamine and tested on tasks like manual dexterity. Tactical Combat Casualty Care...
• Tri-County Differences in Procedures and Policies. Navigating the Broward County e-Issuance System for Summonses, Writs and Subpoenas. Certified Copies Through the Portal. Avoiding Pitfalls in e-Filing from the Desk of the Broward County Clerk's Office Signing Your Pleadings Digitally. Compiling...
• But things haven't really bothered me because I'm just here to learn." "I don't really experience much prejudice or racism much here. Like I know I've heard stories up the wazoo about people being called names and stuff like that...
• ANTECEDENTES PERSONALES IMOGENE KING 1945 Imogene King se diplomó en Enfermería en el St. John´s Hospital School of the Nursing en St. Louis. 1948 Obtuvo su BS de educación en Enfermería 1957 Obtuvo su MS en Enfermería por la St....
• Visual P1 and N1 . Omnipresent in visual ERP studies . Higher amplitude and/or shorter latencies in the contralateral hemisphere (Di Russo et al., 2002
• As we work to help create the bridge between secondary education and whatever is next - let us help our students 'mind the gap' with Incightful Transitions Curriculum. Education Programs. ... PowerPoint Presentation Last modified by: