Quote:
Originally Posted by Andrew Schreiber
I'd still like to see various simulation runs with differing paths as generated by objective functions tuned for various variables (distance travelled, time taken, energy consumed) and various weightings of all of those.
|
That's an interesting challenge. You could choose a board and come up with a bunch of different weights for each of the factors, run with each and then plot each result and be able to see where the switches are between different routes chosen.
I'm now going to go off on a tangent:
I wonder if there's some systematic way solve for what the set of all optimal paths given a set of objective functions that are a linear combination of three other functions. I guess you could do something like breadth-first search but extend your "previous" table to keep track of all the different ways to get there that could be optimal under some set of conditions.
So if you have the weights of distance, time and enery as x, y, and z then at each point you might get you previous table to look like:
prev[(2,2)]=[
Point(2,1),(2x+3y+z),
Point(1,2),(3x+2y+z),
Point(1,2),(x+y+2z),
]
which would show that to get to the point at (2,2) you can come either (2,1) or (1,2) and that there are two different paths to get there via (1,2) which have different costs.
At each point, when you found a differet way to get there, you'd have to go through the table and see if there were any entries that were strictly shorter (less than or equal coefficients for each of the variables). And if not, you'd have to put in back in the queue to visit even if you'd been there before.
At the end, you'd get set of conditions under which you should have come from each direction, and would be able to say what the exact regions (of the objective function weights) were for each.
I haven't thought too hard about what the runtime or space complexity of this would be but it seems like it wouldn't be terrible in practive as long as there was some correlation between the different cost functions.