How to decide `heuristic cost`

for the `cities connected with roads`

problem. The graph has non negative weighted unidirectional edges and no edge connects any vertex to itself. In this graph, there is only one edge between any two vertices. My aim is to get the shortest distance between `single source`

and `single destination`

.

If you're trying to optimize for distance travelled, euclidean distance is a good baseline heuristic.

If you're given a weighted graph, use the edge weight as if it's the length of the segment. The shortest path in a weighted graph is the path with the lowest combined edge weight.

If your edges lie in a Euclidian plane, your vertices correspond to roads, and the vertex cost is the length of the road, then the Euclidian distance or L2 norm is a good choice for the heuristic cost.

Here's why. But first, some quick terminology:

Let `f(x)`

be the **path cost**, the calculated shortest distance from the start node to node `x`

.

Let `h(x)`

be the **heuristic cost**, an estimate of the distance to the goal from node `x`

.

Because A* is a **directed best-first** search algorithm. At each step it moves to the node which minimizes `h(x) + f(x)`

(and calculating `h(x)`

requires that we have a goal node in mind).

For this approach to be **guaranteed** to find the correct shortest patch distance between the start and end nodes, `h(x)`

must be an admissible heuristic. This essentially means that **it must not overestimate the distance to the goal node**.

Therefore, if your nodes are organized on a Euclidian plane, and your costs correspond to the L2 norm distance between the nodes, then the Euclidian distance or L2 norm between the current node `x`

