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.
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.
The solution is easy implemented but very very computionally heavy - I would not be suprised if this was NP-complete problem, similar to the travelling salesman.
The solution has two steps:
compute distance between all points (food locations and your location), you can do that with Floyd-Warshall algorithm in n^3 complexity
from then, you need to find the shortest combination such as its first edge connect you to food location and the last one connects to basket, there is roughly V(k,n) such variations(!).
Because of that, I suggest you use greedy/look ahead algorithm, finding not optimal solution but some "good" solution instead.
For greedy you just always pick closest location, for look-ahead you look at the length of next one too (and if you looked more and more ahead, it would turn into near-bruteforce described above, so better to limit it).
"Each food item gives 10 food. How can I find the shortest path that will allow me to collect 30 food",
so you need to collect 3 food items.
This is small enough that you shouldn't need to give up optimality.
.
maxdist = 0 for tile0 in tiles: for tile1 in tiles: maxdist = max(maddest,distance(tile0,tile1)) dtobin = maxdist+1 for bin in bintiles: if distance(startingtile,bin) < dtobin: dtobin = distance(startingtile,bin) closestbin = bin if dtobin == maxdist+1: print("There are no reachable bins!") return [] path = shortestpath(startingtile,closestbin) L = distance(startingtile,closestbin) midpoint = path[round(L/2)] dtofood = maxdist+1 for food in foodtiles: if distance(midpoint,food) < dtofood: dtofood = distance(waypoint,food) food2 = food if dtofood == maxdist+1: print("There is no reachable food!") return [] partofpath = shortestpath(startingtile,food2) L = distance(startingtile,food2) waypoint = path[round(L/2)] dtofood = maxdist+1 for food in foodtiles: if distance(waypoint,food) < dtofood and food != food2: dtofood = distance(waypoint,food) food1 = food if dtofood == maxdist+1: print("There is only one reachable food item!") return [] partofpath = shortestpath(food2,closestbin) L = distnace(food2,closestbin) waypoint = path[round(L/2)] dtofood = maxdist+1 for food in foodtiles: if distance(waypoint,food) < dtofood and food != food2 and food != food1: dtofood = distance(waypoint,food) food3 = food if dtofood == maxdist+1: print("There are only two reachable food items!") return [] bestsofar = distance(startingtile,food1)+distance(food1,food2)+distance(food2,food3)+distance(food3,closestbin) waypointlists = [] for bin in bintiles: if bestsofar < distance(startingtile,bin): continue for food2 in foodtiles: if bestsofar < distance(startingtile,food2)+distance(food2,bin): continue for food1 in foodtiles: partial = distance(startingtile,food1)+distance(food1,food2) if bestsofar < partial+distance(food2,bin) or food2 == food1: continue for food3 in foodtiles: if bestsofar < partial+distance(food2,food3)+distance(food3,bin) or food3 == food2 or food3 == food1: continue currentpathlength = partial+distance(food2,food3)+distance(food3,bin) if currentpathlength < bestsofar: bestsofar = currentpathlength waypointlists = [[food1,food2,food3,bin]] else: waypointlists.append([food1,food2,food3,bin]) return waypointlists (The continue syntax is described here.)
If waypointlists has more than one list, then choose
one of them according to whatever preference you have.
String together shortest paths [between startingtile and the initial waypoint]
and between consecutive waypoints. (Those shortest paths were found in step 1.)
If memory use is not a problem, then that algorithm can almost certainly be sped-up by
making lists of what tiles could possibly help and only trying those. If memory use is not a
problem, then that algorithm can probably be sped-up by trying things in a better order,
so that it will continue more often in the four final for loops, especially the outer loops.
Also, depending on cache behavior (something I have no clue about) and how often it continues
two lines afterward, computing partial might actually be slower than not doing so.