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
How branching takes place in Instruction pipeline. Explain with suitable examples

1. Write a pseudocode algorithm to print the numbers from 1 to 10, and then from 10 to 1, using exactly one loop. 2. The function contains() takes a food as an argument and tell

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

In this example, suppose the statements are simple unless illustrious otherwise. if-then-else statements if (cond) { sequence of statements 1 } else { sequence of st

WRITE AN ALGORITHM TO CONVERT PARENTHIZED INFIX TO POSTFIX FORM ALSO TRACE ALG ON ((A+B)*C-(D-E)$F+G)

Maximum numbers of nodes a binary tree of depth d The maximum numbers of nodes a binary tree of depth d can have is 2 d+1 -1.

Explain the Assertions in Ruby Ruby offers no support for assertions whatever. Moreover, because it's weakly typed, Ruby doesn't even enforce rudimentary type checking on opera

write an algorithm to find the average number of occurances of MECHANIL in an english passage

Ans: I nsertion into the B-tree: 1.  First search is made for the place where the new record must be positioned. As soon as the keys are inserted, they are sorted into th

Speed cameras read the time a vehicle passes a point (A) on road and then reads time it passes a second point (B) on the same road (points A and B are 100 metres apart). Speed of t