and the goal node is guaranteed to be an admissible heuristic (it's the shortest possible path between the two nodes, so any actual path along a series of vertices in your graph must be longer).

As a bonus, it's informative to note that Dijkstra's Algorithm is simply a special case of A* with `h(x) = 0`

. For any node, we assume that the path to the goal is `0`

, which means we simply take the smallest possible step. This is certainly an admissible heuristic because the distance between any two nodes cannot be less than `0`

(if we're assuming non-negative edge costs).

Similar Questions

I am representing my graph as a adjacency list. I want to know how can I find a cluster of nodes which are internally connected but no edge points outwards from them. Is there any well known algorithm

I have connected to a DVR system which is serving up a continuous live feed from CCTV camera. I am fairly sure the format is H264 (the first 4 bytes are 4HKH). I would like to know how I can read the

How weigth order affects the computing cost in a backtracking algorithm? The number of nodes and search trees are the same but when it's non-ordered it tooks a more time, so it's doing something. Than

I have 500 US cities in a MySQL table. I have the city name, state, longitude and latitude. I want to visually see these cities plotted on a map of the US. How can I do this? Are they any free tools

I was recently asked if I could find an algorithm to compute the minimum cost spanning tree of a given graph, where the total cost of the spanning tree is given by the product of the edge costs rather

I've to decide the meta keywords for my website. I want to decide them carefully for google search. I have 2 questions about it: how many keywords should I use ? my website is in italian, should I us

I am trying to implement an A* Search algorithm. For now I am just trying to find a good path through an environment littered with walls. The walls are randomly generated, and in some cases my path ge

Hi and sorry for my bad English. I'm studying computer science and I didn't understand why this expression (in the image) has this result. Tmedio is the medium cost of a linear search algorithm, a

I am trying to solve the following puzzle. I am confused by one of the test case. Here is the problem: The country of Byteland contains of N cities and N - 1 bidirectional roads between them such that

I have a binary tree that I need to search through. I'm not searching for one specific node of the tree, but rather over every node of the tree to gain information about them. I have a simple recursiv

So I'd like to know what is the general algorithm to implementing an instant search that is not load intensive. Not specifically on the web but even in a desktop/winforms application. Correct me if I

I have taken a job selling a customized online workplace management application. Our clients' businesses work around the application. Our clients track their time (which is how they get paid), fina

In my program I need to search in a quite big string (~1 mb) for a relatively small substring (< 1 kb). The problem is the string contains simple wildcards in the sense of a?c which means I want

I'm looking to build a custom view of a Google Maps type of application for providing directions, but I need to blacklist specific roads or sections of roads. I'm not talking just avoiding highways or

the standard way is the following: AI: A modern Approach function UNIFORM-COST-SEARCH node <- INITIAL-STATE frontier <- priority queue ordered by PATH-COST, with node as the only element explore

I am looking for an API to return a list of cities, given the current city (may be coordinates) and some specified driving distance. If driving distance is unfeasible, the list of cities within a radi

How should I decide system requirements like: RAM capacity FLASH memory capacity Processor frequency etc I am building an application to control NAND FLASH, LCD driver, UART control, keypad control

I am looking for an algorithm that is implemented in C, C++, Python or Java that calculates the set of winning coalitions for n agents where each agent has a different amount of votes. I would appreci

How do I get my search box connected with the Rotten Tomatoes API so I can do a search in my web page and it returns the results from Rotten Tomatoes? I added the $userSearch variable in the PHP secti

I have a directed graph whose vertices have costs. I would like to find the path with maximum cost between two vertices, but I have only found algorithms to solve the path with minimum cost. Also, I'm

I have two combos; provinces and cities. I would like to change cities value when the province combo value changes. Here is my code <div class=cities form> <?php $v = $ajax->remoteFuncti

I have Two Arrays string[] city = {A,B,C,D} And the cost of connecting them say int[] cost ={ 2,1,3,2,4,3} The task is to find the shortest path cost which will be 6 here. Why? A->B = 2

See the screenshot here: I'd like the user to just type a city or country name and the autocompleter will show suggested items. How should I start for creating it? Are there any API(s) or web service

I'm wondering what guidelines you guys are using for determining the structure for your Namespaces. When do you decide something warrants it's own Namespace? I read in a forum discussion or article th

Is there an algorithm or some heuristic to decide whether digital audio data is clipping?

I have 6 cities in my record. mumbai, blore, Hbad, delhi, chennai, pune. And record specif to each city. When user come on my page, I want to show record based on location relevance. I thought to use

I am writing a prototype of a new app for an enterprise. I want to include a great search engine, which is something they have never had before. What I am looking for is something that can translate a

I want to make my own binary search algorithm to search ArrayList of 1 000 000 elements. I decided to do the search with do-while loop. I am aware I could use while() loop. But when I run it, it takes

How do I get the average cost per visit in a TSQL statement? I have the total count of visits and summed the cost.

My question is as follows: According to different sources, Dijkstra's algorithm is nothing but a variant of Uniform Cost Search. We know that Dijkstra's algorithm finds the shortest path between a sou

I want to make a search for articles on my website - is it ok to use just plain 'LIKE' statement or is there a better search algorithm to use with MySQL? (its important it be efficient)

I need a algorithm that does the following: In an NBA fantasy league, given: each player's average point total a price for each player a salary cap Select the optimal 9-player line-up. To use

I'm using Pythons SocketServer.ThreadingTCPServer. Now I want to know how many clients are connected at a certain moment. How to solve this?

I am reading the book -- Artificial Intelligence a modern approach. I came across this sentence describing the time complexity of uniform cost search Uniform-cost search is guided by path costs rath

I am asking this question to make sure some concept of parallel computing concept. Lets give a simple example: We have a set of n numbers, what's the best running time to search a item from it if we h

For large problems sizes, an algorithm with time cost O(2^n) is faster than an algorithm that has time cost O(N^2) Is this true or false? What I think is that if C^n, C = constant and C > 1, then

A school project has me writing a Date game in C++ (example at http://www.cut-the-knot.org/Curriculum/Games/Date.shtml) where the computer player must implement a Minimax algorithm with alpha-beta pru

Also why does this give me an error because I used bool? I need to use this sequential search algorithm, but I am not really sure how. I need to use it with an array. Can someone point me in the corre

I'm developing a web application. How can I get list of cities, when I begin to write name of city? Like as application Weather on iPhone.

Given an array of items, each of which has a value and cost, what's the best algorithm determine the items required to reach a minimum value at the minimum cost? eg: Item: Value -> Cost -----------

I was wondering if this rope bridge problem could be solved with a graphing algorithm search: My gut feeling says DFS but how should I define the states? (That is if DFS is even the way to go.) Rope

I was asked this question in an interview: Assume an infinite array of integers which is sorted. How would you search for an integer in this array? What would be time complexity? I guessed what the in

So, I have a listbox with x number of items. On top of the listbox I have a TextBox (this is the search field). I try do develop an algorithm that removes items from the listbox, if it doesn't contain

I am looking for a method to decide on the price for a Java EE project that we developed. I know of the COCOMO model but don't know if there are any tools/plugins (preferably on Eclipse) to calculate

Or decide between a parallel and a sequential operation in general. It is hard to know without testing whether parallel or sequential implementation is best due to overhead. Obviously it will take som

How can i use Rete Algorithm in java? Do i need to write my own algorithm implementation? Or is there already implemented library available?

How should I test my algorithm in terms of speed? The enhanced algorithm I made and the original algorithm search the same depth and they both give the same move, they only differ in terms of speed. D

I am trying to decide whether I should use App-engine Search API or Datastore for an App-engine Connected Android Project. The only distinction that the google documentation makes is ... an index sea

Should we use all H1 to H6 in a website? i use h1 to h2 usually. now how to judge and decide where to use H3 to h6. should we use like this h3 {display:inline} <div id=content> <h3> some

I was following a tutorial showing how to create a Binary search algorithm from scratch. However I recieve the error Use of unassigned local variable 'Pivot'. I'm new to the language and have only t