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

Question

我写了一部分程序，但找不到如何 continue.This 是我的作业，我已经写了十天了，我的时间快到期了。我的程序要求： a) 通过关键字获取 N 作为输入。 b) 生成 1 到 N*N 之间的随机整数 c) 用这些整数填充矩阵我做了这个，但我不能得到更多。

更多的是=>贪婪的做法例如用户输入 3 作为输入。并像矩阵

一样编程return

1 2 6

4 8 5

3 9 7

最短路径是1,2,6,5,7。另一个示例用户输入 4 作为输入并编写 return 矩阵，如

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;
    }

}

Answer 1

这是我在评论中提到的解决方案的一些 python-ish 伪代码。设 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 本身的级别更高，但实施起来应该很简单。

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

Problems finding the shortest path on the matrix

java

matrix