我如何使用深度优先搜索来解决这个难题？ [英] How do I use depth first search to solve this puzzle?
问题描述
所以我所做的就是采取滑动拼图看起来像这样：
So what I did was take a sliding puzzle that looks like this:
1 0 3
4 2 6
7 5 8
其中0重新presents空的空间，并通过我邻接矩阵把它变成一个图形。那么，什么我想要做的就是通过图形搜索，发现这是0，然后将该值从该值开始，执行DFS，找到从0到右下角的路径时，解决的难题是这样的：
Where 0 represents the empty space and I turned it into a graph via an adjacency matrix. What I then want to do is search through the graph and find the value that's 0 and then starting from that value, perform a DFS and find a path from 0 to the bottom right corner when the solved puzzle would look like this:
1 2 3
4 5 6
7 8 0
这里的code这是应该执行DFS：
Here's the code which is supposed to perform the DFS:
public static boolean SolveNinePuzzle(int[][] B){
//first section of the code makes the adjacency matrix
int[][] G = new int[9][9];
int temp2;
int temp1;
for (int i = 0; i < 3; i++){
for (int j = 0; j < 3; j++){
getBoardFromIndex(i);
if (i < 2){
temp1 = B[i][j];
temp2 = B[i+1][j];
G[temp2][temp1] = 1;
G[temp1][temp2] = 1;
getIndexFromBoard(B);
}
if (i > 0){
temp1 = B[i][j];
temp2 = B[i-1][j];
G[temp2][temp1] = 1;
G[temp1][temp2] = 1;
getIndexFromBoard(B);
}
if (j < 2){
temp1 = B[i][j];
temp2 = B[i][j+1];
G[temp2][temp1] = 1;
G[temp1][temp2] = 1;
getIndexFromBoard(B);
}
if (j > 0){
temp1 = B[i][j];
temp2 = B[i][j-1];
G[temp2][temp1] = 1;
G[temp1][temp2] = 1;
getIndexFromBoard(B);
}
}
}
printGraph(G);
System.out.println();
//Finds out where 0 is and moves the tiles either up down or left or right depending on
int l = B.length;
int temp;
boolean isSolved = true;
printBoard(B);
int n = G.length;
int[] visited = new int[n];
int visits = 0;
int c = 0;
visited[c] = 1;
for (int k = 0; k < visited.length; k++) {
if (visited[k] == 0 && G[c][k] == 1){
visited[c] = 1;
c = k;
k = 0;
}
}
现在它应该通过所有相邻顶点。我还没有的是在黑板上交换价值的一种方式，我也没有搜索停止，当它到达右下角。基本上，我怎么能应用在与董事会的图的DFS算法。
Now it's supposed to go through all the adjacent vertices. What I don't have yet is a way to swap values on the board and I also don't have the search stop when it reaches the bottom right corner. Basically, how can I apply the DFS algorithm on the graph with the board.
推荐答案
从评论重复：
有没有事情没有DFS堆栈或BFS无队列。你给我的DFS实现使用系统堆栈，这是递归的结果，所以我们并不需要明确定义堆栈。由于任何函数调用创建一个系统堆栈（见，怎一个code执行，或当函数被调用时会发生什么），而且没有（固有）的方式来使用队列，队列将始终以实现声明BFS的
There is no thing as DFS without stacks or BFS without queues. The DFS implementation you gave uses System stack, which is result of recursion, so we don't need to define stack explicitly. Since any function call creates a system stack (See, how a code executes, or what happens when a function is called), and there is no (inherent) way to use queue, a queue will always be declared in an implementation of BFS.
现在，只要你想解决这个使用BFS，这里是我建议：
Now, as you want to solve this using BFS, here is what I recommend:
首先，创建访问状态的数组，所以，你不要让每次重复的调用。有9！它可以存储为字符串（密钥）的可能性，（布尔）值映射，它说一个板状态是否被访问或没有。
Firstly, create a array for visited states, so that, you don't make redundant calls every time. There are 9! possibilities which can be stored as string (key), (bool) value mapped, which says whether a board state is visited or not.
标记为参观了初始状态。可以有2（角），3（侧）或4（中心），其可以为每个板状态进行移动。使这些动作和队列推动这些国家中，突然跳出当前的状态（和标记访问过）。直到你得到的目标状态做到这一点。 BFS会，其本身做出一定的，如果你到达目标状态，这将是在最小的移动。
Mark the initial state as visited. There can be 2(corner), 3(side) or 4(center) moves that can be made for every board state. Make those moves and push those states in the queue, popping out the current state (and marking it visited). Do this until you get the target state. BFS will, by itself, make certain that if you reach the target state, it will be, in minimum moves.
这篇关于我如何使用深度优先搜索来解决这个难题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
