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 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

In the array implementation of lists, elements are stored into continuous locations. In order to add an element into the list at the end, we can insert it without any problem. But,

Illustrate the Visual realism applications a)   Robot Simulations : Visualization of movement of their links and joints  and end effector movement etc. b)  CNC programs ver

AVL trees are applied into the given situations: There are few insertion & deletion operations Short search time is required Input data is sorted or nearly sorted

Define Strictly Binary Tree Strictly Binary Tree: - If each non leaf node in binary tree has non empty left and right sub-trees , then the tree is known as a strictly binary t

A town contains a total of 5000 houses. Every house owner has to pay tax based on value of the house. Houses over $200 000 pay 2% of their value in tax, houses over $100 000 pay 1.

insertion and deletion in a tree

Typical programming languages such as Pascal, C or Java give primitive data kinds such as integers, boolean, reals values and strings. They give these to be organised into arrays,

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

Program will demonstrate the insertion of an element at desired position /* Inserting an element into contiguous list (Linear Array) at particular position */ /* contiguous_