So I am on a new project at work that goes live next month. Part 1 and 2 are easy and we are going swimmingly. Part 3 however, involves taking data points from 1 and 2 and making the shortest path between them. Optimally short, all the time.
I dunno how to explain it to my boss that while it is possible to make a solution for it, it is very much not within my realm to make it optimal all the time. I could do it for like maybe 4 I think, but there is also the problem that there are obstacles in the way of these data points. Like immoveable walls. So even though the points are 4 feet away from each other physically, it is probably about 20 feet traveling distance. So I have to add in those coordinates as impassable among other things.
I have told him this, and he has basically said it is what his bosses want. And those bosses shareholders. So come January I will either have a Fields Medal or probably just getting yelled and fired. Whatever, it is a temp job.
If he's dumb enough to think it's possible, then you can obviously just use a good heuristic algorithm and say it's pretty much optimal.
Jack Jackson
I'm quite sure your problem is not equivalent to the TSP, but quite simpler try dynamic programming
Cameron Stewart
Better start plotting vectors
Carter Long
I am mostly just concerned of those outlying cases where the algorithm says do x and x is actually longer than the common sense one.
It's probably not, but it is just the scale of it. There could be anywhere from 3 data points to 50 to more. Plus for each location there could be anywhere from 100-200 requests for solutions an hour.
Samuel Nelson
sounds like a really small scale, you know? you can most likely do very well with some simple dynamic programming
either way, the best bet for something like this in an actual large scale is heuristics. >the algorithm says do x and x is actually longer than the common sense one then your heuristic sucks
Brody Myers
I have been using nearest neighbor in my trials and it is just a problem with that in itself. The "Unique Worse Possible Tour". I dunno about half of this shit. I am mostly a data guy sure, but this is like Math degree worthy stuff.
Kevin Lewis
You need to find the shortest path between two points? I must be a brainlet, but by what you said something like bidirectional dijikstra should work. As long as you model your graph right. If things can change around (or parts of the graph might be unknow), search for the Canadian Traveller Problem
Easton Rogers
Also, if your distances obey the triangle inequality you can find almost optimal solutions to TSP very fast
this doesn't sound like traveling salesman, more like shortest path problem, which is solvable really fast.
Blake Hughes
There's more than two points by the sound of it. Looks like it is to TSP as Hamiltonian path is to Hamiltonian cycle. In fact you should be able to reduce it to it, couldn't you? Like if you add in a vertex to the graph and join it to all other points with the same weight then you have a reduction and solving TSP would solve it. As for the other way around, couldn't you just do something like for each edge, remove it and run OP's algo (if it exists) and then add in the edge and for all of those, see which is best? Seems like they're both polytime reducible to each other.
But yeah OP, there are actually some pretty decent in practice TSP algos out there, even if they aren't polytime in the worst case.
I wish I had your job OP because that sounds like a fun project.
Nicholas Evans
>. Looks like it is to TSP as Hamiltonian path is to Hamiltonian cycle. You mean like a minimum spanning tree connecting all the relevant datapoints of a query?
Im too drunk to parse what you wrote any other way. But yup, sounds like a fun job.
Even if your problem is different, by the sound of it some of the techniques they discuss might be relevant (specially if you need to cull parts of the networks during queries for speedup.) I really dunno if there techniques to speedup MST constructions.
Lucas Sullivan
No wait, I understood what you meant. But I don't think your reduction from TSP problem to OP's problem would work (note that OP says on his post that he needs to connect some points, not all of them). Your operation of adding edges doesn't garantee that the final solution is optimal. Simply placing another edge on the graph could mean needing to throw the entire solution away, as the new edge could invalidade most of it. If it might happen (and in this case, it can happen) that none of your candidate solutions might be optimal, the best of them won't be optimal either and the reduction fails. Further still, adding that last edge doesn't even garantee that you will get a cicle. And even if you had to go through all vertices, I don't think this sort of naive local optimization strategy would work.
On the example you need to find a path connecting S, T_1 and T_2. The red edge is the removed one, and the green lines are the path without the red edge. On example, the optimal path with the removed edge shares only one edge with the optimal path without it. Also, simply adding the removed edge on the path isn't enough to turn it into a actual cicle.
Dylan Walker
>Your operation of adding edges doesn't garantee that the final solution is optimal.
Why not? Every possible cycle has to go through the new vertex, and the edges you add are the same weight.
That is unless OP requires the route to be in a certain order, rather than just some route that connects all dots.
But yeah, if the order doesn't matter I fail to see how the reduction doesn't hold. I could be missing something though since I didn't think too deeply about it. This isn't a local optimization. You're not adding edges within the graph, just to the new added vertex.
>(note that OP says on his post that he needs to connect some points, not all of them).
Oh, I must have missed that, sorry. Disregard the rest of this if that is indeed the case.
Actually why does this matter? Can't you just transform the graph into a different graph that we could apply this to? Simply for each two pair of points run Dijkstra/A* between them (polytime), and then use that as an edge with the entire path's weight in the new graph. Then once you find a solution in the condensed graph you can easily turn it into one in the original one. It should still be optimal since the path has to go through those vertices, right?
That would work, right? Or can you not revisit vertices? (since then two edges in the new condensed graph could have shared vertices in the original one).
like pic related.
And if order does matter 100% then obviously the entire thing to begin with could just be done with repeated Dijkstra/A*. And if you just have the start/end fixed, couldn't you just add in 2 extra vertices, connected to the start end end respectively? I still don't understand why they need 100% optimal answers though. Surely a certain quality guarantee should be fine... Although if there are only like
Carson Rogers
You can program that by using restrictions, but you may need to get creative of how to code it (for example, I assume you do have a hallway connecting everything? You could solve the shortest path to visit the points in the hallway, and then the shortest path in the rooms you visit as an approach to the optimal, with the logic that on each room the shortest path to the door will be the same and if you solve for the distance between doors, you solve the problem). You could also use algorithms or heuristics for picking and adapt them, they do assume you can only go through hallways (you can check how they program it for ideas as in how you can do it). Another option would be to create fictional points that you need to pass in order to evade obstacles and use Dijkstra or Floyd warshall (basically you obtain the shortest distance and path between any pair of points) on said problem (you may need more than one Dijkstra to get all the distances you need).
Note that you get the shortest distance between points with Dijkstra, and you use those distances to use touring heuristics, so either way you need to solve the shortest distance between points first.
I do work on Supply Chain management and I had to solve similar problems, I may not fully understand what op meant because English is not my first language (also, maybe I wasn't clear on what I meant). I'm familiar with various heuristics and problems of this sort, maybe draw a map or something and specify more (do you need to update the route when you reach a point, or when a new "order" appears, or maybe at the beginning of an hour or a day?) about extra info.
Josiah Anderson
Since he talks about physical obstructions, it probably does?
Brandon Allen
>tfw when somone on 4chin cites a paper from your uni
