# Maximize Path Value

I recently had to code an algorithm that will, for an input of: matrix of up to 5x5 size and a defined path length, find a path of this given length from the first top left matrix element (0, 0) to the last bottom right element (n, n). The desired path is the one which maximizes the sum of matrix elements along the path. After reading about common path finding algorithms like Dijkstra or A* and DFS vs. BFS, here is what I've come up with:

def gridsum(grid):
"""Calculates sum of all grid elements"""
s = 0
for el in grid:
s += sum(el)
return s

def longpaths(grid, path):
"""Function to calculate best path for long paths with respect to no. of grid elements"""
# For path length equal to number of grid elements, the solution is trivial:
if path == len(grid)*len(grid[0]):
return gridsum(grid)

# Not sure down to which path length this works..?
if path+1 == len(grid)*len(grid[0]):
s = gridsum(grid)
del grid[0][0]
del grid[len(grid)-1][len(grid[-1])-1]
return s - min(sum(grid, []))

if path+2 == len(grid)*len(grid[0]):
s = gridsum(grid)
del grid[0][0]
del grid[len(grid)-1][len(grid[-1])-1]
m1 = min(sum(grid, []))
s -= m1
for i in range(len(grid)):
if m1 in grid[i]:
gindexm1 = i
grid[gindexm1].remove(m1)
return s - min(sum(grid, []))

class Node():
def __init__(self, parent=None, position=None, value=0):
self.position = position # a tuple representing the indices in grid
self.value = value # grid position value
self.cpl = 0 # current path length
self.cpv = 0 # current path value
self.parents = [parent]
if parent is not None:
for el in parent.parents:
self.parents.append(el)

def __eq__(self, other):
return self.position == other.position

def minsteps(grid, position):
"""Calculates the minimum number of steps necessary to reach target node"""
steps = 0
x, y = position[0], position[1]
while x < len(grid)-1 and y < len(grid[0])-1:
x, y, steps = x+1, y+1, steps+1
while x < len(grid)-1:
x, steps = x+1, steps+1
while y < len(grid[0])-1:
y, steps = y+1, steps+1
return steps

def g_key(grid, path):
# For long paths relative to amount of grid elements, solution is simple
if path+2 >= len(grid)*len(grid[0]):
return longpaths(grid, path)

# Create start and end node
start_node = Node(None, (0, 0), grid[0][0])
start_node.cpv = start_node.value
start_node.cpl = 1
end_node = Node(None, (len(grid)-1, len(grid[0])-1), grid[len(grid)-1][len(grid[0])-1])

# Add a node queue to loop through, start node has not been previously visited
queued_nodes = [start_node]
previously_visited = None
final_path_values = []

while len(queued_nodes) > 0:

# Set current node to first element of queued nodes
current_node = queued_nodes[0]

# If target is unreachable within path length restrictions, skip calculation of this node
if path-current_node.cpl < minsteps(grid, current_node.position):
queued_nodes.remove(current_node)
continue

# Add all paths with length {path} that end at the final node to final paths list
if current_node.cpl == path:
if current_node == end_node:
final_path_values.append(current_node.cpv)
queued_nodes.remove(current_node)
continue

# Generate child nodes to current node, make sure new nodes are within grid and
# have not been visited within the current path, then add them to the node queue
children = []
for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]: # adjacent grid elements
node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])
if any((node_position[0] < 0, node_position[1] < 0, node_position[0] > len(grid)-1, node_position[1] > len(grid[0])-1)):
continue
new_child = Node(current_node, node_position, grid[node_position[0]][node_position[1]])
for parent in new_child.parents:
if parent is not None:
if node_position == parent.position:
previously_visited = True
if previously_visited:
previously_visited = False
continue
children.append(new_child)
queued_nodes.append(new_child)

# Update current path length and value for children
for child in children:
child.cpl = current_node.cpl + 1
child.cpv = current_node.cpv + child.value

# Calculation for this node done, remove it from queue
queued_nodes.remove(current_node)

return max(final_path_values)


For an input of:

g_key([[1, 6, 7, 2, 4],
[0, 4, 9, 5, 3],
[7, 2, 5, 1, 4],
[3, 3, 2, 2, 9],
[2, 6, 1, 4, 0]], 9)


this code finds the correct solution of 46.

However, this algorithm is incredibly slow, as I think it scales with $$\O(n^m)\$$, where n = matrix size and m = path length, and memory intensive since every node has to keep track of every parent/grandparent/great-grandparent node it has to prevent visiting matrix elements multiple times within each path. That is why I had to add the longpaths function to get reasonable runtimes for long paths.

Is there any way to speed this up or at least make it less memory intensive? I have found plenty of documentation how to do this if we just wanted to minimize the path length, but since in this case we want to maximize the path value while keeping a constant path length, I haven't been able to come up with a way to improve on what is basically a brute-force method of calculating everything.

This is pretty easily solvable in O(n^2). Notice that any longest path from a to c with length >1 is a combination of a longest ab path and a longest bc path for some b. What you want to do here is to find the longest path to all squares using dynamic programming.