:!:
Minimum-weight Path.
An agent is required to move from the top row to the bottom row of a m × n grid, (i.e. from start position (0,j) 0<=j<n to end position (m - 1,j) 0<=j<n). On each move, the agent may only take one step rightward, diagonally to the down-right, straight down, diagonally to the down-left or leftward.
Hence an agent at position (row=i, column=j) may move to position (i,j+1), (i+1,j+1), (i+1,j), (i+1,j-1) or (i,j-1) provided that the target position is within the grid boundaries.
The path of the agent is the sequence of positions that the agent has visited on her journey, including the starting and ending positions. Positions in the grid have associated weights (>0 and <100), which are specified by a weight matrix of the same dimensions as the grid. The agent can not visit the same position twice in a specific path. The weight of a path is the sum of weights of all the positions visited on the path.
1 2 3 2
2 4 5 1
2 2 1 6
1 1 5 4
For example, the underlined numbers in the figure above illustrate a path (0,2)->(1,2)->(2,1)->(3,0) that starts at position (0,2) and ends at position (3,0) with total weight 11. Note that this is not a min-weight path that starts at (0,2) and ends at (3,0).
The min-weight path in this case is (0,2)->(1,3)->(2,2)->(3,1)->(3,0) with total weight 7 . It is shown in the following figure:
1 2 3 2
2 4 5 1
2 2 1 6
1 1 5 4
The main goal of this assignment is to find the path with the minimal weight from the start position to the end position, using a recursive algorithm.
Write a program that gets as an input:
□ The dimensions of the grid
□ The weights matrix values
□ The starting point on the first row and the ending point on the last row
□ A number N>0.
The output of the program should be:
□ The Nth path found during the recursion.
The recursive algorithm finds all possible paths from start to end given the allowed agent moves. The Nth path is the one found on the Nth time the program visits the end position.
□ The min-path of an agent in the grid and the weight of this path.
Example:
Enter the dimensions of the grid (0<n,m<20):
4 4
Enter 16 weights (>0 and <100) to fill the grid:
1 2 3 2 2 4 5 1 2 2 1 6 1 1 5 4
Enter the starting point in row #0 (0<=j<4):
2
Enter the ending point in row #3 (0<=j<4):
0
Enter number N (>0):
3
The grid is:
1 2 3 2
2 4 5 1
2 2 1 6
1 1 5 4
The path #3 is:
(0,2)->(0,3)->(1,3)->(2,3)->(2,2)->(3,3)->(3,2)->(3,1)->(3,0)
The minimum path of an agent in the grid is:
(0,2)->(1,3)->(2,2)->(3,1)->(3,0)
The weight of the minimum path is:
7
Important notes:
1) You may assume that input is of integer type, but you have to check that numbers entered by the user are within the valid range. In case of invalid input, the program must ask to re-enter the input (See attached executable).
For example:
Enter 16 weights (>0 and <100) to fill the grid:
1 2 3 2 2 4 5 1 2 2 -7 6 1 1 5 4
Input incorrect!
Enter 16 weights (>0 and <100) to fill the grid:
2) If there is more than one solution (more than one path with a minimal weight) you must print the first path found by your program.
The output of your program must be identical to the one produced by the attached executable file. Therefore the agent must follow the following order when evaluating the next step:
a) Rightward.
b) Diagonally to down-right.
c) Downward.
d) Diagonally to down-left.
e) Leftward.
Write please only recursive algoritm please.
Thnks:mrgreen:
