Modeling a graph in Python

Question

I'm trying to solve a problem related to graphs in Python. Since its a comeptitive programming problem, I'm not using any other 3rd party packages.

The problem presents a graph in the form of a 5 X 5 square grid. A bot is assumed to be at a user supplied position on the grid. The grid is indexed at (0,0) on the top left and (4,4) on the bottom right. Each cell in the grid is represented by any of the following 3 characters. ‘b’ (ascii value 98) indicates the bot’s current position, ‘d’ (ascii value 100) indicates a dirty cell and ‘-‘ (ascii value 45) indicates a clean cell in the grid. For example below is a sample grid where the bot is at 0 0:

b---d
-d--d
--dd-
--d--
----d

The goal is to clean all the cells in the grid, in minimum number of steps. A step is defined as a task, where either i) The bot changes it position ii) The bot changes the state of the cell (from d to -)

Assume that initially the position marked as b need not be cleaned. The bot is allowed to move UP, DOWN, LEFT and RIGHT.

My approach

I've read a couple of tutorials on graphs,and decided to model the graph as an adjacency matrix of 25 X 25 with 0 representing no paths, and 1 representing paths in the matrix (since we can move only in 4 directions). Next, I decided to apply Floyd Warshell's all pairs shortest path algorithm to it, and then sum up the values of the paths. But I have a feeling that it won't work. I'm in a delimma that the problem is either one of the following:

i) A Minimal Spanning Tree (which I'm unable to do, as I'm not able to model and store the grid as a graph).

ii) A* Search (Again a wild guess, but the same problem here, I'm not able to model the grid as a graph properly).

I'd be thankful if you could suggest a good approach at problems like these. Also, some hint and psuedocode about various forms of graph based problems (or links to those) would be helpful. Thank

Answer 1

I think you're asking two questions here.

1. How do I represent this problem as a graph in Python?

As the robot moves around, he'll be moving from one dirty square to another, sometimes passing through some clean spaces along the way. Your job is to figure out the order in which to visit the dirty squares.

# Code is untested and may contain typos. :-)

# A list of the (x, y) coordinates of all of the dirty squares.
dirty_squares = [(0, 4), (1, 1), etc.]
n = len(dirty_squares)    

# Everywhere after here, refer to dirty squares by their index
# into dirty_squares.

def compute_distance(i, j):
  return (abs(dirty_squares[i][0] - dirty_squares[j][0])
          + abs(dirty_squares[i][1] - dirty_squares[j][1]))

# distances[i][j] is the cost to move from dirty square i to
# dirty square j.
distances = []
for i in range(n):
  distances.append([compute_distance(i, j) for j in range(n)])

# The x, y coordinates of where the robot starts.
start_node = (0, 0)

# first_move_distances[i] is the cost to move from the robot's
# start location to dirty square i.
first_move_distances = [
  abs(start_node[0] - dirty_squares[i][0])
      + abs(start_node[1] - dirty_squares[i][1]))
  for i in range(n)]

# order is a list of the dirty squares.
def cost(order):
  if not order:
    return 0  # Cleaning 0 dirty squares is free.
  return (first_move_distances[order[0]]
          + sum(distances[order[i]][order[i+1]]
                for i in range(len(order)-1)))

Your goal is to find a way to reorder list(range(n)) that minimizes the cost.

2. How do I find the minimum number of moves to solve this problem?

As others have pointed out, the generalized form of this problem is intractable (NP-Hard). You have two pieces of information that help constrain the problem to make it tractable:

1. The graph is a grid.
2. There are at most 24 dirty squares.

I like your instinct to use A* here. It's often good for solving find-the-minimum-number-of-moves problems. However, A* requires a fair amount of code. I think you'd be better of going with a Branch-and-Bound approach (sometimes called Branch-and-Prune), which should be almost as efficient but is much easier to implement.

The idea is to start enumerating all possible solutions using a depth-first-search, like so:

  # Each list represents a sequence of dirty nodes.
  []
  [1]
  [1, 2]
  [1, 2, 3]
  [1, 3]
  [1, 3, 2]
  [2]
  [2, 1]
  [2, 1, 3]

Every time you're about to recurse into a branch, check to see if that branch is more expensive than the cheapest solution found so far. If so, you can skip the whole branch.

If that's not efficient enough, add a function to calculate a lower bound on the remaining cost. Then if cost([2]) + lower_bound(set([1, 3])) is more expensive than the cheapest solution found so far, you can skip the whole branch. The tighter lower_bound() is, the more branches you can skip.

Answer 2

Let's say V={v|v=b or v=d}, and get a full connected graph G(V,E). You could calculate the cost of each edge in E with a time complexity of O(n^2). Afterwards the problem becomes exactly the same as: Start at a specified vertex, and find a shortest path of G which covers V.

We call this Traveling Salesman Problem(TSP) since 1832.

Answer 3

The problem can certainly be stored as a graph. The cost between nodes (dirty cells) is their Manhattan distance. Ignore the cost of cleaning cells, because that total cost will be the same no matter what path taken.