I have a rectangular grid with obstacles and food items on certain tiles. There are also a few storage bins. Each food item gives 10 food. How can I find the shortest path that will allow me to collect 30 food and bring it back to any storage bin ?
I don't think I can use Dijksra class of algorithms because it does not account for a state (food carried) during the pathfinding.
Answer
There is an approximation for the traveling salesman that will fit your needs very good. It is Cristofides algorithm. Here is how it works:
From your current position calculate a minimum spanning tree to the food items. Stop the calculation when the tree will contain 30 food. Calculate a hamiltonian path from the tree by appending non-visited elements when walking the tree in preorder.
The results created by this approximation are at most 2 times the optimum path. Further details can be found here for example
The runtime complexity is lower than with using floyd warshall, since constructing the minimum spanning tree is of lower complexity. This is especially true for your case as your a using a grid where the triangle inequality applies and no obstacles are on the gird. When there are obstacles, it path-finding needs to be applied. But again, floyd warshal is not necessary. For the minimum spanning tree construction, you only need the nearest neighbor for the tree, which is still of much lower cost.
Just one restriction is that using this method is bound to symmetric path distances between positions, because each branch of the tree may be walked in both directions and therefore they should have the same distance.
No comments:
Post a Comment