TransWikia.com

Heuristics in A* algorithm

Data Science Asked on February 13, 2021

I am trying to implement the A* algorithm into a graph I have, but I’m not sure if I am doing it properly.

So basically I have some nodes and some edges. In my case the edges are a cost, e.g. dollars defined by the edge type and the actual distance of the edge. So depending on the edge type and the distance of the edge between two nodes, a weight of an edge might look something like this:

node1 to node2 -> 100km * 10$_per_km + edge_insertion_cost -> 1500$

So the price pr. km might vary, as well as the insertion cost of using a particular edge. So far so good.

My "problem" is which heuristics is the best in this case ? I mean, if I just use Euclidian distance I will just get some distance in km, which has nothing to do with cost, node insertion and so on. And since it’s a Euclidian distance, I can’t put a price pr. km on – unless I should just use some kind of average of all different km prices.

So yeah, basically, what would be the best option here ? In some way I feel that it should at least be the same unit as the edge weight.

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP