2

さまざまな検索手法を使用して解決する問題が割り当てられました。この問題は、 Escape From Zurgの問題やBridge and Torchの問題と非常によく似ています。私の問題は、データをツリーとして表現する方法がわからないことです。

これは私の推測ですが、検索してもあまり意味がありません。

グラフ

別の方法は、歩行時間でソートされた二分木を使用することです。ただし、検索アルゴリズムは必ずしもバイナリ ツリーを必要としないため、この問題に正しく取り組んでいるかどうかはまだわかりません。

このデータを表現するためのヒントをいただければ幸いです。

4

2 に答える 2

1

一般に、ツリー検索を使用して問題を解決する場合、各ノードは世界の可能な「状態」(橋のどちら側に誰がいるかなど) を表し、各ノードの子はすべての可能な「後続の状態」を表します。 (以前の状態から 1 回の移動で到達できる新しい状態)。深さ優先検索は、行き止まりになるまで 1 つのオプションを試してから、別のオプションが利用可能だった最後の状態に戻ってそれを試すことを表します。幅優先探索は、多くのオプションを並行して試し、最初のオプションがいつゴール ノードを見つけるかを確認することを表します。

これをエンコードする実際の方法に関しては、これを多方向ツリーとして表現します。各ノードには、おそらく現在の状態と、子ノードへのポインターのリストが含まれます。

お役に立てれば！

于 2012-02-01T20:50:46.507 に答える
1

次のようなものを使用できます。

public class Node
{
   public int root;
   public List<Node> neighbours;
   public Node(int x)
   {
       root=x;
   }
   public void setNeighboursList(List<Node> l)
   {
       neighbours = l;
   }
   public void addNeighbour(Node n)
   {
       if(neighbours==null) neighbours = new ArrayList<Node>();
       neighbours.add(n);
   }
   ...
} 

public class Tree
{
    public Node root;
    ....
}
于 2012-02-02T13:54:17.083 に答える