L11: Basic Solution Procedures Flashcards
Define search.
To search is to make an (educated) guess among several alternatives- but be prepared to undo that guess and try a different alternative if the guess does not lead to a solution.
Define systematic search.
If there is a solution, it will be found.
If there is no solution, the search space will be exhausted and the search will report that there is no solution.
Begin with an empty assignment, incrementally attempt to extend it into a solution.
Define backtracking.
If we discover the current partial assignment cannot be extended to a solution (a dead end):
- Backtrack over last decision made.
- Try an alternative.
How does search as a tree traversal work?
The search for a solution to a CSP may be viewed as exploring a tree.
The root represents the CSP before any search choices.
Choices made correspond to branches in the tree.
Descendants of root node correspond to sub-CSPs.
Original CSP + partial assignment leaves simplified problem.
What is d-way branching?
In d-way branching, each branch under a parent node represents the assignment of one of d domain values from the domain of a particular variable.
E.g. if x= {1,2,3}, then we will have 3 branches from a parent or root node (3-way branching)
What is 2-way or binary branching?
Try extending partial assignment with x = v first. If no solution remove v from consideration before continuing.
The 2 branches from any node represent x = v and x ≠ v.
Each pair of branches divides the search space into two pieces. If we explore the whole tree, we will explore the whole search space.
Compare d-way and binary branching.
D-way branching makes presentation of simpler algorithms easier.
However, ….
What is the variable order?
The variable order is the order in which variables are assigned. The variable order can be fixed or dynamic.
What is a level in a search tree?
The level corresponds to the number of assignments made, also known as search depth.
Root: level 0
X1: level 1
X2: level 2
What is a future variable?
A variable that has not yet been assigned.
What is a past variable?
A variable that has been assigned.
What does each branch of the tree represent?
Each branch represents a partial assignment.
A branch that reaches depth n represents a complete assignment.
What is the generate and test search method?
A simple (but very expensive) method of solving a CSP.
Each possible complete assignment is generated and then tested to see if it satisfies all the constraints.
Brute force: only checks constraints after a complete assignment has been generated.
Systematic: guaranteed to find a solution if one exists (eventually).
Never used in practice.
What is the problem with generate and test searching for constraint optimisation problems?
We can’t stop when we find a satisfying assignment as it might not be the ‘best’ one. We have to examine all complete assignments.
What does the backtrack algorithm do?
Improves on G&T by incrementally extending partial solutions. Every time we make an assignment, we check to see if a constraint has been violated.
Systematic: guaranteed to find a solution if one exists.
Checks a constraint as soon as all of the variable that it constrains are instantiated.
Can spot dead-ends much faster than G&T. The sooner dead-ends are spotted, the more search you save.
