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
This is a unit of which targeted on the emerging data structures. Red- Black trees, Splay trees, AA-trees & Treaps are introduced. The learner must explore the possibilities of app

Sequential files are most frequently utilized in commercial batch oriented data processing where there is the concept of a master file on which details are inserted periodically. F

A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is called as a   Queue.

Question 1 Discuss the following theorems with respect to Splay Trees- Balance Theorem Dynamic Finger Theorem   Question 2 Write a C program for implementation

Q. Explain the result of inserting the keys given. F, S, Q, K, C, L, H, T, V, W, M, R, N, P, A, B, X, Y, D, Z, E  in an order to an empty B-tree of degree-3.

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

how to design a cache simulator with 4-way set associative cache


Q. Explain the basic concept of the primitive data structures.                                             Ans. The concept of P r i m i t i ve Data

State about the Bit String Carrier set of the Bit String ADT is the set of all finite sequences of bits, including empty strings of bits, which we denote λ. This set is {λ, 0