Consistent heuristic function - graph search, Data Structure & Algorithms

Consistent Heuristic Function - Graph Search

Recall the notions of consistency and admissibility for an A* search heuristic.

a. Consider a graph with four nodes S, A, B, C, and G, and with four edges SA, SB, BA, AC, and CG. Write down positive edge lengths and values of an admissible heuristic function h such that using A* with Graph-Search (as given in the lectures) to find a route from S to G gives a suboptimal solution. In other words, construct an admissible heuristic that is not consistent.

b. Prove that any consistent heuristic function that is also admissible.

[Hint: use induction on the number of nodes in the shortest path between a node and a goal.]

Posted Date: 3/19/2013 3:06:12 AM | Location : United States







Related Discussions:- Consistent heuristic function - graph search, Assignment Help, Ask Question on Consistent heuristic function - graph search, Get Answer, Expert's Help, Consistent heuristic function - graph search Discussions

Write discussion on Consistent heuristic function - graph search
Your posts are moderated
Related Questions
State the Introduction to pseudocode No specific programming language is referred to; development of algorithms by using pseudocode uses generic descriptions of branching, loop

Draw a flowchart of a Booth''s multiplication algorithm and explain it.

Which sorting methods would be most suitable for sorting a list which is almost sorted  Bubble Sorting method.

Advantages of dry running a flowchart When dry running a flowchart it's advisable to draw up a trace table illustrating how variables change their values at every stage in the

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

Board coloring , C/C++ Programming

Write the non-recursive algorithm to traverse a tree in preorder.    The Non- Recursive algorithm for preorder traversal is as follows: Initially  push NULL onto stack and

What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

A town contains a total of 5000 houses. Every house owner has to pay tax based on value of the house. Houses over $200 000 pay 2% of their value in tax, houses over $100 000 pay 1.

With the help of a program and a numerical example explain the Depth First Traversal of a tree.