CONTENTS
1.Search Algorithms,
2. Random search,
3. Search with closed and open list,
4. Depth first and Breadth first search,
5. Heuristic search,
6. Best first search,
7. A* algorithm
1. Search Algorithms
A search method is defined by picking the order of node expansion. Strategies are evaluated
along the following dimensions:
completeness: does it always find a solution if one exists?
time complexity: number of nodes generated
space complexity: maximum number of nodes in memory
optimality: does it always find the shortest path solution?
Time and space complexity are measured in terms of
b: maximum branching factor of the search tree
d: depth of the shortest path solution
m: maximum depth of the state space (may be ∞)
1.1 Uninformed techniques
Systematically searches complete graph, unguided. Also known as brute force, naïve, or blind.
While searching you have no clue whether one non-goal state is better than any other. Your
search is blind. Uninformed search algorithms have no additional information on the goal node
other than the one provided in the problem definition. The plans to reach the goal state from the
start state differ only by the order and length of actions.
Examples: Depth First Search and Breadth First Search.
We do not use the path cost when executing uninformed search. The transition model
defines a state space, which can be represented as a directed graph (vertices are states, edges are
actions).
For example, consider the 8-puzzle game, which requires that tokens are shifted around until a
particular goal state is reached. Search space size makes the search tedious. This problem is
called Combinational Explosion.
,1.2 Informed techniques
Use problem specific information to guide search in promising directions. Informed Search
algorithms have information on the goal state which helps in more efficient searching. This
information is obtained by a function that estimates how close a state is to the goal state. These
strategies often depend on the use of heuristic information (heuristic search function). Heuristic
search function h(n), is estimated cost of the cheapest path from node n to goal node. Example:
Best first search, A* algorithm.
1.3 Search Algorithms categorization
1.4 Difference between uninformed and informed search
,Uninformed Search is a class of general purpose algorithms that operates in a brute force way. The
search space is explored without leveraging on any information on the problem. Also called
blind search, or naïve search
Since the methods are generic they are intrinsically inefficient. Uninformed search strategies that do
not take into account the location of the goal. Intuitively, these algorithms ignore where they are
going until they find a goal and report success.
E.g. Random Search
2. Random Search
This method selects randomly a new state from the current one. If the goal state is reached, the
search terminates. Otherwise the methods randomly select an other operator to move to the next
state. Goal achievement is not insured in finite time.
Algorithm : Random Search
Step 1: n=initial node.
Step 2: Finish if n is the goal.
Step 3: Expand n to get a set S of child-nodes.
, Step 4: Select a node n’ from S at random.
Step 5: n=n’, return to 2.
A key issue in search is limiting the portion of the state space that must be explored to find a
solution.
The portion of the search space explored can be affected by the order in which states (and thus
solutions) are examined.
The search strategy determines this order by determining which node (partial solution) will be
expanded next.
Repeated states
Failure to detect repeated states can turn a linear problem into an exponential.
Avoiding Repeated States
Do not re-generate the state you just came from.
Do not create paths with cycles.
Do not generate any state that was generated before (using a hash table to store all generated
nodes) Markov Assumption
Add Closed list to search algorithm or cleverly construct search space Closed list contain the
states that are already visited.
3. Search with closed and open list
To avoid repeated state, Search is implemented using two lists called OPEN and CLOSED are
maintained.
The OPEN list contains those states that are to be expanded and CLOSED list keeps track of
states already expanded.
Here OPEN list is used as a queue. CLOSED list as a stack.
Advantage of open and closed list
The CLOSED list is a collection of all expanded nodes. This means that those are nodes that
were already "searched". This prevents the search from visiting nodes again and again.
CLOSED list generally improves the speed of algorithm. It prevents the algorithm from
expanding pre-visited nodes.
Maybe you reach node A that was expanded previously through another branch. This will let you
cut this branch and try another path.
General Search Algorithm
1.Search Algorithms,
2. Random search,
3. Search with closed and open list,
4. Depth first and Breadth first search,
5. Heuristic search,
6. Best first search,
7. A* algorithm
1. Search Algorithms
A search method is defined by picking the order of node expansion. Strategies are evaluated
along the following dimensions:
completeness: does it always find a solution if one exists?
time complexity: number of nodes generated
space complexity: maximum number of nodes in memory
optimality: does it always find the shortest path solution?
Time and space complexity are measured in terms of
b: maximum branching factor of the search tree
d: depth of the shortest path solution
m: maximum depth of the state space (may be ∞)
1.1 Uninformed techniques
Systematically searches complete graph, unguided. Also known as brute force, naïve, or blind.
While searching you have no clue whether one non-goal state is better than any other. Your
search is blind. Uninformed search algorithms have no additional information on the goal node
other than the one provided in the problem definition. The plans to reach the goal state from the
start state differ only by the order and length of actions.
Examples: Depth First Search and Breadth First Search.
We do not use the path cost when executing uninformed search. The transition model
defines a state space, which can be represented as a directed graph (vertices are states, edges are
actions).
For example, consider the 8-puzzle game, which requires that tokens are shifted around until a
particular goal state is reached. Search space size makes the search tedious. This problem is
called Combinational Explosion.
,1.2 Informed techniques
Use problem specific information to guide search in promising directions. Informed Search
algorithms have information on the goal state which helps in more efficient searching. This
information is obtained by a function that estimates how close a state is to the goal state. These
strategies often depend on the use of heuristic information (heuristic search function). Heuristic
search function h(n), is estimated cost of the cheapest path from node n to goal node. Example:
Best first search, A* algorithm.
1.3 Search Algorithms categorization
1.4 Difference between uninformed and informed search
,Uninformed Search is a class of general purpose algorithms that operates in a brute force way. The
search space is explored without leveraging on any information on the problem. Also called
blind search, or naïve search
Since the methods are generic they are intrinsically inefficient. Uninformed search strategies that do
not take into account the location of the goal. Intuitively, these algorithms ignore where they are
going until they find a goal and report success.
E.g. Random Search
2. Random Search
This method selects randomly a new state from the current one. If the goal state is reached, the
search terminates. Otherwise the methods randomly select an other operator to move to the next
state. Goal achievement is not insured in finite time.
Algorithm : Random Search
Step 1: n=initial node.
Step 2: Finish if n is the goal.
Step 3: Expand n to get a set S of child-nodes.
, Step 4: Select a node n’ from S at random.
Step 5: n=n’, return to 2.
A key issue in search is limiting the portion of the state space that must be explored to find a
solution.
The portion of the search space explored can be affected by the order in which states (and thus
solutions) are examined.
The search strategy determines this order by determining which node (partial solution) will be
expanded next.
Repeated states
Failure to detect repeated states can turn a linear problem into an exponential.
Avoiding Repeated States
Do not re-generate the state you just came from.
Do not create paths with cycles.
Do not generate any state that was generated before (using a hash table to store all generated
nodes) Markov Assumption
Add Closed list to search algorithm or cleverly construct search space Closed list contain the
states that are already visited.
3. Search with closed and open list
To avoid repeated state, Search is implemented using two lists called OPEN and CLOSED are
maintained.
The OPEN list contains those states that are to be expanded and CLOSED list keeps track of
states already expanded.
Here OPEN list is used as a queue. CLOSED list as a stack.
Advantage of open and closed list
The CLOSED list is a collection of all expanded nodes. This means that those are nodes that
were already "searched". This prevents the search from visiting nodes again and again.
CLOSED list generally improves the speed of algorithm. It prevents the algorithm from
expanding pre-visited nodes.
Maybe you reach node A that was expanded previously through another branch. This will let you
cut this branch and try another path.
General Search Algorithm
