Im trying to solve a Problem for my University Homework, The task is to find the cheapest path trough a NxN Matrix where every Point in the Matrix stores a random Integer between 0 and 9. The Start is at 0,0 and the end at N,N . The Output should consist of the cheapest Path as a List of Tupels and the Cost of the Path(adding up the values of each Step).
I have tried using a Tree where 0,0 is the root and the children are its neighbours in the matrix, and the children of the children are their neighbours and so on. Then i wanted to add up all the nodes that end with N,N as the last child, but i didnt get the tree working in the first place. We havent had Trees in our lectures yet, so im open to any other Solution for this Problem. Thank you :)
import random
import math
def Matrix_gen(n):
# Generate a n*n matrix with random values
matrix = []
for i in range(n):
matrix.append([])
for j in range(n):
matrix[i].append(random.randint(0, 9))
return matrix
MATRIX = Matrix_gen(5)
def get_neighbour(i, j, matrix,):
neighbours = []
n = len(matrix) - 1
for x in range(len(matrix)-1):
for y in range(len(matrix)-1):
if x != n:
if matrix[x+1][y] == matrix[i][j]:
neighbours.append((x + 1, y))
if x != 0:
if matrix[x-1][y] == matrix[i][j]:
neighbours.append((x - 1, y))
if y != n:
if matrix[x][y + 1] == matrix[i][j]:
neighbours.append((x, y + 1))
if y != 0:
if matrix[x][y - 1] == matrix[i][j]:
neighbours.append((x, y - 1))
if matrix[i][j] == matrix[n][n]:
return []
return neighbours
#creat a class that stores a Tree
class Tree:
def __init__(self, value, Children = []):
self.value = value
self.Children = Children
#the root of the tree is the first element of the matrix
def root(self):
#add (0,0) as the value of the root
self.value = (0,0)
return self.value
#add the neighbours of the root as the children of the root
def add_children(self, matrix):
#add the neighbours of the lowest node as the children of the lowest node until
#a node has no neighbours
while get_neighbour(self.value[0], self.value[1], matrix) != []:
self.Children.append(get_neighbour(self.value[0], self.value[1], matrix))
self.value = self.Children[-1]
return self.Children
#print the tree
def print_tree(self):
print(self.value)
for i in self.Children:
print(i)
return
#Create the tree in the Class Tree
Tree = Tree((0,0))
Tree.add_children(MATRIX)
Tree.print_tree()
Please read the open letter to students befor copy and paste any of this. Seek help with your tutor if things are unclear.
Disclaimer: Because this is homework, this is (intentionally) not a complete answer. The answer works under the assumption that we are NOT allowed to go diagonal. Allowing diagonal movements adds additional complexity in the path generation and is left for exercising (the needed flexibility is there).
The code will take longer and longer the bigger N is, because of the definition of the problem. See combination of pathes on a grid. See benchmark below...
I tried to keep the code readable and understandable, there are more compressed and probably also better optimized ways to do this (happy to take comments, given that readability is maintained).
Let's start with a set of functions.
from itertools import permutations
import numpy as np
DOWN = 'D'
RIGHT = 'R'
def random_int_matrix(size: int) -> np.array:
"""Generates a size x size matrix with random integers from 0 to 9"""
mat = np.random.random((size, size)) * 10
return mat.astype(int)
def find_all_paths(size: int):
"""Creates all possible pathes going down and right"""
return [gen_path(perm) for perm in permutations([DOWN] * (size-1) + [RIGHT] * (size-1))]
def gen_path(permutation: str) -> list:
track = [(0, 0)]
for entry in permutation:
if entry == DOWN:
track.append((track[-1][0] + 1, track[-1][1]))
else:
track.append((track[-1][0], track[-1][1] + 1))
return track
def sum_track_values(mat: np.array, track: list) -> list:
"""Computes the value sum for the given path"""
return sum([mat[e[0], e[1]] for e in track])
OK, now we can run the programm
MATRIX_SIZE = 4
matrix = random_int_matrix(MATRIX_SIZE)
print('Randomly generated matrix:\n', matrix)
paths = find_all_paths(MATRIX_SIZE)
costs = np.array([sum_track_values(matrix, p) for p in paths])
min_idx = costs.argmin()
print('Best path:', paths[min_idx])
print('Costs:', costs[min_idx])
In my case the result was
Randomly generated matrix:
[[3 8 6 6]
[2 4 1 4]
[7 4 0 4]
[9 6 8 4]]
Best path: [(0, 0), (1, 0), (1, 1), (1, 2), (2, 2), (2, 3), (3, 3)]
Costs: 18
Small benchmark:
Runtime for N=1: 0.0000 sec (1 possible paths)
Runtime for N=2: 0.0000 sec (2 possible paths)
Runtime for N=3: 0.0001 sec (24 possible paths)
Runtime for N=4: 0.0016 sec (720 possible paths)
Runtime for N=5: 0.1344 sec (40,320 possible paths)
Runtime for N=6: 19.9810 sec (3,628,800 possible paths)