# COMP7404 Topic 2 Beyond Classical Search

Author: Yu Zhang | 478 words, 3 minutes | 2020-10-04 | Category: Notes

Translations: ZH

# COMP7404 Computational Intelligence and Machine Learning

Planning vs Identification

• Planing: sequence of actions
• The path to the goal is the important thing
• Paths have various costs, depths
• Heuristics to guide, frontier to keep backups
• Identification: assignments to variables
• The goal itself is important, not the path

Local Search can find solutions faster for specific types of identification problems

Local Search

• Evaluate and modify one current state rather than systematically explore paths from an initial state
• Suitable for problems were all that matters in the solution state and not the path cost to reach it
• Although local search algorithms are not systematic they have two advantages
• Require very little memory
• Often find reasonable solutions in large spaces

Local Search Algorithm

``````	Randomly initialize currentState
If cost of currentState == 0 return currentState
If min(cost(getNeighbors(currentState))) > cost(currentState)
goto step 1 (we have reached a local minimum)
Select cheapest neighbor as currentState and goto step2
``````

Example: 8-Queens

• States
• Each state has 8 queens on board, one per column
• Successors
• All possible states generated by moving single queen to another square in the same column
• Cost function
• Number of pairs of queens that are attacking each other, either directly and indirectly

Constraint Satisfaction Problems

CSPs use a factored representation for states

• A set of variables, each of which has a value

Defining CSPs

• A CSP consists of three components
• A set of variables, X = {X1,…,Xn}
• A set of domains, D = {D1,…,Dn}, where Di = {V1,…,Vk} for each variable Xi
• A set of constraints C which specify allowable combinations of values
• To solve a CSP we need to define a state space
• Each state is defined by an assignment of values to some or all variables {Xi = Vi, Xj = Vj,…}

Solving CSPs

• States are defined by the values assigned so far
• Initial state
• Empty assignment {}
• Successor function
• Assign a value to an unassigned variable
• Goal test
• Current assignment is complete and consistent

Solutiona to CSPs

• Consistent - No constraints are violated
• Complete - Every variable is assigned

Backtracking Search (The basic algorithm for solving CSPs)

Idea

• Only consider assignments to a single variable at each point
• Only allow legal assignemnts to each point

DFS with these two ideas is called backtracking search

Improving Backchecking

Idea

• Forward checking (FC)
• Constraint propagation (AC-3)

Filtering: Forward Checking

• Filtering
• Keep track of domains for unassigned variables and cross off bad options
• Forward checking
• Cross off values that violate a constraint when added to the existing assignment

Improving Backtracking Further

• Variable Ordering
• Minimum remaining values (MRV)
• Choose the variable with the fewest legal left values in its domain
• Most constraint variable
• Fail-first heuristic
• Tie-breaker among MRV variables
• Degree Heuristic (Deg)
• Choose the variable with the most constraints on remaining variables
• Value Ordering
• Least constraining value (LCV)
• Choose the value that rules out the fewest values in the remaining variables

## Related Posts

2020-11-11
xDeepFM for Recommender Systems - 推荐系统
2020-10-05