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
After going through this unit, you will be able to: • define and declare Lists; • understand the terminology of Singly linked lists; • understand the terminology of Doubly

Which data structure is used for implementing recursion Stack.

Binary search technique:-  This technique is applied to an ordered list where elements are arranged either in ascending order or descending order. The array is separated into t

Tree is dynamic data structures. Trees can expand & contract as the program executes and are implemented via pointers. A tree deallocates memory whereas an element is deleted.

Search engines employ software robots to survey the Web & build their databases. Web documents retrieved & indexed through keywords. While you enter a query at search engine websit

Q. Construct a complete binary tree with depth 3 for this tree which is maintained in the memory using the linked representation. Make the adjacency list and adjacency matrix for t

Sorting is significant application activity. Several sorting algorithms are obtainable. But, each is efficient for a specific situation or a specific kind of data. The choice of a

If a node in a BST has two children, then its inorder predecessor has No right child

Determination of Time Complexity The RAM Model The random access model (RAM) of computation was devised through John von Neumann to study algorithms. In computer science,

Program gives the program segment by using arrays for the insertion of an element to a queue into the multiqueue. Program: Program segment for the insertion of any element to t