lovasoa
Origin and Destination parameters
Hello,
Firstly, I'm asking myself how this algorithm would compete with a brute force one? Like this one for example. My understanding is that your simulated annealing algorithm returns an approximation using probabilities, which means you won't always get the same output for the same input (while brute force will always find the perfect solution because it will try all possible paths). On the other hand, simulated annealing will be faster than brute force. Am I right?
Secondly, being able to define a fixed starting point and destination point would be amazing. I've no idea how this problem should be called, maybe the "divorced salesman" as seen on StackOverflow. In this same question, they're talking about adding a dummy city whose distances to every other points is 0. Would that be a good option? Is it possible to go that way using your repository?
I will make a fork of your repository anyway because I need to change the distance calculation algorithm to take the earth's radius in account (in my case it won't be x/y but lat/lon instead).
Thank you for your help.
Hello, indeed, brute force is slower when the number of points is large. I would happily welcome a pull request that would add support for defining a starting and ending point and custom distance functions.
I'm not 100% sure if adding a dummy point is the right way to go. What do you think? I will think about it when I got some more time.
Concerning the custom distances: may I ask why you're storing the distances in a flat array instead of a 2D (multidimensional) array? For performance? I think that the code be improved by calculating the distance between each pair of points only once (currently it's calculating A->B and then B->A again). Finally, if two points are equals (i=j) it could simply set the distance to 0. Currently those two small improvements don't have an huge performance impact but if i'm using the haversine distance formula for instance, the performance impact will be higher.
change the distance calculation algorithm to take the earth's radius in account (in my case it won't be x/y but lat/lon instead).
Hi, any updates on being able to use lat/lon?
I would still happily welcome a pull request that would add support for defining a starting and ending point and custom distance functions 🙂