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
write an algorithm given each students name and grade points for six courses.find his grade point average and group students into the gpa groups 3.5

An interesting application or implementation of trees is the playing of games such as tie-tac-toe, chess, nim, kalam, chess, go etc. We can depict the sequence of possible moves

What is Assertions Introduction At every point in a program, there are generally constraints on the computational state that should hold for program to be correct. For ins

1) What will call a graph that have no cycle? 2) Adjacency matrix of an undirected graph is------------- on main diagonal. 3) Represent the following graphs by adjacency matr

Determine the effect of Ruby in implementation of string Ruby has a String class whose instances are mutable sequences of Unicode characters. Symbol class instances are charact

Write an algorithm to count number of nodes in the circular linked list.                            Ans. Counting No of Nodes in Circular List Let list be a circular h

What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

The Ruby Programming Language Although data structures and algorithms we study aren't tied to any program or programming language, we need to write particular programs in speci

What is Solid modeling Solid modeling is the most powerful of the 3-D modeling technique. It provides the user with complete information about the model. Defining an object wit

explanation of doubly linklist