Implementing an A* for giving only relevant nodes to the haskell part

[fkarg]

The general idea was to unload the haskell part in case of bigger datasets, so the python part would make a A* search over the whole dataset and return all the nodes of the n best ways (the best way and all ways with a distance tolerance of at least 10% to 50% ). this should make it a lot faster, but for the sake of speed we might not actully find the possibly shortest (time) and most probable way that way, but it's pretty unlikely

[sternenseemann]

I think this would lead to incorrect behaviour. Also this optimization is splitting the algorithm into two parts. Optimizations should be only done in the Haskell code!

[fkarg]

okay then do it this way, but then it's only really possible with the database included, since otherwise we might have to parse huge JSON files at some point ...

[sternenseemann]

We'll deal with it at that point.

[froozen]

I talked to @shak-mar today, and he had the great idea of implementing the algorithm as a pathfinding algorithm in a three-dimensional space, the third dimension being the changing probabilities.

I'll probably look into that after some sleep and maybe rewrite the algorithm to check how the both of them perform under high load (many, many nodes).

[sternenseemann]

Making it 3d seems to be a good idea.

Am 16.06.2015 um 15:49 schrieb froozen notifications@github.com:

I talked to @shak-mar today, and he had the great idea of implementing the algorithm as a pathfinding algorithm in a three-dimensional space, the third dimension being the changing probabilities.

I'll probably look into that after some sleep and maybe rewrite the algorithm to check how the both of them perform under high load (many, many nodes).

— Reply to this email directly or view it on GitHub.

[froozen]

Yup. It'll also be a nice chance for me to learn a bit about the different pathfinding algorithms. :)

[fkarg]

This might actually work, if you're seeing it as an 3D - tree, you might actully be able to do it with an only slightly modified A* in the end, as it should be totally fitting for it

[froozen]

I've been thinking about how to approach this new algorithm for a while now, and I've come to the conclusion that we won't get an algorithm that is more efficient than our current one by using a 3D-tree.

The construction of that tree would do exactly the same thing as we are doing with our algorithm right now and running another algorithm, like the A*, over it would only add extra costs. The way we're handling probabilities right now is cutting us off from any more efficient algorithms. There are two ways for us to handle that fact:

• Keeping the inefficient algorithm
• Coming up with a different, simpler weighting scheme for our edges

[nkoehring]

Good that you decided to not split the path finding out into the python part. It would be super slow compared to haskell.

[froozen]

Agreed, though the choice was made mainly for comfort reasons as writing a recursive algorithm in haskell is a lot easier.

[fkarg]

I think you might have the wrong idea as to what a A* is or how to implement it some efficient way @froozen . Either way, I'd come to the lab at Wednesday, I hope to see you there, I'd explain as to how I meant it. And it might be good for what we are going to do next and all. Ah, and don't forget the book ;)

[froozen]

I think it might be useful to state what we decided on when we met, so I'll try just that. Please correct me if I'm wrong.

• We will use the A*
• The waiting ticks for each node will be limited to some fixed number
• The algorithm should load the needed data in the background while running

I'm not quite sure how realistic the last idea is, but we'll just have to see.

[sternenseemann]

Haskell load in background also know as laziness

[froozen]

Lazyness isn't in the background, though. Letting lazyness hadle it means doing all the DB lookups in the main thread and hence not getting the speedup we were hoping to achieve by doing it in the first place.

Another problem with it would be, that the whole algorithm would take place in the IO monad, which isn't really good style.

[froozen]

I just came across exactly what we need: haxl It basically handles the efficient loading of data in the background of pure algorithms.

[sternenseemann]

Intredasting.