3
\$\begingroup\$

I've developed a program in Python that calculates the lowest possible costing path between two points in a matrix, including the values contained in the start and finish cells. The code is below. Once the matrix gets larger than 4×4, it becomes very slow. Are there any obvious problems with my code (recursive method). I'm wondering if this can be improved before looking at other non-recursive approaches.

def legal_moves(rows,cols,path, start):
    list_moves = []
    row_start = start[0]
    col_start = start[1]

    if col_start < cols:
        if col_start == 0:
            new_col_start = [col_start+1, col_start]
        else:
            new_col_start = [col_start+1, col_start-1, col_start]
    else:
        new_col_start = [col_start-1, col_start]

    if row_start < rows:
        if row_start == 0:
            new_row_start = [row_start+1,row_start]
        else:
            new_row_start = [row_start+1, row_start-1, row_start]
    else:
        new_row_start = [row_start-1, row_start]

    for row in new_row_start:
        for col in new_col_start:
            if row == row_start and col == col_start:
                next
            else:
                if [row,col] not in path:
                    list_moves.append([row,col])
    return list_moves

def min_path (rows,cols,path, start, end, path_sum=0):
    if path == None:
        path = [start]
    else:
        path = path [:] + [start]

    row_index = start[0]
    col_index = start[1]

    if start == [0,1] and path_sum == 18:
        print ("",end="")

    path_sum += matrix[row_index][col_index]

    if start == end:
        list_paths.append(path)
        list_sum.append (path_sum)
        return 

    list_moves = legal_moves(rows,cols,path,start)

    for move in list_moves:
        min_path (rows,cols,path, move, end, path_sum)


matrix = [[1,4,6,7],
[3,5,7,8],
[19,2,12,11]]

cols = len(matrix[0]) - 1
rows = len(matrix) - 1
start = [2,3]
end = [0,0]

list_paths = []
list_sum = []
path = None

min_path(rows,cols,path,start,end)
print (f'From: {start} to {end} with a cost of: {min(list_sum)}')
print (f'They are: {list_paths[list_sum.index(min(list_sum))]}')
\$\endgroup\$

Your Answer

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

Browse other questions tagged or ask your own question.