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
Explain an efficient way of storing a sparse matrix in memory.   A matrix in which number of zero entries are much higher than the number of non zero entries is called sparse mat

draw a flowchart which prints all the even numbers between 1-50

I was wanting to know where this web site was created. My second question is,,, are the online tuters accredited teachers? If they are, are they only working for the website or ma

This is the most extensively used internal sorting algorithm. In its fundamental form, it was invented by C.A.R. Hoare in the year of 1960. Its popularity lies in the easiness of i

Program: Creation of a linked list In the next example, wewill look to the process of addition of new nodes to the list with the function create_list(). #include #includ

Book to refer: Introduction to Algorithms, 3rd Ed, by Clifford Stein, Thomas H. Cormen, Ronald Rivest, Charles E. Leiserson Question: Tic Tac Toe game -Design a GUI and implement

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

Five popular hashing functions are as follows: 1) Division Method 2) Midsquare Method 3) Folding Method 4) Multiplicative method 5) Digit Analysis

Relation between the time and space complexities of an algorithm The examining of algorithm focuses on time complexity and space complexity. As compared to time analysis, the a

how to define the size of array