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
Instructions Design and test a reference array. Reference array stores the references to user supplied objects of different types. Just think it as a heterogeneous array wh

Q. Explain the basic concept of the primitive data structures.                                             Ans. The concept of P r i m i t i ve Data

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

Q. Establish the usage of linked lists for polynomial manipulation.                                       Ans. Usag e of Linked List for Polynomial Manipulation. Link

what happen''s in my computer when i input any passage

The information in the table below is available for a large fund-raising project. a. Determine the critical path and the expected completion time of the project. b. Plot the total

One of the main problems with the linear queue is the lack of appropriate utilization of space. Assume that the queue can store 100 elements & the complete queue is full. Thus, it

write aprogram for random -search to implement if a[i]=x;then terminate other wise continue the search by picking new randon inex into a

Almost Complete Binary Tree :-A binary tree of depth d is an almost whole binary tree if: 1.Any node and at level less than d-1 has two children. 2. for any node and in the tree wi

Write an algorithm for binary search. What are its limitations? .