如何使用动态规划求复杂条件下所有可能路径的数量？

问题描述 投票：0回答：0

数组代表一张地图，其中'0'代表空地，'1'代表无法通过的障碍物。

int[][] map = {
                { 0, 0, 2, 0, 0, 0, 1, 1, 1, 1 },
                { 0, 1, 0, 1, 1, 0, 0, 0, 1, 1 },
                { 0, 1, 0, 1, 1, 0, 1, 0, 1, 1 },
                { 0, 1, 0, 1, 1, 0, 0, 2, 0, 1 },
                { 0, 1, 0, 1, 1, 0, 0, 1, 0, 1 },
                { 0, 1, 0, 1, 1, 0, 1, 1, 0, 1 },
                { 0, 1, 0, 0, 0, 0, 1, 1, 0, 1 },
                { 0, 1, 0, 1, 1, 1, 1, 1, 0, 1 },
                { 0, 1, 0, 1, 1, 1, 1, 0, 0, 1 },
                { 0, 0, 0, 1, 1, 1, 1, 0, 1, 1 },
                { 0, 1, 1, 1, 1, 0, 0, 0, 0, 1 },
                { 0, 1, 1, 0, 0, 2, 1, 1, 0, 1 },
                { 0, 1, 1, 0, 1, 0, 0, 1, 0, 0 },
                { 0, 1, 1, 0, 1, 1, 0, 1, 1, 0 },
                { 0, 1, 1, 0, 1, 1, 0, 1, 0, 0 },
                { 2, 0, 0, 0, 1, 1, 0, 0, 0, 1 },
                { 0, 1, 1, 1, 1, 1, 1, 1, 0, 1 },
                { 0, 1, 1, 1, 1, 1, 1, 1, 0, 1 },
                { 0, 0, 0, 0, 1, 0, 0, 0, 0, 1 },
                { 0, 1, 1, 1, 1, 1, 1, 1, 0, 3 }
        };

一个人要从左上往右下移动，标记为3。图中0表示空地，可以自由行走。 1表示障碍物，不允许他通过。 3表示最终目的地。

任务是找出从左上角到右下角的可能路径总数，标记为'3'。有效路径有几个限制：

  1. 只允许彼此相邻的运动（左，右，上，下）而不是对角线。
  2. 一旦一个像素在单次旅程中被访问过，就不能再次访问它。
  3. 单程应该去过'numOfStation'次站。该站标记为 2.

我提示了 chatGPT（模型 3.5 和模型 4.0）的代码，但它只是给了我错误的代码。它给我的代码如图所示。

public class MapPathFinder {
    private int[][] map;
    private int n;
    private int numOfStation;

    public MapPathFinder(int[][] map, int numOfStation) {
        this.map = map;
        this.n = map.length;
        this.numOfStation = numOfStation;
    }

    public int findNumOfPaths() {
        int[][][] dp = new int[n][n][numOfStation + 1]; // 3D array to store subproblem solutions
        // dp[i][j][k] stores the number of valid paths from (0, 0) to (i, j) that pass
        // through k stations

        // initialize base cases
        dp[0][0][0] = 1;
        for (int k = 1; k <= numOfStation; k++) {
            // initialize the first row and first column for each k
            if (map[0][k] == 2) {
                dp[0][k][1] = dp[0][k - 1][1];
            }
        }
        for (int k = 1; k <= numOfStation; k++) {
            if (map[k][0] == 2) {
                dp[k][0][1] = dp[k - 1][0][1];
            }
        }

        // fill the 3D array bottom-up
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                if (i >= n || j >= n || map[i][j] == 1) {
                    // current cell is outside the bounds of the map or is an obstacle, skip it
                    continue;
                }
                for (int k = 1; k <= numOfStation; k++) {
                    int paths = 0;
                    if (map[i][j] == 2) {
                        // if the current cell is a station, increment k
                        k++;
                    }
                    if (k <= numOfStation) {
                        // update the solution only if k is valid
                        if (map[i - 1][j] != 1) {
                            // if the cell above the current cell is not an obstacle, add its value to paths
                            paths += dp[i - 1][j][k];
                        }
                        if (map[i][j - 1] != 1) {
                            // if the cell to the left of the current cell is not an obstacle, add its value
                            // to paths
                            paths += dp[i][j - 1][k];
                        }
                        dp[i][j][k] = paths;
                    }
                }
            }
        }

        return dp[n - 1][n - 1][numOfStation];

    }

代码可能有两个错误：

ArrayIndexOutOfBoundsException，如本例所示：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 10 out of bounds for length 10
        at Assignment.MapPathFinder.findNumOfPaths(MapPathFinder.java:36)
        at Assignment.MapPathFinder.main(MapPathFinder.java:90)
  1. 不正确的输出。例如，对于给定的数组，它应该输出 16，但它却输出 0。

回溯技术经过测试，可以成功解决问题。我现在正在研究解决问题的其他算法。这里还有更多测试用例：

测试用例 2：numOfStation = 3，路径 = 41

