深度优先搜索多个解决方案
Depth first Search more than one solution
我有这个表示为无向图的迷宫。
它是这样的：
11 3
2 3
0 3
1 4
5 4
5 7
6 7
7 8
8 9
9 10
6 11
7 11
在这张图中，使用深度优先搜索，它向我展示了从起始节点到目标节点的解决方案。我作为起始节点的输入是 0，我的目标节点是 1。作为目标路径，我得到的解决方案是 0-3-11-7-5-4-1，但如果您再次分析，还有另一个解决方案是 0-3-11-6-7-5-4-1。我在这里的目的不是展示最佳解决方案，而是展示他们有多少解决方案，然后分析最佳解决方案。
我遇到的困难是我无法打印多个解决方案。它只打印 0-3-11-7-5-4-1 没有别的，有时这个 0-3-11-6-7-5-4-1 因为我期望有两个要打印。这是我到目前为止完成的代码：
public class DepthFirstSearch {
private final boolean[] visited;
private final int sourceNode;
private final int[] pathTo;
/**
*
* @param mazeGraph
* @param sourceNode
* @param goal
*/
public DepthFirstSearch(MazeGraph mazeGraph, int sourceNode, int goal) {
this.sourceNode = sourceNode;
visited = new boolean[mazeGraph.node];
pathTo = new int[mazeGraph.node];
performRecursiveDFS(mazeGraph, sourceNode, goal);
}
//Perform recursive depth-first search
private void performRecursiveDFS(MazeGraph mazeGraph, int node, int goal) {
visited[node] = true;
for (int arc : mazeGraph.getAdjacencyList(node)) {
if (!visited[arc]) {
pathTo[arc] = node;
performRecursiveDFS(mazeGraph, arc, goal);
}
}
}
//Put path to goal in the stack
public Stack<Integer> pathTo(int toGoalNode) {
if (!visited[toGoalNode]) {
return null;
}
Stack<Integer> pathStack = new Stack<Integer>();
for (int pathToGoalNode = toGoalNode; pathToGoalNode != sourceNode; pathToGoalNode = pathTo[pathToGoalNode]) {
pathStack.push(pathToGoalNode);
}
pathStack.push(sourceNode);
reverseStack(pathStack);
return pathStack;
}
//Reverse the stack
public void reverseStack(Stack<Integer> stackToBeReverse) {
if (stackToBeReverse.isEmpty()) {
return;
}
int bottom = popBottomStack(stackToBeReverse);
reverseStack(stackToBeReverse);
stackToBeReverse.push(bottom);
}
//Pop the bottom of the stack
private int popBottomStack(Stack<Integer> stackToBeReverse) {
int popTopStack = stackToBeReverse.pop();
if (stackToBeReverse.isEmpty()) {
return popTopStack;
} else {
int bottomStack = popBottomStack(stackToBeReverse);
stackToBeReverse.push(popTopStack);
return bottomStack;
}
}
//Print the path to goal
public void printPath( int toGoal) {
if (visited[toGoal]) {
out.println("Path to Goal: ");
for (int x : pathTo(toGoal)) {
if (x == toGoal) {
out.print(x);
} else {
out.print(x + " - ");
}
}
out.println();
}
}
/**
*
* @param args
*/
public static void main(String[] args) {
Scanner scanFile = new Scanner(in);
out.print("Enter maze file: ");
String file = scanFile.nextLine();
out.print("Enter start node: ");
int startNode = scanFile.nextInt();
out.print("Enter goal node: ");
int goalNode = scanFile.nextInt();
MazeGraph mazeGraph = new MazeGraph(file);
mazeGraph.print();
out.println("Starting at 0\nGoal at 1");
DepthFirstSearch depthFirstSearch = new DepthFirstSearch(mazeGraph, startNode, goalNode);
depthFirstSearch.printPath( goalNode);
}
}
迷宫图源代码：
public class MazeGraph {
final int node; //Declaring constant value of a node.
int arc;
List<Integer>[] adjacencyList;
final static Set<Integer> setOfNodes = new HashSet<Integer>();
/**
* This constructors takes an integer parameter for reading node indexes in
* a list of adjacent nodes.
*
* @param node - integer parameter for passing the nodes value from the file
* and create a list of adjacent nodes.
*/
MazeGraph(int node) {
this.node = node;
this.arc = 0;
adjacencyList = (List<Integer>[]) new List[node];
for (int index = 0; index < node; index++) {
adjacencyList[index] = new LinkedList<Integer>();
}
}
/**
* The main constructor that takes a String for reading maze file.
*
* @param mazeFile
*/
public MazeGraph(String mazeFile) {
this(getNodeSize(mazeFile));
Scanner scan;
try {
//Scan maze file.
scan = new Scanner(new File(mazeFile));
/*loop when it has next integer then read two nodes from the file and add arc for it.*/
while (scan.hasNextInt()) {
int node1 = scan.nextInt();
int node2 = scan.nextInt();
addArc(node1, node2);
}
} catch (FileNotFoundException ex) {
out.println("File not found.");
}
}
/**
* This method returns a size of the set of nodes by taking a String
* parameter which the name of the maze file.
*
* @param mazeFile - String parameter for reading maze file for scanning the
* size of the nodes.
* @return - returns an integer value for the size of the set of nodes.
*/
public static int getNodeSize(String mazeFile) {
Scanner scanNodeSize;
try {
scanNodeSize = new Scanner(new File(mazeFile));
while (scanNodeSize.hasNextInt()) {
int node1 = scanNodeSize.nextInt();
int node2 = scanNodeSize.nextInt();
setOfNodes.add(node1);
setOfNodes.add(node2);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
return setOfNodes.size();
}
/**
* This method adds an arc by adding two different nodes in array of list
* called adjacency list.
*
* @param node1 - first node.
* @param node2 - next node.
*/
private void addArc(int node1, int node2) {
arc++; //Increase arc by one whenever this addArc method is called.
adjacencyList[node1].add(node2);
adjacencyList[node2].add(node1);
}
/**
* Print the nodes and its arcs by looping through the adjacency list.
*/
public void print() {
out.println(node + " Nodes, " + arc + " Arcs \n");
for (int n = 0; n < node; n++) {
out.print(n + " connected to ");
for (int w : adjacencyList[n]) {
out.print(w + " ");
}
out.println();
}
}
/**
* This method returns a list of nodes to allow objects to be the target for
* "for-each" statement.
*
* @param nodes - an Integer parameter for getting the number of nodes in a
* list.
* @return - returns a list of nodes.
*/
public Iterable<Integer> getAdjacencyList(int nodes) {
return adjacencyList[nodes];
}
/**
* Unit testing To test if it reads the file.
*
* @param args
*/
public static void main(String[] args) {
out.print("Enter maze file: ");
Scanner scanFile = new Scanner(in);
String file = scanFile.nextLine();
MazeGraph G = new MazeGraph(file);
G.print();
}
}
请详细解释为什么会发生这种情况，并告诉我 suggestions/advise 我该如何改进。如果没问题，也检查我的代码质量，否则不检查也可以。无论如何提前致谢。
您的算法找到一条路径实际上是幸运的，因为它有一个主要缺陷：如果您离开递归调用，您不会取消设置 visited。所以你必须把这个添加到你的 performRecursiveDFS:
private void performRecursiveDFS(MazeGraph mazeGraph, int node, int goal) {
visited[node] = true; //set visited
for (int arc : mazeGraph.getAdjacencyList(node)) {
if (!visited[arc]) {
pathTo[arc] = node;
performRecursiveDFS(mazeGraph, arc, goal);
}
}
visited[node] = false; //unset visited
}
这是必要的，因为你“回溯”你正在寻找另一条路径，而对于那条路径，你还没有访问过node。
另外在递归调用中，可以检查是否达到目标，如果是，则打印路径：
private void performRecursiveDFS(MazeGraph mazeGraph, int node, int goal) {
visited[node] = true; //set visited
if(node == goal) { //found the goal? Good, print it and backtrack.
printPath(goal);
} else {
for (int arc : mazeGraph.getAdjacencyList(node)) {
if (!visited[arc]) {
pathTo[arc] = node;
performRecursiveDFS(mazeGraph, arc, goal);
}
}
}
visited[node] = false; //unset visited
}
除了打印路径，你当然可以做一些其他的事情，比如计数，将路径存储在列表中等
编辑：使用您提供的迷宫文件对其进行测试，我得到：
$ java DepthFirstSearch
Enter maze file: maze
Enter start node: 0
Enter goal node: 1
12 Nodes, 12 Arcs
0 connected to 3
1 connected to 4
2 connected to 3
3 connected to 11 2 0
4 connected to 1 5
5 connected to 4 7
6 connected to 7 11
7 connected to 5 6 8 11
8 connected to 7 9
9 connected to 8 10
10 connected to 9
11 connected to 3 6 7
Starting at 0
Goal at 1
Path to Goal:
0 - 3 - 11 - 6 - 7 - 5 - 4 - 1
Path to Goal:
0 - 3 - 11 - 7 - 5 - 4 - 1
我有这个表示为无向图的迷宫。 它是这样的：
11 3
2 3
0 3
1 4
5 4
5 7
6 7
7 8
8 9
9 10
6 11
7 11
在这张图中，使用深度优先搜索，它向我展示了从起始节点到目标节点的解决方案。我作为起始节点的输入是 0，我的目标节点是 1。作为目标路径，我得到的解决方案是 0-3-11-7-5-4-1，但如果您再次分析，还有另一个解决方案是 0-3-11-6-7-5-4-1。我在这里的目的不是展示最佳解决方案，而是展示他们有多少解决方案，然后分析最佳解决方案。
我遇到的困难是我无法打印多个解决方案。它只打印 0-3-11-7-5-4-1 没有别的，有时这个 0-3-11-6-7-5-4-1 因为我期望有两个要打印。这是我到目前为止完成的代码：
public class DepthFirstSearch {
private final boolean[] visited;
private final int sourceNode;
private final int[] pathTo;
/**
*
* @param mazeGraph
* @param sourceNode
* @param goal
*/
public DepthFirstSearch(MazeGraph mazeGraph, int sourceNode, int goal) {
this.sourceNode = sourceNode;
visited = new boolean[mazeGraph.node];
pathTo = new int[mazeGraph.node];
performRecursiveDFS(mazeGraph, sourceNode, goal);
}
//Perform recursive depth-first search
private void performRecursiveDFS(MazeGraph mazeGraph, int node, int goal) {
visited[node] = true;
for (int arc : mazeGraph.getAdjacencyList(node)) {
if (!visited[arc]) {
pathTo[arc] = node;
performRecursiveDFS(mazeGraph, arc, goal);
}
}
}
//Put path to goal in the stack
public Stack<Integer> pathTo(int toGoalNode) {
if (!visited[toGoalNode]) {
return null;
}
Stack<Integer> pathStack = new Stack<Integer>();
for (int pathToGoalNode = toGoalNode; pathToGoalNode != sourceNode; pathToGoalNode = pathTo[pathToGoalNode]) {
pathStack.push(pathToGoalNode);
}
pathStack.push(sourceNode);
reverseStack(pathStack);
return pathStack;
}
//Reverse the stack
public void reverseStack(Stack<Integer> stackToBeReverse) {
if (stackToBeReverse.isEmpty()) {
return;
}
int bottom = popBottomStack(stackToBeReverse);
reverseStack(stackToBeReverse);
stackToBeReverse.push(bottom);
}
//Pop the bottom of the stack
private int popBottomStack(Stack<Integer> stackToBeReverse) {
int popTopStack = stackToBeReverse.pop();
if (stackToBeReverse.isEmpty()) {
return popTopStack;
} else {
int bottomStack = popBottomStack(stackToBeReverse);
stackToBeReverse.push(popTopStack);
return bottomStack;
}
}
//Print the path to goal
public void printPath( int toGoal) {
if (visited[toGoal]) {
out.println("Path to Goal: ");
for (int x : pathTo(toGoal)) {
if (x == toGoal) {
out.print(x);
} else {
out.print(x + " - ");
}
}
out.println();
}
}
/**
*
* @param args
*/
public static void main(String[] args) {
Scanner scanFile = new Scanner(in);
out.print("Enter maze file: ");
String file = scanFile.nextLine();
out.print("Enter start node: ");
int startNode = scanFile.nextInt();
out.print("Enter goal node: ");
int goalNode = scanFile.nextInt();
MazeGraph mazeGraph = new MazeGraph(file);
mazeGraph.print();
out.println("Starting at 0\nGoal at 1");
DepthFirstSearch depthFirstSearch = new DepthFirstSearch(mazeGraph, startNode, goalNode);
depthFirstSearch.printPath( goalNode);
}
}
迷宫图源代码：
public class MazeGraph {
final int node; //Declaring constant value of a node.
int arc;
List<Integer>[] adjacencyList;
final static Set<Integer> setOfNodes = new HashSet<Integer>();
/**
* This constructors takes an integer parameter for reading node indexes in
* a list of adjacent nodes.
*
* @param node - integer parameter for passing the nodes value from the file
* and create a list of adjacent nodes.
*/
MazeGraph(int node) {
this.node = node;
this.arc = 0;
adjacencyList = (List<Integer>[]) new List[node];
for (int index = 0; index < node; index++) {
adjacencyList[index] = new LinkedList<Integer>();
}
}
/**
* The main constructor that takes a String for reading maze file.
*
* @param mazeFile
*/
public MazeGraph(String mazeFile) {
this(getNodeSize(mazeFile));
Scanner scan;
try {
//Scan maze file.
scan = new Scanner(new File(mazeFile));
/*loop when it has next integer then read two nodes from the file and add arc for it.*/
while (scan.hasNextInt()) {
int node1 = scan.nextInt();
int node2 = scan.nextInt();
addArc(node1, node2);
}
} catch (FileNotFoundException ex) {
out.println("File not found.");
}
}
/**
* This method returns a size of the set of nodes by taking a String
* parameter which the name of the maze file.
*
* @param mazeFile - String parameter for reading maze file for scanning the
* size of the nodes.
* @return - returns an integer value for the size of the set of nodes.
*/
public static int getNodeSize(String mazeFile) {
Scanner scanNodeSize;
try {
scanNodeSize = new Scanner(new File(mazeFile));
while (scanNodeSize.hasNextInt()) {
int node1 = scanNodeSize.nextInt();
int node2 = scanNodeSize.nextInt();
setOfNodes.add(node1);
setOfNodes.add(node2);
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
return setOfNodes.size();
}
/**
* This method adds an arc by adding two different nodes in array of list
* called adjacency list.
*
* @param node1 - first node.
* @param node2 - next node.
*/
private void addArc(int node1, int node2) {
arc++; //Increase arc by one whenever this addArc method is called.
adjacencyList[node1].add(node2);
adjacencyList[node2].add(node1);
}
/**
* Print the nodes and its arcs by looping through the adjacency list.
*/
public void print() {
out.println(node + " Nodes, " + arc + " Arcs \n");
for (int n = 0; n < node; n++) {
out.print(n + " connected to ");
for (int w : adjacencyList[n]) {
out.print(w + " ");
}
out.println();
}
}
/**
* This method returns a list of nodes to allow objects to be the target for
* "for-each" statement.
*
* @param nodes - an Integer parameter for getting the number of nodes in a
* list.
* @return - returns a list of nodes.
*/
public Iterable<Integer> getAdjacencyList(int nodes) {
return adjacencyList[nodes];
}
/**
* Unit testing To test if it reads the file.
*
* @param args
*/
public static void main(String[] args) {
out.print("Enter maze file: ");
Scanner scanFile = new Scanner(in);
String file = scanFile.nextLine();
MazeGraph G = new MazeGraph(file);
G.print();
}
}
请详细解释为什么会发生这种情况，并告诉我 suggestions/advise 我该如何改进。如果没问题，也检查我的代码质量，否则不检查也可以。无论如何提前致谢。
您的算法找到一条路径实际上是幸运的，因为它有一个主要缺陷：如果您离开递归调用，您不会取消设置 visited。所以你必须把这个添加到你的 performRecursiveDFS:
private void performRecursiveDFS(MazeGraph mazeGraph, int node, int goal) {
visited[node] = true; //set visited
for (int arc : mazeGraph.getAdjacencyList(node)) {
if (!visited[arc]) {
pathTo[arc] = node;
performRecursiveDFS(mazeGraph, arc, goal);
}
}
visited[node] = false; //unset visited
}
这是必要的，因为你“回溯”你正在寻找另一条路径，而对于那条路径，你还没有访问过node。
另外在递归调用中，可以检查是否达到目标，如果是，则打印路径：
private void performRecursiveDFS(MazeGraph mazeGraph, int node, int goal) {
visited[node] = true; //set visited
if(node == goal) { //found the goal? Good, print it and backtrack.
printPath(goal);
} else {
for (int arc : mazeGraph.getAdjacencyList(node)) {
if (!visited[arc]) {
pathTo[arc] = node;
performRecursiveDFS(mazeGraph, arc, goal);
}
}
}
visited[node] = false; //unset visited
}
除了打印路径，你当然可以做一些其他的事情，比如计数，将路径存储在列表中等
编辑：使用您提供的迷宫文件对其进行测试，我得到：
$ java DepthFirstSearch
Enter maze file: maze
Enter start node: 0
Enter goal node: 1
12 Nodes, 12 Arcs
0 connected to 3
1 connected to 4
2 connected to 3
3 connected to 11 2 0
4 connected to 1 5
5 connected to 4 7
6 connected to 7 11
7 connected to 5 6 8 11
8 connected to 7 9
9 connected to 8 10
10 connected to 9
11 connected to 3 6 7
Starting at 0
Goal at 1
Path to Goal:
0 - 3 - 11 - 6 - 7 - 5 - 4 - 1
Path to Goal:
0 - 3 - 11 - 7 - 5 - 4 - 1