This blog is a simple summary about heuristic function for the lectrure CS118.
1. Definition of Heuristic function
According to the Wikipedia, a heuristic method in computer science, especially in artificial intelligence, is a function used to boost the speed of solving a problem or finding an approximate solution when classic methods fails to find any exact solution. “This is achieved by trading optimality, completeness, accuracy, or precision for speed. In a way, it can be considered a shortcut.”
Thus, a heuristic function is a method of ranking the alternatives in search algorithm with weights or costs at each branching step. This function is built based on available information for every state in the search problem and can be used to decide which branch to stick on. To be concrete, heuristics are just functions that take search states and return numbers that estimate the cost to a nearest goal. More effective heuristics will return values closer to the actual goal costs. To be admissible, the heuristic values must be lower bounds on the actual shortest path cost to the nearest goal (and non-negative). To be consistent, it must additionally hold that if an action has cost c, then taking that action can only cause a drop in heuristic of at most c.
The heuristic function cost is F(n) = h(n) + g(n).
2. Heuristic funtion in A* searching algorithm
A heuristic h(n) can be used to control the actual searching path of A* algorithm. Actually, the heuristic function is not doing the optimization job, but force the A* algorithm to spend less time on exploring new node in the graph when finding the optimal path. It is more like a restriction. When we do searching without heuristic function, or provided with a trivial heuristic which return zero everywhere, the A* algorithm will degenerate into Uninformed Cost Search (UCS) like Dijkstra’s algorithm.
Properties:
- When h(n) is always 0, then it will return g(n). A* degenerates to Dijkstra’s algorithm but can still promise on finding the shortest path.
- If the value of h(n) is always lower than the actual cost to the goal, A* can find a shortest path. The lower h(n) is, the more nodes A* needs to explore.
- When h(n) is equal to the actual cost of moving to the goal point, A* algorithm will find out the shortest path without exploring any extra node. The A* will become perfect.
- When h(n) is higher than the actual cost to goal, A* cannot promise on finding optimal solution but can run fast.
- When h(n) is far greater than the actual cost, A* algorithm will become the Greedy Best First Seach.
Trade off
According to Wikipedia:
- Optimality: When several solutions exist for a given problem, does the heuristic guarantee that the best solution will be found? Is it actually necessary to find the best solution?
- Completeness: When several solutions exist for a given problem, can the heuristic find them all? Do we actually need all solutions? Many heuristics are only meant to find one solution.
- Accuracy and precision: Can the heuristic provide a confidence interval for the purported solution? Is the error bar on the solution unreasonably large?
- Execution time: Is this the best known heuristic for solving this type of problem? Some heuristics converge faster than others. Some heuristics are only marginally quicker than classic methods.
When h(n) is suitable, we can find out the shortest path very fast. When h(n) is relatively lower, we can still get the shortest path but the algorithm will be slow. When it is too high, we give up on the shortest path but can get a faster speed.
Reference:
2.http://blog.jobbole.com/84694/