A thief steals from you and gets a 20 meter head start. You could easily catch him on open ground, since you can run twice as fast and so catch up 5 meters for every 10 meters you travel. Once the theif reaches a time warp he is trying to get back to , you cant catch him and there are a bunch of rivers in the path: see Figure. There are N places (marked by black lines) shallow enough to cross, but you'll get 5 meters further behind for every 10 meters of river you cross. Assume the thief is too terrified to consider moving back towards the left side of the map. Given the starting and ending locations, and the positions of (both ends of) the N crossings, i want an algorithm to find whether it is possible for the thief to escape, i.e., to reach the end location before you catch up. i am struggling on how to approach this problem .. any ideas are highly appreciated ..thanks
CodePudding user response：
It's a bit unclear what exactly is needed here, but here's an outline of an approach to solve this problem:
You need to create an acyclic graph from the picture given with two sets of weights, one for you and one for the thief that represents how much time it takes each of you to travel that far (or alternatively, two acyclic graphs with the same shape but different weights):
Make nodes/vertexes out of: the starting and ending (timewarp) points, the entry points to every bridge and the exit points from every bridge.
Make edges that connect the entry point vertices of every bridge to their own exit point vertices. Set the thief's edge-weights to the length of the bridge and set yours to 1.5 times that.
Make edges from the starting point vertex to the entry points of every bridge that crosses the first river.
Make edges from the exit point vertices of every bridge over the first river to the entry point vertices of every bridge over the second river.
Repeat step 4 until you get to the last river.
Make edges from the exit point vertices of every bridge over the last river to the timewarp's vertex.
For every non-bridge edge, set the thief's weights equal to their length, and set your weights to half that.
Now, you can use A* search algorithm to determine how long it takes the their and you to get to the timewarp. Whoever would get there first wins.
For A* you need some kind of global maximum distance estimating function, if you cannot derive something for that, just use a maximum possible distance for every thing. If you do this, A* devolves into Djikstra's algorithm, which still works but is slower.