BFS入門、Java迷宮問題
3737 ワード
これは実はBFSの入門級の問題で、私は初心者の姿勢で研究して、不足があれば指摘してください.
BFSの核心はqueryの先進的な先出し原則を利用することであり,本題の遡及はstackの後進的な先出し原則を用い,両データ構造に対する復習といえる.
問題を解く過程でJavaのオブジェクトレプリケーションの本質をより深く理解し、具体的には別のブログ「Javaオブジェクトレプリケーションの背後」に掲載されている.
本題は基本的なBFS原理であり,二次元配列を用いて象限を構築し,二次元boolean配列を用いてvisitedを構築し,二次元dir配列を用いて上下左右の移動を構築する.
以下はコードです
以下はノードクラス
なお、nodeには、遡及の必要性のためにprev_xとprev_yが追加されている
問題を解く過程で私は考えの上で2つのボトルネックに出会ったことがある.
1.最初はBFSのアルゴリズムではこの迷宮の問題を解決できないと思っていましたが、当時の考えでは、例えばいつも分岐点があって、それから通れるように見える道と通れない道があって、もし点をマークする方法を通じて、通れない道で通れる点をfalseとマークして、そこで通じないかもしれません.実はこの考えはよく考えてみるともしかすると、あのいわゆる通れない道に別の道を通れる点があれば、それ自体が通れるに違いないからかもしれません.今は簡単そうに見えるポイントで、当時は確かに困っていました.
2.遡及時の利用
BFSの核心はqueryの先進的な先出し原則を利用することであり,本題の遡及はstackの後進的な先出し原則を用い,両データ構造に対する復習といえる.
問題を解く過程でJavaのオブジェクトレプリケーションの本質をより深く理解し、具体的には別のブログ「Javaオブジェクトレプリケーションの背後」に掲載されている.
本題は基本的なBFS原理であり,二次元配列を用いて象限を構築し,二次元boolean配列を用いてvisitedを構築し,二次元dir配列を用いて上下左右の移動を構築する.
以下はコードです
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class solution {
public static int M = 5;
public static int N = 5;
public static void main(String args[]) {
int maze[][] = { { 0, 1, 0, 0, 0 }, { 0, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0 }, { 0, 1, 1, 1, 0 },
{ 0, 0, 0, 1, 0 } };
if (maze_path(maze))
System.out.println("The solution is showed above");
else
System.out.println("It is not feasible");
}
public static boolean maze_path(int MAZE[][]) {
int maze[][] = MAZE;
boolean visited[][] = new boolean[5][5];
Queue<Node> unvisited = new LinkedList<Node>();
Stack<Node> path = new Stack<Node>();
Node start = new Node(0, 0);
visited[0][0] = true;
Node end = new Node(4, 4);
Node cur = new Node(0, 0, 0, 0);
Node move = new Node(0, 0, 0, 0);
int dir[][] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
unvisited.offer(start);
while (!unvisited.isEmpty()) {
cur = unvisited.poll();
path.push(cur);
for (int i = 0; i < 4; i++) {
move.x = cur.x + dir[i][0];
move.y = cur.y + dir[i][1];
move.prev_x = cur.x;
move.prev_y = cur.y;
if (move.x == end.x && move.y == end.y) {
while (!path.isEmpty()) {
Node show_path = path.pop();
if (move.prev_x == show_path.x && move.prev_y == show_path.y) {
System.out.println("(" + show_path.x + ", " + show_path.y + ")");
move = show_path;
}
}
return true;
}
if (move.x >= 0 && move.x < M && move.y >= 0 && move.y < N && (maze[move.x][move.y] == 0)
&& (!visited[move.x][move.y])) {
Node new_node = new Node(move.x, move.y, move.prev_x, move.prev_y);
unvisited.offer(new_node);
visited[move.x][move.y] = true;
}
}
}
return false;
}
}
以下はノードクラス
public class Node {
public int x;
public int y;
public int prev_x;
public int prev_y;
boolean value;
public Node(int X, int Y, int PREV_X, int PREV_Y) {
this.x = X;
this.y = Y;
this.prev_x = PREV_X;
this.prev_y = PREV_Y;
}
public Node(int X, int Y) {
this.x = X;
this.y = Y;
}
}
なお、nodeには、遡及の必要性のためにprev_xとprev_yが追加されている
問題を解く過程で私は考えの上で2つのボトルネックに出会ったことがある.
1.最初はBFSのアルゴリズムではこの迷宮の問題を解決できないと思っていましたが、当時の考えでは、例えばいつも分岐点があって、それから通れるように見える道と通れない道があって、もし点をマークする方法を通じて、通れない道で通れる点をfalseとマークして、そこで通じないかもしれません.実はこの考えはよく考えてみるともしかすると、あのいわゆる通れない道に別の道を通れる点があれば、それ自体が通れるに違いないからかもしれません.今は簡単そうに見えるポイントで、当時は確かに困っていました.
2.遡及時の利用
while (!path.isEmpty()) {
Node show_path = path.pop();
if (move.prev_x == show_path.x && move.prev_y == show_path.y) {
System.out.println("(" + show_path.x + ", " + show_path.y + ")");
move = show_path;
}
}
, stack , prev , 。