What do you mean by heuristic and heuristic search? What are the advantages and Characteristics of Heuristic Search? – Artificial Intelligence
There are two types of search algorithms in Artificial Intelligence, Uninformed search algorithms and Informed search algorithms.
Uninformed search algorithms or Brute-force algorithms, search through the search space all possible candidates for the solution checking whether each candidate satisfies the problem’s statement.
Informed search algorithms use heuristic functions that are specific to the problem, apply them to guide the search through the search space to try to reduce the amount of time spent in searching.
A good heuristic will make an informed search dramatically outperform any uninformed search: for example, the Traveling Salesman Problem (TSP), where the goal is to find is a good solution instead of finding the best solution. In such problems, the search proceeds using current information about the problem to predict which path is closer to the goal and follow it, although it does not always guarantee finding the best possible solution. Such techniques help in finding a solution within reasonable time and space (memory).
Requirement of Search Algorithms / Techniques
- The first requirement is that it causes motion, in a game playing program, it moves on the board and in the water jug problem, filling water is used to fill jugs. It means the control strategies without the motion will never lead to the solution.
- The second requirement is that it is systematic, that is, it corresponds to the need for global motion as well as for local motion. This is a clear condition that neither would it be rational to fill a jug and empty it repeatedly, nor it would be worthwhile to move a piece round and round on the board in a cyclic way in a game.
Informed / Heuristic Search Algorithms / Techniques
Many Informed search Algorithms techniques are developed, using heuristic functions.
The algorithms that use heuristic functions are called heuristic algorithms.
Heuristic algorithms are not really intelligent; they appear to be intelligent because they achieve better performance.
Heuristic algorithms are more efficient because they take advantage of feedback from the data to direct the search path.
Example: Finding a route from one city to another city is an example of a search problem in which different search orders and the use of heuristic knowledge are easily understood.
State: The current city in which the traveler is located.
Operators: Roads linking the current city to other cities.
Cost Metric: The cost of taking a given road between cities.
Heuristic information: The search could be guided by the direction of the goal city from the current city, or we could use airline distance as an estimate of the distance to the goal.
For complex problems, the traditional algorithms, presented above, are unable to find the solution within some practical time and space limits. Consequently, many special techniques are developed, using heuristic functions.
- Blind search is not always possible, because it requires too much time or space (memory).
- Heuristics are rules of thumb; they do not guarantee a solution to a problem.
- Heuristic Search is a weak technique but can be effective if applied correctly; it requires domain-specific information.
Characteristics of heuristic search
Heuristics are knowledge about the domain, which help search and reasoning in its domain.
Heuristic search incorporates domain knowledge to improve efficiency over blind search.
A heuristic is a function that, when applied to a state, returns the value as estimated merit of state, with respect to the goal.
- Heuristics might (for reasons) underestimate or overestimate the merit of a state with respect to the goal.
- Heuristics that underestimate are desirable and called admissibly.
The heuristic evaluation function estimates the likelihood of a given state leading to the goal state.
Heuristic search function estimates cost from current state to goal, presuming function is efficient.
Heuristic search compared with other search
The Heuristic search is compared with Brute force or Blind search techniques below:
| Brute force / Blind search | Heuristic search |
| Can only search what it has knowledge about already | Estimates ‘distance’ to goal state through explored nodes |
| No knowledge about how far a node from the goal state | Guides search process toward the goal |
| Prefers states (nodes) that lead close to and not away from goal State |
Example: Travelling salesman
A salesman has to visit a list of cities and he must visit each city only once. There are different routes between the cities. The problem is to find the shortest route between the cities so that the salesman visits all the cities at once.
Suppose there are N cities, then a solution would be to take N! possible combinations to find the shortest distance to decide the required route. This is not efficient as with N=10 there are 36,28,800 possible routes. This is an example of a combinatorial explosion.
There are better methods for the solution of such problems: one is called branch and bound. First, generate all the complete paths and find the distance of the first complete path. If the next path is shorter, then save it and proceed this way avoiding the path when its length exceeds the saved shortest path length, although it is better than the previous method.
Summary
This article discusses Heuristic Search – Characteristics Advantages – Artificial Intelligence. If you like the material share it with your friends. Like the Facebook page for regular updates and YouTube channel for video tutorials.