# Searching for Solutions

First step to solve a problem is formulation of the problem. After discussing problem formulation in the previous post Problem Solving Agents, in this post we discuss how to solve the problem.

A solution is an action sequence, so search algorithms work by considering various possible action sequences. The possible action sequences starting at the initial state form a **search tree** with the initial state at the root, the branches are actions and the **nodes** correspond to states in the state space of the problem.

Suppose we want to find a path from city of **Arad** to **Bucharest**. the root node of the tree corresponds to the initial state, \(In(Arad)\). The first step is to test whether this state is a goal state, clearly it is not. Then we need to consider taking various actions. We do this by **expanding** the current state ; that is, applying each legal action in the current state, thereby, **generating** a new set of states. In this case, we add three branch from the node \(In(Arad)\) leading to three new **child nodes**: \(In(Sibiu)\), \(In(Timisora)\) and \(In(Zerind)\). Now we must choose which of the three possibilities consider further.

This is the essence of search — following up one option now and putting the other aside for later, in case the first choice does not lead to a solution. Suppose we choose **Sibiu** first. First we check, whether it is a goal state or not? Since, it is not, we expand it to get \(In(Arad)\), \(In(Fagaras\), \(In(Oradea\) and \(In(Rimnicu Vilcea)\). We can then choose any of these four or go back and choose **Timisoara** or **Zerind**. Each of these six nodes is a** leaf node, **that is**, **a node with no children in the tree**.**

The set of all leaf nodes available for expansion at any given point is called thefrontier.

**Tree Search Algorithm**

The process of expanding nodes on the frontier continues until either a solution is found or there are no more states to expand. The general tree search algorithm is shown below:

function TREE-SEARCH(problem) return solution or failure frontier = {initial-state} loop: if is-empty(frontier): return failure else: temp = choose a leaf node and remove it from the frontier if GOAL-NODE(temp): return corresponding solution else: expand temp and add the resulting node to the frontier

All the tree search algorithm share this basic structure. The primary different in tree search algorithms in the way they choose which state to expand next (called **Search Strategy**).

Partial tree search shown in figure 2, includes the path from** Arad **to** Sibiu** and back again to **Arad** again. We say that \(In(Arad)\) is a repeated state in the search tree, generated in this case by a **loopy path**. Considering such loopy paths means that the complete search tree for Romania is infinite because there is no limit to how often one can traverse a loop. Loop can cause certain algorithm to fail, making otherwise solvable problem unsolvable.

Fortunately there is no need to consider loopy paths, because path cost is additive and step cost is non-negative, a loopy path to any given state is never better than the same path with the loop removed.

**Graph Search**

To avoid exploring redundant path, we need to remember where we are. To do this, we augment the TREE-SEARCH algorithm with a data structure called the **explored Set, **which remembers every expanded node**. **Newly generated nodes that match previously generated nodes— one in the explored set or frontier, can be discarded instead of being added to the frontier. This new algorithm is called **GRAPH-SEARCH**.

function GRAPH-SEARCH(problem) return solution or failure frontier = {initial-state} explored-set = {} loop: if isempty(frontier): return failure else: temp = choose a leaf node and remove from frontier if GOAL-NODE(temp): return solution else: add the node to the explored node expand the choosen node, adding the resulting nodes to the frontier only if not in the frontier or explored set.

Clearly search tree constructed by the GRAPH-SEARCH algorithm contains at most one copy of each state, so we think of it as growing a tree directly on the state space graph. The algorithm has another nice property:

The frontier separates the state space graph into the explored region and the unexplored region, so that every path from the initial state to an unexplored state has to pass through the state in the frontier. At every step moves a state from the frontier into the explored region while moving some states from the unexplored region into the frontier, so we see that algorithm is systematically examining the states in the state space, one by one, until it find a solution.

**Infrastructure of Search Algorithms**

Search Algorithm require a data structure to keep track of the search tree that is being constructed. for each node \(n\) of the tree , we have a structure that contains four components:

- \(n.STATE\): The state in the state space to which the node corresponds.
- \(n.PARENT\): The node in the search tree that generated this node.
- \(n.ACTION\): The action that is applied to the parent to generate this node.
- \(n.PATH-COST\): The cost, traditionally denoted by \(g(n)\), of the path from the initial state to the node, as indicated by the parent pointers.

Given the component for a parent node, it is easy to see how to compute the necessary component for a child node. The function CHILD-NODE takes a parent node and action as input and return the resulting child node:

function CHILD-NODE(problem, parent, action) return a node return a node with STATE = problem.RESULT(parent.STATE, action) PARENT = parent ACTION = action PATH-COST = parent.PATH-COST + problem.STEP-COST(parent.STATE, action)

The node data structure is shown below:

Notice how the **PARENT **pointers string the nodes together into a tree structure. These pointers also allow the solution path to be extracted when a goal node is found; we use the **SOLUTION** function to return the sequence of actions obtained by following parent pointers back to the root.

**What is the difference between node and state?**

A node is a bookkeeping data structure used to represent the search tree. A state corresponds to configuration of the world. Thus nodes are on the particular paths, as defined by PARENT pointers, whereas, states or not. Furthermore, two different nodes can contain the same world state if that state is generated via two different search path.

**How to implement the frontier?**

frontier needs to be stored in such a way that the search algorithm can easily choose the next node to expand according to its preferred strategy. The appropriate data structure for this is** queue**. The operation on the queue are as follows:

- \(EMPTY(queue)\): returns true only when there are no element in the queue.
- \(POP(queue)\): remove the first element of the queue and returns it.
- \(INSERT(element, queue)\): insert an element and returns the resulting queue.

Queue are characterized by the order in which they stored the inserted nodes. Three common variants are:

**First-in, First-out or FIFO Queue:**which pops the oldest element of the queue.**Last-in, First-out or LIFO Queue (stack):**which pops the newest element of the queue.**Priority Queue:**which pops the element of the queue with the highest priority according to some ordering function.

**How to implement the explored set?**

The explored set can be implemented with a hash table to allow efficient checking for repeated state. With a good implementation, insertion and lookup can be done in roughly constant time no matter how many states are stored.

This article is contributed by Ram Kripal. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help others. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.