Search Methods

Brute Force

Try all combinations for all regions.

Informed Search

Choose an element that does not conflict with neighbours.

General Search - Types

Instead of writing a custom program for every problem to be solved, general-purpose methods aim to write search algorithms into which individual problems can be plugged-in.

State Space Search / Solution Space Search

• Describe the given state
• Devise an operator to choose an action in each state
• Navigate the state space in search of the desired or goal state

State Space Search → Graph Search

• A state is a representation of a situation.
• A MoveGen function captures the moves that can be made in a given state.
• It returns a set of states – neighbours – resulting from the moves.
• The state space is an implicit graph defined by the MoveGen function.
• A GoalTest function checks if a given state is a goal state.
• A search algorithm navigates the state space using these two functions

Constraint Processing