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
what algorithms can i use for the above title in my project desing and implmentation of road transport booking system

Decision Tree - ID3 algorithm: Imagine you only ever do one of the following four things for any weekend:   go shopping   watch a movie   play tennis   just

Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

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


Q. Write  down the  algorithm  to  insert  an  element  to  a  max-heap  which  is  represented sequentially.           Ans: The algorithm to insert an element "newkey" to

for(int i = 0; i for (int j = n - 1; j >= i ; j--){ System.out.println(i+ " " + j);

What is complexity of an algorithm? What is the basic relation between the time and space complexities of an algorithm? Justify your answer by giving an example.

i need the full concept of it... please can anyone provide

What are stored and derived attributes?  Stored attributes: The attributes kept in a data base are called stored attributes.  Derived attributes: The attributes that are