I get this one from mailing list.
Shooting* is edge-based, so it goes from edge to edge while A* and
Dijkstra go vrom vertex to vertex. Thus you need a data structure
which keeps all adjacent edges for every edge of your graph. It can be
also done by making a line graph
(http://en.wikipedia.org/wiki/Line_graph) out your original road
network. And then you can assign an edge-to-edge passage cost (as a
special attribute of your adjacent edges structure or as a cost of the
line graph) which actually represents any kind of limitations or
penalties for going from one edge to another - such as turn
restrictions in a case of turns or any other kind of restrictions like
traffic lights. Having this you can use A* or any other shortest path
algorithm using edges as vertices.
So, that's an idea behind the Shooting*.
And I get this one agaian from Anton Patrushev:
http://download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/discussion/topic/276.html. You write like this: In A* we are using something similar to Manhattan function (|Dx|+|Dy|)/2 http://pgrouting.postlbs.org/browser/trunk/core/src/astar_boost_wrapper.cpp#L75
There you'll see other attempts commented out.
We tried different function is OK. Probably, it was historical reason. heuristic function and for some reason (I don't remember now) decided that for a common road network this
In Shooting* we are using Euclidian distance. http://pgrouting.postlbs.org/browser/trunk/core/src/shooting_star_boost_wrapper.cpp#L100 .
The other formula:
- Euclidean distance > Sqrt(Dx²+Dy²+Dz²) ;
- Manhattan distance > |Dx|+|Dy|+|Dz| ;
- Maximum distance > Max(|Dx|, |Dy|, |Dz|).
I still don’t understand about all.Friend, Can you tell me briefly and detail of The process algorithm shooting star?