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 is tha flow chart of algorithm

Normally a potential y satisfies y r = 0 and 0 ³ y w - c vw -y v . Given an integer K³0, define a K-potential to be an array y that satisfies yr = 0 and K ³ y w - c vw -y v

Complexity : How do the resource needs of a program or algorithm scale (the growth of resource requirements as a function of input). In other words, what happens with the performan

Enumerate about the carrier set members Ruby is written in C, so carrier set members (which is, individual symbols) are implemented as fixed-size arrays of characters (which is

i:=1 while(i { x:=x+1; i:=i+1; }


System defined data types:- These are data types that have been defined by the compiler of any program. The C language contains 4 basic data types:- Int, float,  char and doubl

Implementations of Kruskal's algorithm for Minimum Spanning Tree. You are implementing Kruskal's algorithm here. Please implement the array-based Union-Find data structure.

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

This notation gives an upper bound for a function to within a constant factor. Given Figure illustrates the plot of f(n) = O(g(n)) depend on big O notation. We write f(n) = O(g(n))