Trending Technology Machine Learning, Artificial Intelligent, Block Chain, IoT, DevOps, Data Science

Recent Post

Search

Thursday, 5 July 2018

Heuristic Search in AI

Heuristic search is a AI search technique that employs heuristic for its moves.

Heuristic is a rule of thumb that probably leads too a solution.

Heuristic play a major in search strategies because of exponential nature of the most problems. Heuristics help to reduce the number of alternatives from an exponential number to a polynomial number.

Heuristic Search :-

In Artificial Intelligence, heuristic search has a general meaning, and a more specialized technical meaning.

In a general sense, the term heuristic is used for any advice that is often effective, but is not guaranteed to work in every case.

Within the heuristic search architecture, however, the term heuristic usually refers to the special case of a heuristic evaluation function.

Heuristic information :-

In order to solve larger problems, domain-specific knowledge must be added to improve search efficiency.

Information about the problem include the nature of states, cost of transforming from one state to another, and characteristics of the goals.

This information can often be expressed in the form of heuristic evaluation function, say f(n,g), a function of the nodes n and / or the goals g.

Heuristic evaluation function :-

Heuristic evaluation function estimates the cost of an optimal path between a pair of states in a single -path-finding problem.

For example, Euclidean or airline distance is an estimate of the highway distance between a pair of locations.

For a fixed goal state, a heuristic evaluation is a function of a node, say h(n), that estimates the distance from node, say n to the given state.

h(n) = estimates cost of the cheapest path from node n to a goal node.

There is a whole family of Best-First Search algorithms with different evaluation functions
  - Each has a heuristic function h(n).

Manhattan Distance :-

Manhattan distance is a common heuristic function for the sliding-tile puzzles.

Manhattan distance is computed by counting the number of moves along the grid that each tile is displaced from its goal position, and summing these values over all faces.
 

No comments:

Post a Comment