4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How many food/storage bin items will be available on the map? \$\endgroup\$ – ssb Sep 10 '14 at 23:56
  • \$\begingroup\$ It varies depending on the map, food items are about 1 per 16 square tiles and bins 1 per 100 square tiles. Obstacles are large blocks that take about a third of the map. \$\endgroup\$ – vivi Sep 11 '14 at 0:03
4
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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:

  1. compute distance between all points (food locations and your location), you can do that with Floyd-Warshall algorithm in n^3 complexity

  2. 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).

\$\endgroup\$
  • \$\begingroup\$ I think steps 2 and 3 must be combined to account for the case when items close together would be quick to gather, but bring you further from the storage bin, and there are other items further apart but closer to the storage bin reducing the overall path length. \$\endgroup\$ – vivi Sep 11 '14 at 0:17
  • \$\begingroup\$ @vivi you re right. It should indeed be in one step - removing step 3. \$\endgroup\$ – wondra Sep 11 '14 at 0:23
  • \$\begingroup\$ Thanks I realise now that this is similar to the traveling salesman, I'll try to find an approximate solution. \$\endgroup\$ – vivi Sep 11 '14 at 1:04
  • \$\begingroup\$ It can't be very computationally heavy NP-complete or tsp-like because it is bound to 3 food items. Problems can only be computationally complex when the input is unbound. \$\endgroup\$ – AturSams Oct 2 '15 at 6:57
  • \$\begingroup\$ This case it is limited, the problem itself is not. \$\endgroup\$ – wondra Oct 5 '15 at 17:20
1
\$\begingroup\$

"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.

  1. Compute shortest paths and distances from the starting location to each food location,
    between each pair of food locations, and from each food location to each bin location.
    The Floyd-Warshall algorithm can do that, but using Dijkstra's algorithm once with the starting
    location as the initial node and once with each food tile as the initial node will probably
    be faster, since your graph is sparse and all other pairwise information is not important.
  2. Use the algorithm described by the following pseudo-code.

.

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.)

  1. If waypointlists has more than one list, then choose
    one of them according to whatever preference you have.

  2. 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.