在矩阵上寻找最短路径的问题

Question

在矩阵上寻找最短路径的问题

javamatrix

3

我写了程序的一部分，但不知道如何继续。这是我的作业，我已经工作了十天了，时间快要到期了。

我的程序要求：

a）通过关键字获取N作为输入。

b）生成1到N * N之间的随机整数

c）用这些整数填充矩阵

我已经完成了这个方面，但是我不能再做更多了。

更多内容是贪心法，

例如，用户输入3作为输入。

程序返回一个像矩阵的东西

1 2 6

4 8 5

3 9 7

最短路径是1,2,6,5,7。

另一个例子，用户输入4作为输入，程序返回像这样的矩阵

14 11 6 8

15 3 16 1

10 4 2 5

12 9 7 13

最短路径可以是14,11,3,4,2,5,13，

并且路径中不允许交叉步骤。

我的代码如下。

import java.util.*;

public class Challenge1 {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("Enter a value for the matrix size.");
        int length = input.nextInt();
        int[][] x = randomMatrix(length);

        for (int i = 0; i < x.length; i++) {
            for (int j = 0; j < x[i].length; j++) {
                System.out.print(x[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static int[][] randomMatrix(int n) {
        Random r = new Random();
        int[][] matrix = new int[n][n];
        boolean[] trying = new boolean[n * n];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                matrix[i][j] = r.nextInt(n * n) + 1;
                if (trying[matrix[i][j] - 1] == false)
                    trying[matrix[i][j] - 1] = true;

                else {
                    while (trying[matrix[i][j] - 1] == true) {
                        matrix[i][j] = r.nextInt(n * n) + 1;
                    }
                    trying[matrix[i][j] - 1] = true;
                }
            }
        }
        return matrix;
    }

}

- ZpCikTi

4

这些数字在寻找最短路径时有任何意义吗？为了澄清，我不知道您所说的“更多就是=>检查邻居数量，并继续使用最小值”的含义，它是无法理解的。 - lared

我认为路径应该从左上角开始，到右下角结束；其成本将是位于路径中的条目的总和。 - Codor

1

@ZpCikTi 我怀疑贪心算法会得到全局最优解。 - Codor

是的，这是贪心算法。 - ZpCikTi

@ZpCikTi 你读过关于穷举递归算法的内容吗？在这个例子中，基本思路是有一个先前访问过的矩阵元素列表；然后对于每个访问过的节点（从左上角开始），您递归地访问尚未访问过的相邻节点。每次访问时更新成本，在到达终点时将其与先前记录的最小成本进行比较。这种算法耗尽了所有可能的路径，因此被命名为“穷举”。 - lared

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- lared · Answer 1

以下是我在评论中提到的解决方案的Python伪代码。让shortestPath是一个最初为空的列表，而shortestPathCost是迄今为止找到的最短路径的权重之和。最初它的值为+infinity。两者都在全局可见。

 Procedure exhaustiveSearch (currentCost, currentPath, endNode):
      currentNode = currentPath.last
      if currentNode == endNode and currentCost < shortestPathCost:
           shortestPath = currentPath
           shortestPathCost = currentCost
           return

      for each neighbouringNode of currentNode not in currentPath:
           exhaustiveSearch (currentCost + neighbouringNode.cost, 
                             currentPath + neighbouringNode,
                             endNode)

就是这样。参数是按值复制的。如果您这样调用它：

 exhaustiveSearch(0, [firstNode], endNode);

shortestPath和shortestPathCost将保存网格中最短路径之一。显然，解决方案比Java本身的级别高一些，但实现起来应该很简单。