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 quick sort algorithm

A full binary tree with 2n+1 nodes have n non-leaf nodes

If a Dequeue is implemented via arrays, then this will suffer with the similar problems which a linear queue had suffered. Program 8 gives the array implementation of Dequeue.

Document processing is quickly becoming one of the dominant functions of computers. Computers are utilized to edit, search & transport documents over the Internet, and to display d

It is a naturally occurring sorting method exemplified through a card player arranging the cards dealt to him. He picks up the cards like they are dealt & added them into the neede


REPRESENTATION OF ARRAYS This is not uncommon to determine a large number of programs which procedure the elements of an array in sequence. However, does it mean that the eleme

Asymptotic notation Let us describe a few functions in terms of above asymptotic notation. Example: f(n) = 3n 3 + 2n 2 + 4n + 3 = 3n 3 + 2n 2 + O (n), as 4n + 3 is of

Explain the theory of computational complexity A  problem's  intractability  remains  the  similar  for  all  principal  models  of   computations    and   all reasonable inpu

What is binary search?   Binary search is most useful when list is sorted. In binary search, element present in middle of the list is determined. If key (the number to search)