我正在嘗試實作一個游戲，其中可行的動作是down-left和down-right。
該函式的引數是陣列的大小，因此如果您傳遞它將是一個4 x 4 陣列。4
起始位置是任何列的第一行。陣列中的每個元素都是 range 中的一個數字，取自檔案。我需要從任何起始列中找到最有利可圖的路線的結果值。1-100
我當前的實作將比較右側位置和左側位置并移動到較高的位置。問題是，例如，如果左側位置的價值低于右側位置，但從長遠來看，左側位置將提供更多利潤，因為它可以訪問更高價值的元素，我的演算法將失敗。
這是一個演示：
84 (53) 40 62
*42* 14 [41] 57
76 *47* 80 [95]
如果我們從 number 開始53。包含的數字*是我的演算法將采取的移動，但包含的數字[]是我的演算法應該采取的移動。
這是我的代碼：
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());
}
}
uj5u.com熱心網友回復：
貪心演算法與動態規劃
您的解決方案的邏輯存在問題。
基本上，您實作的是一種稱為貪心演算法。在迭代的每一步，您都在選擇一個區域最優的結果，假設這個選擇將導致最優的全域結果。即您的代碼基于這樣的假設，即通過在兩列之間選擇區域最大值，您將獲得正確的全域最大值。
因此，您的bestPath()方法中的代碼幾乎在每次迭代時都會丟棄僅基于一個 next value的路徑分支。這種方法可能會導致不正確的結果，尤其是對于大型矩陣。
貪心演算法很少能夠給出準確的輸出，通常它們的結果有點接近但并不精確。作為優勢，它們運行得很快，通常在O(n)時間內。
對于這個問題，您需要使用動態規劃( DP )。
簡而言之，DP是一種增強的蠻力方法，它可以兌現結果并重用它們，而不是多次重新計算相同的值。而且，作為常規的蠻力DP演算法總是檢查所有可能的組合。
動態編程有兩種主要方法：制表法和記憶法（有關更多資訊，請查看這篇文章）。
制表
在首先實作制表時，您需要創建一個陣列，然后需要預先填充（全部或部分）。制表也稱為自下而上的方法，因為計算是從基本的邊緣情況開始的。在迭代這個陣列時，每個可能的結果都是根據先前獲得的值計算的。最終結果通常存盤在最后一個單元格中（在本例中為最后一行）。
要實作制表，我們需要創建相同大小的矩陣，并將給定矩陣中的所有值復制到其中。然后逐行填充每個單元格，其中包含從第一行到達該單元格可以獲得的最大可能利潤。
即每次迭代都會產生一個2D-array的解決方案，在每一步連續增加一行。它將從僅包含一個第一行的陣列開始（不需要更改），然后為了獲得第二行中每個單元格的利潤，它的值必須與第一行的最佳值相結合（這將是大小為 ) 的二維陣列的有效解決方案2 * n，依此類推。這樣，解決方案逐漸發展，最后一行將包含每個單元格的最大結果。
代碼將如下所示：
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);
}
負責從最后一行中提取最大值的輔助方法（如果您想為此使用流，請使用）。 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;
}
記憶
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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/446410.html