I'm trying to implement a game where the viable moves are down-left and down-right.
The parameter for the function is for the size of the array, so if you pass 4 it will be a 4 by 4 array.
The starting position is the top row from any column. Every element in the array is a number in the range 1-100, taken from a file. I need to find the resulting value for the most profitable route from any starting column.
My current implementation will compare the right position and left position and move to whichever is higher. The problem is, for example, if the left position is lower in value than the right, but the left position will provide more profit in the long run since it can access higher value elements, my algorithm fails.
Here is a demo:
84 (53) 40 62
*42* 14 [41] 57
76 *47* 80 [95]
If we start at number 53. The numbers enclosed in * are the moves that my algorithm will take, but the numbers enclosed in [] are the moves my algorithm should take.
This is my code:
import java.util.ArrayList;
import java.util.Scanner;
public class bestPathGame{
private int[][] grid;
private int n;
public bestPathGame(int num){
Scanner input = new Scanner(System.in);
n = num;
grid = new int[n][n];
for(int i = 0; i < n; i ){
for(int j = 0; j < n; j ){
grid[i][j] = input.nextInt();
}
}
}
public static void main(String[] args){
bestPathGame obj = new bestPathGame(Integer.parseInt(args[0]));
obj.bestPath();
}
private boolean moveLeftBetter(int r,int c){
if(c <= 0){
return false;
} else if (c >= n -1 ){
return true;
}
return grid[r][c-1] > grid[r][c 1];
}
public void bestPath(){
ArrayList<Integer> allOptions = new ArrayList<>();
for(int k = 0; k < n; k ){
int row = 0;
int col = k;
int collection = grid[row][col];
while(row < n - 1){
row = 1;
if(moveLeftBetter(row,col)){
col-=1;
} else{
col =1;
}
collection = grid[row][col];
}
allOptions.add(collection);
}
System.out.println(allOptions.stream().reduce((a,b)->Integer.max(a,b)).get());
}
}
CodePudding user response：
Greedy algorithm vs Dynamic programming
There's an issue with the logic of your solution.
Basically, what you are implemented is a called a greedy algorithm. At each step of iteration, you are picking a result that optimal locally, assuming that this choice will lead to the optimal global result. I.e. your code is based on the assumption that by choosing a local maximum between the two columns, you will get the correct global maximum.
As a consequence, your code in the bestPath() method almost at each iteration will discard a branch of paths based on only one next value. This approach might lead to incorrect results, especially with large matrixes.
Greedy algorithms are rarely able to give an accurate output, usually their result is somewhat close but not precise. As an upper-hand, they run fast, typically in O(n) time.
For this problem, you need to use a dynamic programming (DP).
In short, DP is an enhanced brute-force approach which cashes the results and reuses them instead of recalculating the same values multiple times. And as well, as a regular brute-force DP algorithms are always checking all possible combinations.
There are two major approaches in dynamic programming: tabulation and memoization (take a look at this post for more information).
Tabulation
While implementing a tabulation first you need to create an array which then need to be prepopulated (completely or partially). Tabulation is also called the bottom-up approach because calculation start from the elementary edge cases. Every possible outcome is being computed based on the previously obtained values while iterating over this array. The final result will usually be stored in the last cell (in this case in the last row).
To implement the tabulation, we need to create the matrix of the same size, and copy all the values from the given matrix into it. Then row by row every cell will be populated with the maximum possible profit that could be obtained by reaching this cell from the first row.
I.e. every iteration will produce a solution for a 2D-array, that continuously increases by one row at each step. It'll start from the array that consists of only one first row (no changes are needed), then to get the profit for every cell in the second row it's values has to be combined with the best values from the first row (that will be a valid solution for 2D-array of size 2 * n), and so on. That way, solution gradually develops, and the last row will contain the maximum results for every cell.
That how the code will look like:
public static int getMaxProfitTabulation(int[][] matrix) {
int[][] tab = new int[matrix.length][matrix.length];
for (int row = 0; row < tab.length; row ) { // populating the tab to preserve the matrix intact
tab[row] = Arrays.copyOf(matrix[row], matrix[row].length);
}
for (int row = 1; row < tab.length; row ) {
for (int col = 0; col < tab[row].length; col ) {
if (col == 0) { // index on the left is invalid
tab[row][col] = tab[row - 1][col 1];
} else if (col == matrix[row].length - 1) { // index on the right is invalid
tab[row][col] = tab[row - 1][col - 1];
} else {
tab[row][col] = Math.max(tab[row - 1][col - 1], tab[row - 1][col 1]); // max between left and right
}
}
}
return getMax(tab);
}
Helper method responsible for extracting the maximum value from the last row (if you want to utilize streams for that, use IntStream.of(tab[tab.length - 1]).max().orElse(-1);).
public static int getMax(int[][] tab) {
int result = -1;
for (int col = 0; col < tab[tab.length - 1].length; col ) {
result = Math.max(tab[tab.length - 1][col], result);
}
return result;
}
Memoization
The second option is to use Memoization, also called the top-down approach.
As I said, DP is an improved brute-force algorithm and memoization is based on the recursive solution that generates all possible outcomes, that is enhanced by adding a HashMap that stores all previously calculated results for every cell (i.e. previously encountered unique combination of row and column).
Recursion starts with the first row and the base-case of recursion (condition that terminates the recursion and is represented by a simple edge-case for which output is known in advance) for this task is when the recursive call hits the last row row == matrix.length - 1.
Otherwise, HashMap will be checked whether it already contains a result. And if it not the case all possible combination will be evaluated and the best result will be placed into the HashMap in order to be reused, and only the then the method returns.
Note that tabulation is usually preferred over memoization, because recursion has significant limitations, especially in Java. But recursive solutions are sometimes easier to came up with, so it's completely OK to use it when you need to test the idea or to prove that an iterative solution is working correctly.
The implementation will look like that.
public static int getMaxProfitMemoization(int[][] matrix) {
int result = 0;
for (int i = 0; i < matrix[0].length; i ) {
result = Math.max(result, maxProfitHelper(matrix, 0, i, new HashMap<>()));
}
return result;
}
public static int maxProfitHelper(int[][] matrix, int row, int col,
Map<String, Integer> memo) {
if (row == matrix.length - 1) { // base case
return matrix[row][col];
}
String key = getKey(row, col);
if (memo.containsKey(key)) { // if cell was already encountered result will be reused
return memo.get(key);
}
int result = matrix[row][col]; // otherwise result needs to be calculated
if (col == matrix[row].length - 1) { // index on the right is invalid
result = maxProfitHelper(matrix, row 1, col - 1, memo);
} else if (col == 0) { // index on the left is invalid
result = maxProfitHelper(matrix, row 1, col 1, memo);
} else {
result = Math.max(maxProfitHelper(matrix, row 1, col - 1, memo),
maxProfitHelper(matrix, row 1, col 1, memo));
}
memo.put(key, result); // placing result in the map
return memo.get(key);
}
public static String getKey(int row, int col) {
return row " " col;
}
Method main() and a matrix-generator used for testing purposes.
public static void main(String[] args) {
int[][] matrix = generateMatrix(100, new Random());
System.out.println("Tabulation: " getMaxProfitTabulation(matrix));
System.out.println("Memoization: " getMaxProfitMemoization(matrix));
}
public static int[][] generateMatrix(int size, Random random) {
int[][] result = new int[size][size];
for (int row = 0; row < result.length; row ) {
for (int col = 0; col < result[row].length; col ) {
result[row][col] = random.nextInt(1, 101);
}
}
return result;
}