連続ですみませんがもう一問お願いします。
以下は探索プログラムの一例である。
（元の問題文が英語で、エキサイト翻訳で和訳にしています）
幅優先探索の例
図：http://
アルゴリズム解説：http://
参照ソースコード：http://
深さ優先探索の例
図：http://
アルゴリズム解説：http://
参照ソースコード：http://
プログラム作成の手順
1.Nodeクラスの作成：http://
2.木かグラフのコンストラクタを作る：http://
3.探索プログラム
幅優先探索プログラム：http://
★深さ優先探索プログラム：http://
4.メインメソッド：http://
出力サンプル
幅優先探索プログラム：http://
深さ優先探索プログラム：http://
以上において、★の深さ優先探索プログラムのソースコードを完成させよ、というのが問題です。
長くなってしまってすみませんが、よろしくお願いします。
以下は探索プログラムの一例である。
（元の問題文が英語で、エキサイト翻訳で和訳にしています）
幅優先探索の例
図：http://
アルゴリズム解説：http://
参照ソースコード：http://
深さ優先探索の例
図：http://
アルゴリズム解説：http://
参照ソースコード：http://
プログラム作成の手順
1.Nodeクラスの作成：http://
2.木かグラフのコンストラクタを作る：http://
3.探索プログラム
幅優先探索プログラム：http://
★深さ優先探索プログラム：http://
4.メインメソッド：http://
出力サンプル
幅優先探索プログラム：http://
深さ優先探索プログラム：http://
以上において、★の深さ優先探索プログラムのソースコードを完成させよ、というのが問題です。
長くなってしまってすみませんが、よろしくお願いします。
|
|
|
|
コメント(4)
すみません、それでは原文のアルゴリズムを貼ります。
幅優先探索プログラムのアルゴリズム
The breadth-first search algorithm searches a state space by constructing a hierarchical tree structure consisting of a set of nodes and links. The algorithm defines a way to move through the tree structure, examining the value at nodes. From the start, it looks at each node one edge away. Then it moves out from those nodes to all two edges away from the start. This continues until either the goal node is found or the entire tree is searched.
The algorithm follows:
1.Create a queue and add the first node to it.
2.Loop:
If the queue is empty, quit.
Remove the first node from the queue.
If the node contains the goal state, then exit with the node as the solution.
For each child of the current node: add the new state to the back of the queue.
深さ優先探索プログラム
The depth-first algorithm follows a single branch of the tree down as many levels as possible until we either reach a solution or a dead end. It searches from the start or root node all the way down to a leaf node. If it does not find the goal node, it backtracks up the tree and searches down the next untested path until it reaches the next leaf.
The algorithm follows:
1.Create a queue and add the first node to it.
2.Loop:
If the queue is empty, quit.
Remove the first node from the queue.
If the node contains the goal state, then exit with the node as the solution.
For each child of the current node: add the new state to the front of the queue.
以上です。よろしくお願いします。
幅優先探索プログラムのアルゴリズム
The breadth-first search algorithm searches a state space by constructing a hierarchical tree structure consisting of a set of nodes and links. The algorithm defines a way to move through the tree structure, examining the value at nodes. From the start, it looks at each node one edge away. Then it moves out from those nodes to all two edges away from the start. This continues until either the goal node is found or the entire tree is searched.
The algorithm follows:
1.Create a queue and add the first node to it.
2.Loop:
If the queue is empty, quit.
Remove the first node from the queue.
If the node contains the goal state, then exit with the node as the solution.
For each child of the current node: add the new state to the back of the queue.
深さ優先探索プログラム
The depth-first algorithm follows a single branch of the tree down as many levels as possible until we either reach a solution or a dead end. It searches from the start or root node all the way down to a leaf node. If it does not find the goal node, it backtracks up the tree and searches down the next untested path until it reaches the next leaf.
The algorithm follows:
1.Create a queue and add the first node to it.
2.Loop:
If the queue is empty, quit.
Remove the first node from the queue.
If the node contains the goal state, then exit with the node as the solution.
For each child of the current node: add the new state to the front of the queue.
以上です。よろしくお願いします。
できました。出力結果もサンプルと一致します。
public void depthFirst() {
Vector open = new Vector();
open.addElement(node[0]);
Vector closed = new Vector();
boolean success = false;
int step = 0;
for (;;) {
System.out.println("STEP:" + (step++));
System.out.println("OPEN:" + open.toString());
System.out.println("closed:" + closed.toString());
if (open.size() == 0) {// openは空か？
success = false;
break;
} else {
Node node = (Node) open.elementAt(0);
open.removeElementAt(0);
if (node == goal) {
success = true;
break;
} else {
Vector children = node.getChildren();
closed.addElement(node);
for (int i = children.size() - 1; i >= 0; i--) {
// for(int i = 0 ; i < children.size() ; i++){
Node m = (Node) children.elementAt(i);
if (!open.contains(m) && !closed.contains(m)) {
m.setPointer(node);
open.insertElementAt(m, 0);
if (m == goal) {
success = true;
break;
}
}
}
}
}
}
if (success) {
System.out.println("*** Solution ***");
printSolution(goal);
}
}
public void depthFirst() {
Vector open = new Vector();
open.addElement(node[0]);
Vector closed = new Vector();
boolean success = false;
int step = 0;
for (;;) {
System.out.println("STEP:" + (step++));
System.out.println("OPEN:" + open.toString());
System.out.println("closed:" + closed.toString());
if (open.size() == 0) {// openは空か？
success = false;
break;
} else {
Node node = (Node) open.elementAt(0);
open.removeElementAt(0);
if (node == goal) {
success = true;
break;
} else {
Vector children = node.getChildren();
closed.addElement(node);
for (int i = children.size() - 1; i >= 0; i--) {
// for(int i = 0 ; i < children.size() ; i++){
Node m = (Node) children.elementAt(i);
if (!open.contains(m) && !closed.contains(m)) {
m.setPointer(node);
open.insertElementAt(m, 0);
if (m == goal) {
success = true;
break;
}
}
}
}
}
}
if (success) {
System.out.println("*** Solution ***");
printSolution(goal);
}
}
- mixiユーザー
- ログインしてコメントしよう！
|
|
|
|
Javaの課題丸投げ 更新情報
Javaの課題丸投げのメンバーはこんなコミュニティにも参加しています
人気コミュニティランキング
- 1位
- 十二国記
- 23166人
- 2位
- 楽天イーグルス
- 31952人
- 3位
- 北海道日本ハムファイターズ
- 28124人