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
Define Binary Tree  A binary tree T is explained as a finite set of nodes that is either empty or having of root and two disjoint binary trees TL, and TR known as, respectively

A stack is a last in, first out (LIFO) abstract data type and sequential data structure. A stack may have any abstract data type as a component, but is characterized by two fundame

In this unit, we learned the data structure arrays from the application point of view and representation point of view. Two applications that are representation of a sparse matrix

The class Element represents a single node that can be part of multiple elements on a hotplate and runs in its own thread. The constructor accepts the initial temperature and a hea

Problem 1. Explain about the doubly linked list with neat diagram. Diagram Explaining doubly linked list 2. Explain what are the criteria to be used in evaluatin

(1)  (i) Add the special form let to the metacircular interpreter Hint: remember let is just syntactic sugar for a lambda expression and so a rewrite to the lambda form is all t

Importance of Object-Oriented over java Java is basically based on OOP notions of classes and objects. Java uses a formal OOP type system that should be obeyed at compile-t

how to write prims algorithms? with example

In-order Traversal  This process when executed iteratively also needs a stack and a Boolean to prevent the implementation from traversing any portion of a tree twice. The gener

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