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
Ask question #Minima binary search tree is used to locate the number 43 which of the following probe sequences are possible and which are not? explainum 100 words accepted#

Define Dynamic Programming  Dynamic  programming  is  a  method  for  solving  problems  with  overlapping  problems.  Typically, these sub problems arise from a recurrence rel

What do you mean by complexity of an algorithm? The complexity of an algorithm M is the function f(n) which gives the running time and/or storage space need of the algorithm i

Q. Describe the adjacency matrix and make the same for the given undirected graph.    Ans: The representation of Adjacency Matrix: This representation consists of

Complexity classes All decision problems fall in sets of comparable complexity, called as complexity classes. The complexity class P is the set of decision problems which ca

The fundamental element of linked list is a "record" structure of at least two fields. The object which holds the data & refers to the next element into the list is called a node .

A full binary tree with n leaves have:- 2n -1 nodes.

Explain about Franklin Algorithm We mentioned how the number of possible comparisons of polygons grows as the square of the number of polygons in the scene. Many of the hidden-

how we can convert a graph into tree

Q. Explain the technique to calculate the address of an element in an array. A  25 × 4  matrix array DATA is stored in memory in 'row-major order'. If base  address is 200 and