May 31st, 2013, 10:50 AM
Help with algorithm - Delivery problem with LIFO loading
Hello everyone! I've been trying to tackle a problem but I 've reached a roadblock in my train of thought and would appreciate some help...
The description of the problem is the following:
You are given a delivery list of items that have to be moved from one location to another. The number of "locations" is known, and each action you
perform has a "cost":
-moving from one location to another costs 3 points
-loading or unloading an item costs 1 point
The catch is that the items you carry are loaded in a LIFO format, meaning that when you can only load to or unload from the "top" of your currently carried items.
You start from "Home" and have to end there, having satisfied the delivery list with the least possible cost.
For simplicity, the only desired output is the least possible cost.
So, while trying to figure out the problem I 've become stumped, since I cannot prove any possible "simplifications" of the delivery route.
For example, you could say that a smart move is to first completely satisfy a specific location: that is, deliver all its in-bound items and load all
out-bound items, so you don't have to visit this location again. But, I can't be sure that this will always be the least costly decision.
Then again, you can always try to exhaustively search all possible moves and compare costs, but these are too many (what location will you go to? what will
the order of your carried items be?)
So, I would appreciate any help-ideas you have... and thanks for your time (pre-emptively )
Click Here to Expand Forum to Full Width