Tell me more ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.
up vote 8 down vote favorite
1

I have a problem with the shooting star algorithm. It's my final project and I need some help.

My question is how can I calculate the heuristic shooting star algorithm? I can use the pgrouting shooting star, but I don't understand how to calculate heuristic shooting star.

I have searched the calculating heuristic shooting star in internet book but I can't find it now.

Can you tell me about shooting star algorithm, not just source code , Mr Mario?

share|improve this question

2 Answers

up vote 2 down vote

If I understand you correctly, and I am not an expert, but maybe you can find something in the source code of pgrouting shooting star heuristic function and modify it too your needs. Of course, your would have to build pgrouting again.

share|improve this answer
Thanks Mr.Mario Miler,your source code is same with pgrouting or library in Postgresql, Postgis.Right? – donni Jan 18 at 13:23
This is source code from pgrouting repository. You will have download the whole repository, change heuristic function of your choice and build it. You can find some instructions here pgrouting.org/docs/1.x/install_ubuntu.html .. little, old but should work. I haven't build pgrouting for some time now so cant tell you if there are any problems. – Mario Miler Jan 18 at 18:34
Can you tell me about shooting star algorithm, Mr Mario? – donni Jan 19 at 11:37
Can you tell me about shooting star algorithm, not just source code , Mr Mario? – donni Jan 19 at 11:39
Shooting start is just a fancy name for what is essentially still A*. It just routes between links instead of nodes. See this discussion: download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/… – Uffe Kousgaard Jan 19 at 12:00
show 6 more comments
up vote 0 down vote

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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.