The Heuristics

·         Searching is an important aspect of AI, as so many problems are viewed as searching problems.

·         In one line searching is nothing but reaching the goal state from initial state using some algorithms.

·         Actually goal state is always associated with a function which returns true if the state, passed as argument, is a goal state. Please note that we don’t used “the goal state”, and its need not be as it is not unique. Because there are problems where we have more than one goal states.

·         A search algorithm is complete if it finds one of the goal states of for the given problem.

·         A search algorithm is optimal if it finds the goal state (or path to goal state) with less cost. Cost is some mathematical scale to find the pay to move from one state to another. Cost is uniform or it need not be uniform for some problems.

·         The algorithms are generally classified into 2 types – blindfold (uninformed) search algorithms and heuristic (informed) search algorithms. The first category of problems are generic algorithms which can be applied to any of problems, but computationally very bad as they don’t have any idea about the problem for which they are applied but the latter ones are embedded with the knowledge about the problem to significantly speed up the searching process.

·         The best examples of blindfold search algorithms are DFS (Depth first search), BFS (Breadth first search) and UCS (Uniform-cost search).

·         The blindfold search algorithms are provided with nothing except node, edges and costs of the state space tree of the problem.

·         DFS is complete but it is not an optimal search algorithm but BFS is complete under some assumptions and it is optimal, Of course.

·         All above mentioned algorithms are blind, i.e., they don’t have any idea about the correct direction to solution(s) of the given problem. They blindly stumble around the current state until it reaches the goal state.  

·         One way of providing this missed information is by the concept of Heuristic function.

·         Before proceeding let’s see one simple problem of finding the largest number among an integer array, say 14, 25, 39, 54, 66, 19. Of course answer is 66, but here we got some simple and important questions! What makes us to say 66 is the largest number in this array? What is special with 66 to say it is greater than all other numbers? In other words what is the scale that we used to find out 66? The answers for these questions are trivial, Of course, but we need understand them correctly. Here we used the face value of each number as the scale.

·         Even this is simple we need to see from the machine point of view. Machine needs some tool or scale or at least a measurement to take decision. In other words we need a mathematical model, Of course. The mathematical model can be well organized model or its just simple function. Informally the well organized model means, a mathematical model with heavy knowledge base, highly skilled algorithms etc… A simple function is mapping of current state of the problem to some mathematical quantity which says, how much far or near to the goal of the problem.

·         Heuristics is a mathematical model, which may or may not use the well organized model, of latter kind to estimate the cost from any state to goal state.

·         In more formal (literally) way, heuristic is a function h: S -> R⁺, which maps each member of set S to a positive real number (which is nothing but cost). h is not one-to-one because, cost for two state can be same and it is an on-to function, Of course. At the beginning of this definition we mentioned as literally formal because, in this definition we didn’t specify that the destination should be a goal state. Whatever heuristic acts as tool that what machine needs, for searching problems.

·         After this, next question comes to our mind is what should be a heuristic function? In other words how to implement this heuristic function? Below are some characteristics of heuristic functions.

·         The function should maps to a positive real number or to some measurable mean.

·         The input should include the one of the state from the set S of problem.

·         The heuristic can be an abstraction of domain knowledge of the solving problem.

·         It should be transparent to the external world.

·         In some cases we can just estimate the cost so it can also called as estimator for machine to reach the one of the goal state of the problem.

ontd...

c