我写了程序的一部分,但找不到如何继续。这是我的作业,我已经写了十天了,我的时间即将到期。 我的计划要求: 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;
}
}
最佳答案
这是我在评论中提到的解决方案的一些 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 本身要高一些,但它应该很容易实现。
关于java - 寻找矩阵上最短路径的问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27868185/