2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The desired path length is given as input, we're interested in the path of this length that maximizes the sum of matrix elements it passes by (for the example input I provided, the path of length 9 is: (start: element (0, 0)) 1, 6, 7, 9, 5, 5, 4, 9, 0 (end: element (n, n)), the sum of which is 46). Breaking the problem down into smaller subproblems does not seem trivial to me, since the final solution for path length of x may be completely different from the final solution for path length of x-1 and thus not composed of the solutions for shorter paths. \$\endgroup\$ – SquaricAcid Apr 3 at 1:16

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.