State space search pdf

A Start State. The state from where the search begins. A Goal Test. A function that looks at the current state returns whether or not it is the goal state. The Solution to a search problem is a sequence of actions, called the plan that transforms the start state to the goal state.

This plan is achieved through search algorithms. Types of search algorithms: There are far too many powerful search algorithms out there to fit in a single article.

Instead, this article will discuss six of the fundamental search algorithms, divided into two categories, as shown below. Note that there is much more to search algorithms than the chart I have provided above. However, this article will mostly stick to the above chart, exploring the algorithms given there. Uninformed Search Algorithms: The search algorithms in this section have no additional information on the goal node other than the one provided in the problem definition. Uninformed search is also called Blind search.

The following uninformed search algorithms are discussed in this section. A strategy, describing the manner in which the graph will be traversed to get to G. A fringe, which is a data structure used to store all the possible states nodes that you can go from the current states. A tree, that results while traversing to the goal node. A solution plan, which the sequence of nodes from S to G. Depth First Search : Depth-first search DFS is an algorithm for traversing or searching tree or graph data structures.

The algorithm starts at the root node selecting some arbitrary node as the root node in the case of a graph and explores as far as possible along each branch before backtracking. Example: Question. The equivalent search tree for the above graph is as follows. The traversal is shown in blue arrows. Time complexity: Equivalent to the number of nodes traversed in DFS. Space complexity: Equivalent to how large can the fringe get. Completeness: DFS is complete if the search tree is finite, meaning for a given finite search tree, DFS will come up with a solution if it exists.

Optimality: DFS is not optimal, meaning the number of steps in reaching the solution, or the cost spent in reaching it is high. Breadth First Search : Breadth-first search BFS is an algorithm for traversing or searching tree or graph data structures. Time complexity: Equivalent to the number of nodes traversed in BFS until the shallowest solution. Optimality: BFS is optimal as long as the costs of all edges are equal.

In other words, traversing via different edges might not have the same cost. The goal is to find a path where the cumulative sum of costs is the least. The cost of each node is the cumulative cost of reaching that node from the root. Based on the UCS strategy, the path with the least cumulative cost is chosen.

Note that due to the many options in the fringe, the algorithm explores most of them so long as their cost is low, and discards them when a lower-cost path is found; these discarded traversals are not shown below. The actual traversal is shown in blue.

Advantages: UCS is complete only if states are finite and there should be no loop with zero weight. UCS is optimal only if there is no negative cost.

No information on goal location. Informed Search Algorithms: Here, the algorithms have information on the goal state, which helps in more efficient searching.

This information is obtained by something called a heuristic. In this section, we will discuss the following search algorithms. For example — Manhattan distance, Euclidean distance, etc. Depth First Search : Depth-first search DFS is an algorithm for traversing or searching tree or graph data structures.

The algorithm starts at the root node selecting some arbitrary node as the root node in the case of a graph and explores as far as possible along each branch before backtracking. Example: Question. The equivalent search tree for the above graph is as follows.

The traversal is shown in blue arrows. Time complexity: Equivalent to the number of nodes traversed in DFS. Space complexity: Equivalent to how large can the fringe get. Completeness: DFS is complete if the search tree is finite, meaning for a given finite search tree, DFS will come up with a solution if it exists.

Optimality: DFS is not optimal, meaning the number of steps in reaching the solution, or the cost spent in reaching it is high. Breadth First Search : Breadth-first search BFS is an algorithm for traversing or searching tree or graph data structures.

Time complexity: Equivalent to the number of nodes traversed in BFS until the shallowest solution. Optimality: BFS is optimal as long as the costs of all edges are equal. In other words, traversing via different edges might not have the same cost. The goal is to find a path where the cumulative sum of costs is the least. The cost of each node is the cumulative cost of reaching that node from the root. Based on the UCS strategy, the path with the least cumulative cost is chosen.

Note that due to the many options in the fringe, the algorithm explores most of them so long as their cost is low, and discards them when a lower-cost path is found; these discarded traversals are not shown below. The actual traversal is shown in blue.

Advantages: UCS is complete only if states are finite and there should be no loop with zero weight. UCS is optimal only if there is no negative cost. No information on goal location. Informed Search Algorithms: Here, the algorithms have information on the goal state, which helps in more efficient searching.

This information is obtained by something called a heuristic. In this section, we will discuss the following search algorithms. For example — Manhattan distance, Euclidean distance, etc.

Lesser the distance, closer the goal. Different heuristics are used in different informed algorithms discussed below. Greedy Search: In greedy search, we expand the node closest to the goal node. Lower the value of h x , closer is the node from the goal. Strategy: Expand the node closest to the goal state, i.

Find the path from S to G using greedy search. The heuristic values h of each node below the name of the node. We choose D, as it has the lower heuristic cost. We choose E with a lower heuristic cost.

This entire traversal is shown in the search tree below, in blue. Disadvantage: Can turn into unguided DFS in the worst case. In this search, the heuristic is the summation of the cost in UCS, denoted by g x , and the cost in the greedy search, denoted by h x. The summed cost is denoted by f x. Here, h x is called the forward cost and is an estimate of the distance of the current node from the goal node.

And, g x is called the backward cost and is the cumulative cost of a node from the root node. The entire work is shown in the table below. Note that in the fourth set of iteration, we get two paths with equal summed cost f x , so we expand them both in the next set.