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))]}')