Given a N ∗ N M atrix M filled with non-negative integers, find all the possible cells M (i, j) where indexes i and j are unique and the sum of those cells is maximized or minimized for all the possible solutions found.
The formal definition of the problem is the following:
Let {P1, P2, ..., Pk, ..., Pn} be a set of solutions for this problem where Pk = {M (i, j)1 +M (i, j)2 +
M (i, j)3 + ... + M (i, j)m−1 + M (i, j)m} = S is a set of coordinates for integers values in a matrix,
and S the sum of those integers for that solution Pk. The S sum is valid only if:
1. All the indexes i and j for that sum of Pk are unique
2. The integer in M (i, j) is not zero
3. Index j in M (i, j)x must be the same as index i in M (i, j)x+1
4. Index i in M (i, j)1 and index j in M (i, j)m must be zero for all the solutions Pk
5. A possible solution Pk is considered optimal only if the sum S of all its integers is the minimum
or the maximum sum S from all the solutions Pk
6. All the vertices but the source vertex must be visited only once. The source vertex is visited
twice because it plays the role of the source and destination vertex in this algorithm
For example, given the following matrix M filled with integers and zeros find all the possible
results that met the above conditions.
∞ 7 1 0 0 8
7 ∞ 5 0 9 6
1 5 ∞ 4 0 0
0 0 4 ∞ 2 0
0 9 0 2 ∞ 3
8 6 0 0 3 ∞
All possible solutions are:
1. P = {M [0][1] + M [1][5] + M [5][4] + M [4][3] + M [3][2] + M [2][0]} = 23
2. P = {M [0][2] + M [2][3] + M [3][4] + M [4][5] + M [5][1] + M [1][0]} = 23
3. P = {M [0][2] + M [2][3] + M [3][4] + M [4][1] + M [1][5] + M [5][0]} = 30
4. P = {M [0][5] + M [5][1] + M [1][4] + M [4][3] + M [3][2] + M [2][0]} = 30
1. (2 points) Create a state-space tree to design a backtracking algorithm to find all the solutions
for the following matrix M . Note that approaches other than creating a state-space tree for
this algorithm won’t get credit. Show all your work
∞ 20 22 21 15 16
20 ∞ 20 14 17 13
22 20 ∞ 23 19 11
21 14 23 ∞ 17 16
15 17 19 17 ∞ 16
16 13 11 16 16 ∞
