Clarification of Question by
tokes-ga
on
03 Dec 2004 08:42 PST
I may be wrong with that answer, but that was the example with a
solution I was given to use as a checking tool. The code needs to be
written in JAVA. You must store the integer objects in the
ArrayLinearList.
Here is all the information about this code:
Given an n*n matrix A and you start at A(0,0). You have to find an
optimal(least-cost) path from A(0,0) to A(n-1,n-1). cost[i][j]
represents the cost of moving onto A(i,j), and it always positive.
Notice that the path always progresses downward (either straight down
or diagonally) or toward the right. That is, when you are on A(i,j),
you can move to either A(i,j+1), A(i+1,j+1), or A(i+1, j) as long as
they are legal locations.
For example, here is a sample least-cost path through a 4*4 matrix.
COST MATRIX OPTIMAL PATH
j j
0 1 2 3 0 1 2 3
0 10 45 37 90 0 x
1 20 32 45 11 1 x x
i i
2 12 31 56 8 2 x
3 9 65 82 20 3 x
Your method leastcostpath() should use dynamic programming to solve
this problem. Define your recurrence equation g(i,j) (which you should
be represented by an int[][] in your method) to be the cost of the
optimal path from A(0,0) to A(i,j).
/ c(0,0) if i=0 and j=0
\ ? if i=0 and j>0
g(i,j)= / ? if i>0 and j=0
\ min(?,?,?) otherwise
package dataStructures;
class LeastCostPath {
// NO data members allowed
// NO constructors needed
public static ArrayLinearList pathSearching(int n, int [][]cost) {
// your code goes here
}
// create helper methods if you need
}
Note: The ArrayLinearList contains the row and column number of each
point in the path from A(0,0) to A(n-1,n-1). In the example above,
LeastCostPath.pathSearching(4, cost) will return the ArrayLinearList
[0,0,1,1,1,2,2,3,3,3]. Store Integer objects in the ArrayLinearList.
You may assume that n > 0.
Note: When backtracking, you don't know the final path length until
you are done backtracking. One way to get around that would be to
assign your path ArrayLinearList in reverse order while backtracking
and then reversing the final result.
You may use the methods of the ArrayLinearList class.
