I'm trying to find an algorithm to find the max sum of non adjacent (adjacent being horizontal/vertical elements) elements in an n sized square grid. I've tried converting the grid into a flow graph and calculating the max flow, but not having much luck. Is there an algorithm to solve this? If not, how would we go about making one?

CodePudding user response：

There is an algorithm for solving this efficiently, using the max-flow min-cut theorem. This involves a series of transformations of your problem-- you may want to verify for yourself why each transformation works.

First, let's get the positive/negative number technicalities out of the way. If your max sum is allowed to be empty, then the smallest it can ever be is 0. If there is at least one positive number in the grid, we never have to take negative numbers into our sum, so we can completely ignore those cells.

However, if your maximum sum can't be empty, and all numbers are negative, then take the single maximum number in the grid as the best sum.

You have a 'grid graph' in two dimensions: each cell corresponds to a vertex, and vertices are adjacent if and only if their cells are horizontally or vertically adjacent.

This is a bipartite graph (just like a chessboard): if you number the rows and columns, then cell (x, y) is adjacent to (x 1, y), (x-1, y), (x, y 1), and (x, y-1). Looking at the parity of x y, a cell is only adjacent to cells whose coordinates sum to the opposite parity.

Now, you're looking for the maximum weighted independent set in this bipartite graph. The algorithm for finding that has been completely laid out in this SO post, and also in this CS StackExchange post with references, so I won't repeat all of the same details again here for a third time.

Instead, here's an outline of the problem transformations, in order:

• Max sum of nonadjacent cells in square grid S

• Maximum weighted independent set of vertices in bipartite graph G

• Minimum weighted vertex cover in G

• Minimum weight cut in flow graph F, where F has same vertices as G plus a source and sink vertex

• Maximum flow in F from source to sink

After removing all negative cells and finding this maximum flow, the answer to your maximum sum question is: (Sum of all cells) - (Max flow in F).