int[][] map = {
    {0, 0, 2, 0, 0, 0, 1, 1, 1, 1},
    {0, 1, 0, 1, 1, 0, 0, 0, 1, 1},
    {0, 1, 0, 1, 1, 0, 1, 0, 1, 1},
    {0, 1, 0, 1, 1, 0, 0, 2, 0, 1},
    {0, 1, 0, 1, 1, 0, 1, 1, 0, 1},
    {0, 1, 0, 1, 1, 0, 1, 1, 0, 1},
    {0, 1, 0, 0, 0, 0, 1, 1, 0, 1},
    {0, 1, 0, 1, 1, 0, 1, 1, 0, 1},
    {0, 1, 0, 1, 1, 2, 1, 0, 0, 1},
    {0, 0, 0, 1, 1, 0, 1, 0, 1, 1},
    {0, 1, 1, 1, 1, 0, 0, 0, 0, 1},
    {0, 1, 1, 0, 0, 0, 1, 2, 0, 1},
    {0, 1, 1, 0, 1, 0, 0, 1, 0, 0},
    {0, 1, 1, 0, 1, 1, 0, 1, 1, 0},
    {0, 1, 1, 0, 1, 1, 0, 1, 0, 0},
    {2, 0, 0, 0, 1, 1, 0, 0, 0, 1},
    {0, 1, 1, 1, 1, 1, 1, 1, 0, 1},
    {0, 1, 1, 1, 1, 1, 1, 1, 0, 1},
    {0, 0, 0, 0, 1, 0, 0, 0, 0, 1},
    {1, 1, 1, 0, 0, 0, 1, 1, 0, 3}
};

测试用例 3：numOfStation = 3，路径 = 38

int[][] map = {
                {0, 0, 2, 0, 0, 0, 1, 1, 1, 1},
                {0, 1, 0, 1, 1, 0, 0, 0, 1, 1},
                {0, 1, 0, 1, 1, 0, 1, 0, 1, 1},
                {0, 1, 0, 1, 1, 0, 0, 2, 0, 1},
                {0, 1, 0, 1, 1, 2, 0, 1, 0, 1},
                {0, 1, 0, 1, 1, 0, 1, 1, 0, 1},
                {0, 1, 0, 0, 0, 0, 1, 1, 0, 1},
                {0, 1, 0, 1, 1, 1, 1, 1, 0, 1},
                {0, 1, 0, 1, 1, 1, 1, 0, 0, 1},
                {0, 0, 0, 1, 1, 1, 1, 0, 1, 1},
                {0, 1, 1, 1, 1, 0, 0, 0, 0, 1},
                {0, 1, 1, 0, 0, 2, 1, 1, 0, 1},
                {0, 1, 1, 0, 1, 0, 0, 1, 0, 0},
                {0, 1, 1, 0, 1, 1, 0, 1, 1, 0},
                {0, 1, 1, 0, 1, 1, 0, 1, 0, 0},
                {2, 0, 0, 0, 1, 1, 0, 0, 0, 1},
                {0, 1, 1, 0, 1, 1, 1, 1, 0, 1},
                {0, 1, 1, 0, 1, 1, 1, 1, 0, 1},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
                {1, 1, 1, 1, 1, 1, 1, 1, 0, 3}
             };

测试用例 4：numOfStation = 3，路径 = 27

int[][] array = {
    {0, 0, 2, 0, 0, 0, 1, 1, 1, 1},
    {0, 1, 0, 1, 1, 2, 0, 0, 1, 1},
    {0, 1, 0, 1, 1, 0, 1, 0, 1, 1},
    {0, 1, 0, 1, 1, 0, 1, 0, 1, 1},
    {0, 1, 0, 1, 1, 2, 0, 0, 0, 1},
    {0, 1, 0, 1, 1, 0, 1, 1, 0, 1},
    {0, 1, 0, 0, 0, 0, 1, 1, 0, 1},
    {0, 1, 0, 1, 0, 1, 1, 1, 0, 1},
    {0, 1, 0, 1, 0, 1, 1, 0, 0, 1},
    {0, 0, 0, 0, 0, 1, 1, 0, 1, 1},
    {0, 1, 1, 0, 1, 0, 0, 0, 0, 1},
    {0, 1, 1, 0, 0, 2, 1, 1, 0, 1},
    {0, 1, 1, 0, 1, 0, 0, 1, 0, 0},
    {0, 1, 1, 0, 1, 1, 0, 1, 1, 0},
    {0, 1, 1, 0, 1, 1, 0, 1, 0, 0},
    {2, 0, 0, 0, 1, 1, 0, 0, 0, 1},
    {0, 1, 1, 1, 1, 1, 1, 1, 0, 1},
    {0, 1, 1, 1, 1, 1, 1, 1, 0, 1},
    {0, 0, 0, 0, 1, 0, 0, 0, 0, 1},
    {1, 1, 1, 0, 0, 0, 1, 1, 0, 3}
};
java dynamic-programming maze
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.