In the previous article on Artificial Intelligence which appeared on diGIT’s April 2010 issue, we discussed about search strategies for problem solving. There we talked about the main two strategies in search called ‘uninformed search’ and ‘informed search’ and discussed in detail only about ‘uninformed search’. Today we are going to discuss about what is meant by ‘informed search’. As the name implies, it uses problem-specific knowledge in which is beyond the actual problem itself in finding the best solution that problem in hand unlike the previously discussed ‘uninformed search’ where no additional knowledge about the problem has been provided. Informed search leads to finding better problem-specific solutions in an efficient manner when compared to the other search strategy mentioned before. Informed Search is also known as ‘Heuristic search’ which shows that this type of search strategy uses heuristics (cues) about the problem domain to come up with the most suitable solution.
This is a general graph search algorithm. At each node of the graph it should evaluate which node to be expanded next in order to arrive at the optimal solution efficiently. This is achieved by the introduction of an ‘evaluation function’ which evaluates at each point, which node to be expanded next based on the lowest evaluation function result. Usually, the evaluation function mentioned above measures the distance from the node in concern to the goal, so a lower evaluation function is preferred over a higher evaluation function. Another key factor in this search algorithm is called the ‘heuristic function’ which is a part of the evaluation function, which is defined as the ‘cheapest cost of the cheapest path from a node to a goal node’. Therefore, this algorithm chooses the lowest cost paths from the selected best nodes of the graph to arrive at the goal node, leading to the best solution and the heuristic function value would be zero at the goal node, which acts as a stopping condition for the algorithm to terminate when it reaches the goal.
Based on how the ‘evaluation function’ and ‘heuristic function’ is linked together, there can be different variations of the above mentioned ‘Best-First Search’ strategy, which are explained in detail as follows.
This search method expands the node that is closest to the goal node which is likely to lead to a solution in a quick manner. In this case, the ‘heuristic function’ (h(n)) and the ‘evaluation function’ (f(n)) are the same. One can come up with different ‘heuristic functions’ based on the problem domain in concern and apply it.
Here:- f(n) = h(n)
Let’s first consider a small example which consists of distances between cities and where a tourist wants to find the path that he should travel in order to minimize the distance he travels from city ‘A’ to city ‘N’.
The following table shows the distances in kilometers (approximate road distance) from the destination city ‘N’ to each respective city.
|From City||Road distance (km)||From City||Road distance (km)|
Let’s also assume that the existing roads connecting the above cities are as follows.
Now let’s try to see how to perform greedy best-first search to go from city A to city N. So starting from city A, one can go to either city B, H or D according to the above road map.
Since the heuristic is based on expanding the node with the lowest distance, in the above first step, the algorithm would select to go to city H from cist A since it has the lowest road distance. Then it would see which city to move from H.
Since the lowest distance is to city K, it would move to that city next as shown above. Based on the heuristic function of expanding the nodes based on the lowest distance to goal node, this algorithm would move on until it reaches the destination city ‘N’ as shown below.
This is another best-first search strategy which has a different relationship with the evaluation function and the heuristic function when compared to afore explained ‘greedy best-first search’. Here the evaluation function (f(n)) is defined as the combination of cost to reach the node (g(n)) and the cost to each node from the goal node (h(n)).
Here:- f(n) = g(n) + h(n)
Therefore, this search strategy not only uses the heuristic function which consists of distances to each node from the goal node (h(n)) but also uses the path cost (so far travelled cost) from start node to the node in concern (g(n)) in the evaluation. This appears to be a better heuristic which uses the cue that the distance travelled should be minimized along each possible path.
In this article, we briefly discussed about some informed (heuristic based) search strategies applicable to problem solving. Hope you all got a general idea as to how this strategy is different from the uninformed search strategies described in a previous article and also got a sense of how different heuristic based search strategies work. We would continue to talk about some more heuristic based search strategies and how to come up with heuristic functions to evaluate those in the next article.