Its not, that i’ve found an ancients treasure of navigatory wisdom of have the total clue about how to find the shortest possible way to my next target, but I have made up my mind about that.
Imagine a network of N nodes… with N greater than 2 with hardwired connections… every node is reachable… not every node is connected with every neighbour… let this be our near realistic scene of a Country with cities and roads (at the moment, all with the same quality, but different length).
Imagine you are in town A, willing to get to town B. Its your interest to get there as soon and as relaxed as possible. Because you are a lazy guy, you bought a TimTim-System (imagine that as a fictive company with proprietary map data, selling navigation systems) some while ago. You type in “City A” and then “City B”. The route you travel gets you there quick… or short… but even relaxed? The data of nearly all navigation system providers derives from sattelite positioning data and digital maps, defines crossings of a type, defines roads with a quality and length and calculates an approximation of the way, it wants you to take. That may be wht most people are looking for, but its not the best way.
My idea starts in a very simple way… Imagine every City as a root for a tree… every City you can directly (with maximum a step) go to is supplied as a data source and can be treated as a small Tree. If you want to go from city A to city B, the algo takes the small tree for city A, which … micht have city C and D as a neigbour… and attaches the subtrees of city C and D to it. City C has City A, D and E as a neighbour, city D has city A, C, and F as a neigbour. So all the subtrees are attached with only 2 rules:
- A subtree may be attached many times in one layer of the pathtree
- A subtree may be attached only in ONE layer. If it has to be attached in a second layer, too, the path ends at this point. (This imlies that the root tree is not attached any more, too.)
The extension of the tree ends, when there are no more leafes, that can be extended. “Thats very lazy!” you might scream now, because that only finds some possibilities from A to B, but thats all we want, hou? So lets pick one of the paths from A to B now. All Paths in the tree, that end with the leaf B can be considered as possible ways to B. I said before, that we have information about how long the ways are (this information may be replaced with an algo, that weights them in a different way). We just add the weights for every path and pick the one with the lowest weight… and voilla! Here we have our precious path!
This method has some flaws:
- a long route to a target is preferred, if it has lesser nodes in it.
- if there the target is unreachable, the tree might get very huge.
- The weighing doens’t change the route completly, but only has influence on a choice of a very small number of combinations.
but also some rather impressive advantages:
- The memory usage is kept in acceptable states, because the tree is only expanded in a senseful manner (if there are no nodes with an unusual high ammound of neighbours)
- The algo’s weight behavour is very flexible, because nearly every meta information can be combined (to a comparable value) to be a weight.
- There is no need to know about koordinates and streets
- Because this algo not aims to choose the shortest way, it is not affected by the “traveling salesman problem”.
The new idea is the weighting system, I imagine. It consists of a “matrix of interests”, that produces some value, that ist used as weight. Possible Meta Information may be “Occurance of traffic jams” “Speed limits” “Beauty of the landscape” “Occurance of police controls” “Relaxedness of traveling”… and many other things that might be ignored my major commercial Companies.
This is because I thought, that if we already have the community giving the data, it might also be able to classify it and tell us ubout their experiences with it. First, to prevet others from running into the same trouble, second to share the beauty of a nice trip.
Connnected to this, i want to create a system named “Happy Sightsharing”, which should be a open portal for exchange of GPS Coordinates of beatiful scenes and/or points of major interest. Thits system might generate gpsdrive waypoints (or export the whole favorites as waypoint snippet) or even other waypoint formats. This is the most realistic option of them all, so it might be implemented first. I am not sure, if I will be able to impemennt all these nice things, but I hope, some nice people (perhaps YOU!?) might help me.
I aim to implement that algo as a web application to collect meta data, position data for nodes, ways and many other things. You can take this moment as the moment, a new “initiative” is formed, named: “Free shortest of the simplest” or short “Fresh ofS”. I want this to become a research project.
If you want to, feel free to yoin my projects in some way. I’d like to share my ideas with someone.
So far… with my strange ideas… let this all become a freaky spot for exchanging the beauty of traveling!
The Starseeker