Heuristic Search.

HEURISTIC SEARCH

               Solve complex problems efficiently ,it is necessary to compromise the requirements of the movability and systematically. A control structure has to be constructed that no longer guarantees the best solution, but that will almost always find a very good answer. Such a technique is said to be heuristic (rule of thumb). A heuristic search improves the efficiently of the search process, but sacrifices the claims of completeness. But they improve the quality of the paths that are explored. Using good heuristics we can get good solutions to hard problems, such as the traveling salesman problem.

Applying it to the traveling salesman problem produces the following procedure.

1. Arbitrarily select a starting city.

2. To select the next city, look at all cities not yet visited. Select the one closet to the current city.

     Go to it next.

3. Repeat step 2 until all the cities have been visited.

This procedure executes in time proportional to N * N , instead of N! and it is possible to prove an upper bound on the error it incurs. In many AI problems , however, it is not possible to produce such bounds. This is true for two reasons.

For real world problems, it is often hard to measure precisely the goodness of a particular solution. For instance , answers to questions like “Why has inflation increased?” can not be precise.

ii) For real world problems it is often useful to introduce heuristics based on relatively unstructured knowledge. This is because often a mathematical analysis is not possible. Without heuristics, it is not possible to tackle combinatorial explosion. Moreover, we go for optimum solution that satisfy some set of requirements. We stop with satisfactory solutions even though there might be better solutions.

Ex.A good example of this is the search for a taking space. Most people will stop as soon as there find a fairly good space, even if there must be a slightly better space or ahead.