Scribd
Upload
949 views22 pages

Backtracking Search For CSP

The document discusses Constraint Satisfaction Problems (CSP), which involve finding solutions that meet specific constraints and are applicable in various fields like scheduling and planning. It highlights the use of heuristics, particularly the Minimum Remaining Values (MRV) and min-conflicts approaches, in optimizing the search process for solutions. Additionally, it references key textbooks for further reading on artificial intelligence concepts.

Uploaded by

harshil.sharma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
949 views22 pages

Backtracking Search For CSP

The document discusses Constraint Satisfaction Problems (CSP), which involve finding solutions that meet specific constraints and are applicable in various fields like scheduling and planning. It highlights the use of heuristics, particularly the Minimum Remaining Values (MRV) and min-conflicts approaches, in optimizing the search process for solutions. Additionally, it references key textbooks for further reading on artificial intelligence concepts.

Uploaded by

harshil.sharma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 22

Course Name: Introduction to Artificial Intelligence

Topic: Backtracking search for CSP


Prepared By: Ms. Harshil Sharma, Assistant Professor
Department of FCE
DEFINING CONSTRAINT SATISFACTION PROBLEMS (CSP)
DEFINING CONSTRAINT SATISFACTION PROBLEMS (CSP)
CONSTRAINT SATISFACTION PROBLEMS (CSP)

CSP is a specific type of problem-solving approach that


involves identifying constraints that must be satisfied and
finding a solution that satisfies all the constraints.
CSP has been used in a variety of applications, including
scheduling, planning, resource allocation, and automated
reasoning.
DEFINING CONSTRAINT SATISFACTION PROBLEMS (CSP)
DEFINING CONSTRAINT SATISFACTION PROBLEMS (CSP)
DEFINING CONSTRAINT SATISFACTION PROBLEMS (CSP)
IN THIS WE WILL ANSWER THESE QUESTIONS
 Map coloring problem for this
map.
 Domain={Red,Green,Blue}
 Constraint- adjacently connected
nodes cannot have same color
 If some variable X has no legal values left, the MRV heuristic will
select X and failure will be detected immediately—avoiding pointless
searches through other variables.
 The MRV heuristic usually performs better than a random or static
ordering, sometimes by orders of magnitude, although the results vary
depending on the problem.
 The MRV heuristic doesn’t help at all in choosing the first region to
color in Australia, because initially every region has three legal colors.
Once a variable has been selected, the algorithm must decide
on the order in which to examine its values.
LOCAL SEARCH FOR CSPS

 Local search algorithms turn out to be very effective in


solving many CSPs.
 They use a complete-state formulation where each state as
signs a value to every variable, and the search changes the
value of one variable at a time.
 Uses the min-conflicts heuristic approach.
 Takes less time.
LOCAL SEARCH FOR CSPS
 As an example, in the 8-queens problem, we start on the left
with a complete assignment to the 8 variables; typically this
will violate several constraints.
 We then randomly choose a conflicted variable, which turns
out to be Q8, the rightmost column.
 We’d like to change the value to something that brings us
closer to a solution; the most obvious approach is to select
the value that results in the minimum number of conflicts
with other variables—the min-conflicts heuristic.
LOCAL SEARCH FOR CSPS
LOCAL SEARCH FOR CSPS
REFERENCE BOOK

ArtificialIntelligence: A Modern Approach S.


Russell and P. Norvig Prentice Hall
Artificial Intelligence: Rich and Knight , 3rd edition
Thank You!!

You might also like