3

Javaで解決すべき問題があります。横断する必要があるツリーがあります。ここにあります：

        1
     /     \
   1 2 3  1 2 3      
 /   |  \    \
123 123 123  same for those three nodes

ここでトラバースする必要がある方法は、ルートから開始し、最も左端のノード (ここでは 1) とその左端のリーフ (1) を実行することです。その後、すべての数字をトレースするルートから再び開始し、今度は同じ最左端のノードの次の葉に到達する必要があります..など、上から始まり、残りのすべての葉に1つずつ到達するたびにそのノード。左端のノードのすべてのリーフがトレースされた後、通常どおりに (上から開始して) 次の招待されていないノード (ここでは 2) に移動し、すべてのツリーについて同様に続きます。したがって、最初の 6 つのトレースは次のようになります。

111 112 113 121 122 123 ...など

トレースされた数字はすべて、上記の方法で順番にトレースして記録する必要があります。誰でもそれを達成する方法についてアルゴリズムを手伝うことができますか?. ありがとう。

4

2 に答える 2

4

必要なのは、ツリー トラバーサル アルゴリズムです。

void traverse(Node root, String path) {
    path += root.getValue();
    for (Node child : root.getChildren())
        traverse(child, path);

    // end of current traversal
    if (root.getChildren().isEmpty())
        System.out.print(path + " ");
}
于 2012-04-29T12:38:53.700 に答える
1

あなたが説明していることは、深さ優先探索として知られています。これは仕事にとって最も効率的なアルゴリズムではないことを知っておく必要があります。ダイクストラのようなより良いものがあります。

何をしようとしているのかに応じて、アルファベータプルーニングやゲームプレイ検索用の他のヒューリスティックなど、さらに特殊な戦術を採用できます。

深さ優先探索を使用するように設定されていて、ルートからそのノードへのパスを返したい場合は、目標ノードが見つかったら、次のようなものを使用できます。nodeあなたのゴールノードであると仮定して...

List<Node> path = new ArrayList<Node>();
path.add(node);
while(node.parent != null){
  path.add(node.parent);
  node = node.parent;
}
return path; //returns a path from {goal,...,root}
于 2012-04-29T12:15:29.843 に答える