我写了一个算法来找到两点之间所有可能的路径。我用 c#.net 和 java 编写了算法。该算法产生大约 40,000 条可能的路径。令我惊讶的是，C#.net 中的算法只需要 13 分钟即可完成（在 i3 处理器中），而 java 甚至在 4 小时内都无法完成。
java中的递归可能很慢，但我不这么认为。
我有什么遗漏吗？
好的，这是要求，迷宫是一个包含数字 0、1、2 和 3 的二维数组。0 表示可步行点，1 表示障碍物，2 表示起点，3 表示出口点。该程序是通过仅触摸一次所有 0 来找到从点 2 到 3 的所有路径。我们不能跨过 1s，因为它们是障碍物。
这是 C#.Net 中的代码
public class Maze
{
//Represents each point in the Maze.
private class Node
{
private int val;
public Node(int num)
{
val = num;
switch (num)
{
case 1: IsPit = true;
break;
case 2: IsEntranceNode = true;
break;
case 3:
IsExitNode = true;
break;
}
}
public string Name { get; set; }
public bool IsPit { get; private set; }
public bool IsVisited { get; set; }
public bool IsExitNode { get; private set; }
public bool IsEntranceNode { get; private set; }
public Node UpNode { get; set; }
public Node DownNode { get; set; }
public Node LeftNode { get; set; }
public Node RightNode { get; set; }
}
#endregion
//Number of pits in the maze.
private int numberOfPits;
//Stack traces the path traversed.
private Stack<String> pathTraversed;
//Represents the maze.All Nodes are wired to its adjacent nodes.
private Node[,] Maze { get; set; }
//Number of paths found.
private int pathCount = 1;
//displays a set.
static void printSet(int[,] set)
{
Console.Write(" \t");
for (var i = 0; i < set.GetLength(1); i++)
Console.Write(i + " ");
Console.WriteLine("\n--------------------------");
for (var i = 0; i < set.GetLength(0); i++)
{
Console.Write((char)(65 + i) + " | \t");
for (var j = 0; j < set.GetLength(1); j++)
Console.Write(set[i, j] + " ");
Console.WriteLine();
}
}
static void Main(string[] args)
{
int[,] set2 = new int[7, 7] { { 2, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 3, 1, 1 }
};
Console.WriteLine("\n\nSet 2");
Console.WriteLine("=====");
printSet(set2);
Console.WriteLine("\nPath found");
Console.WriteLine("==========");
startTime = DateTime.Now;
new Maze().AddPoints(set2).FindPaths();
endTime = DateTime.Now;
difference = endTime.Subtract(startTime).TotalMinutes;
Console.WriteLine("Time taken in mins : " + difference);
Console.WriteLine("\nPress any key to exit");
Console.ReadKey();
}
//Adds points to the maze.Transforms a matrix to 2 dimensional connected nodes.
public Program AddPoints(int[,] matrix)
{
Maze = new Node[matrix.GetLength(0), matrix.GetLength(1)];
for (int i = 0; i < matrix.GetLength(0); i++)
{
for (var j = 0; j < matrix.GetLength(1); j++)
{
Node node = Maze[i, j];
if (node == null)
{
node = new Node(matrix[i, j]);
Maze[i, j] = node;
}
if (!(i - 1 < 0))
Maze[i - 1, j].DownNode = node;
if (!(i + 1 > matrix.GetLength(0) - 1))
{
var downNode = Maze[i + 1, j];
if (downNode == null)
Maze[i + 1, j] = new Node(matrix[i + 1, j]);
Maze[i + 1, j].UpNode = node;
}
if (!(j - 1 < 0))
Maze[i, j - 1].RightNode = node;
if (!(j + 1 > matrix.GetLength(1) - 1))
{
var leftNode = Maze[i, j + 1];
if (leftNode == null)
Maze[i, j + 1] = new Node(matrix[i, j + 1]);
Maze[i, j + 1].LeftNode = node;
}
node.Name = ((char)(65 + i)).ToString() + j.ToString();
if (node.IsPit)
numberOfPits++;
}
}
return this;
}
//Finds path between the start node and end node.
public void FindPaths()
{
var startNode = Maze[0, 0];
if (!startNode.IsEntranceNode)
throw new Exception("Node is not starting node.");
pathTraversed = new Stack<string>();
pathTraversed.Push(startNode.Name);
Traverse(startNode.RightNode);
Traverse(startNode.DownNode);
Traverse(startNode.LeftNode);
Traverse(startNode.UpNode);
}
//Traverses a node.
private void Traverse(Node node)
{
if (node == null)
return;
if (node.IsEntranceNode || node.IsPit || node.IsVisited)
return;
if (node.IsExitNode)
{
pathTraversed.Push(node.Name);
if (pathTraversed.Count == Maze.Length - numberOfPits)
{
var msg = "Path " + pathCount++ + " : " + string.Join("->", pathTraversed.Reverse());
Console.WriteLine(msg);
}
pathTraversed.Pop();
return;
}
pathTraversed.Push(node.Name);
node.IsVisited = true;
Traverse(node.RightNode); //
Traverse(node.DownNode); // Move to Next Node
Traverse(node.LeftNode); //
Traverse(node.UpNode); //
if (node.Name != pathTraversed.Peek())
throw new Exception("Error in Logic.");
node.IsVisited = false;
pathTraversed.Pop();
}
}
这是Java程序
public class PathFinder
{
public static void main(String[] args){
int[][] set1 = new int[][] { { 2, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 3, 1, 1 }};
ObservableStack<String> observableStack = new ObservableStack<String>();
StackObserver stackObserver = new StackObserver(plotter);
Maze maze = new Maze(set1,(IPathFinderStack<String>)observableStack);
maze.findPaths();
}
}
public class Maze {
private Node[][] nodes;
IPathFinderStack<String> pathTraversed;
private int numberOfPits = 0;
private int result = 0;
public Node[][] getVector(){
return nodes;
}
public Maze(int[][] matrix ,IPathFinderStack<String> stack){
pathTraversed = stack;
addNodes(matrix);
}
public void addNodes(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
nodes = new Node[rows][cols];
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
Node node = nodes[i][j];
if (node == null){
node = new Node(matrix[i][j]);
nodes[i][j] = node;
}
if (!(i - 1 < 0))
nodes[i-1][j].setDownNode(node);
if (!((i + 1) > rows - 1))
{
Node downNode = nodes[i+1][j];
if (downNode == null)
nodes[i + 1][j] = new Node(matrix[i+1][j]);
nodes[i + 1][j].setUpNode(node);
}
if (!(j - 1 < 0))
nodes[i][j-1].setRightNode(node);
if (!(j + 1 > cols - 1)){
Node leftNode = nodes[i][j+1];
if (leftNode == null)
nodes[i][j+1] = new Node(matrix[i][j+1]);
nodes[i][j+1].setLeftNode(node);
}
String name = new String(new char[] {(char) (65 + i), (char)(48 + j)});
node.setName(name);
if (node.isPit())
this.numberOfPits ++;
}
}
}
public void findPaths(){
Node startNode = nodes[0][0];
pathTraversed.push(startNode.getName());
Traverse(startNode.getRightNode());
Traverse(startNode.getDownNode());
Traverse(startNode.getLeftNode());
Traverse(startNode.getUpNode());
}
private void Traverse(Node node){
if (node == null)
return ;
if (node.isEntrance() || node.isVisited() || node.isPit())
return ;
if (node.isExit()){
pathTraversed.push(node.getName());
if (pathTraversed.getLength() == (nodes[0].length * nodes.length) - numberOfPits){
String msg = "Path found" + (++result);
Logger.Log(msg);
Logger.Log(pathTraversed.toString());
}
pathTraversed.pop();
return;
}
pathTraversed.push(node.getName());
node.setVisited(true);
Traverse(node.getRightNode());
Traverse(node.getDownNode());
Traverse(node.getLeftNode());
Traverse(node.getUpNode());
node.setVisited(false);
pathTraversed.pop();
}
}
public class Node
{
private String name;
private int val;
private boolean isPit;
private boolean isVisited;
private boolean isEntrance;
private boolean isExit;
private Node downNode;
private Node upNode;
private Node leftNode;
private Node rightNode;
public Node(int val){
this.val = val;
this.isPit = (val == 1);
this.isEntrance = (val == 2);
this.isExit = (val == 3);
this.isVisited = false;
}
public String getName(){
return this.name;
}
public void setName (String name) {
this.name = name;
}
public boolean isPit(){
return isPit;
}
public boolean isVisited(){
return isVisited;
}
public void setVisited(boolean isVisited) {
this.isVisited = isVisited;
}
public boolean isEntrance(){
return isEntrance;
}
public boolean isExit(){
return isExit;
}
public Node getDownNode(){
return downNode;
}
public void setDownNode(Node node){
downNode = node;
}
public Node getUpNode(){
return upNode;
}
public void setUpNode(Node node){
upNode = node;
}
public Node getLeftNode(){
return leftNode;
}
public void setLeftNode(Node node){
leftNode = node;
}
public Node getRightNode(){
return rightNode;
}
public void setRightNode(Node node) {
rightNode = node;
}
}
ObservableStack 是由数组组成的普通堆栈。我使它可以观察到将它连接到小程序以动画遍历。
我希望我已经提供了足够的细节。