6

3 人の人食い人種と 3 人の宣教師が川を渡らなければなりません。彼らのボートは二人しか乗れません。人食い人種の数が宣​​教師の数を上回っている場合、川のどちらかの側で、宣教師は困っています (結果については説明しません)。各宣教師と各人食い人種がボートを漕ぐことができます。6 人全員が川を渡るにはどうすればよいでしょうか。

IDDFS (反復深化深さ優先検索) と GreedyBFS (貪欲な最良優先検索) を使用してこの問題を解決するためのアルゴリズムが見つかりません。これを解決する方法についてのアイデアも私を幸せにします。

編集:

ウィキでIDDFSのアルゴリズムを見つけました：

IDDFS(root, goal)
{
  depth = 0
  repeat
  {
    result = DLS(root, goal, depth)
    if (result is a solution)
      return result
    depth = depth + 1
  }
}


DLS(node, goal, depth) 
{
  if (depth == 0 and node == goal)
    return node
  else if (depth > 0)
    for each child in expand(node)
      DLS(child, goal, depth-1)
  else
    return no-solution
}

しかし、私の問題で DLS() の expand(node) が何を達成することになっているのかわかりません。これは私のノードクラスです:

public class Node{
    //x-no of missionaries
    //y-no of cannibals
    //z-position of boat
    int x,y;
    boolean z;
    Node(int x,int y,boolean z){
        this.x=x;
        this.y=y;
        this.z=z;
    }
    public int getM(){
        return this.x;
    }
    public int getC(){
        return this.y;
    }
    public boolean getB(){
        return this.z;
    }
    public void setM(int x){
        this.x=x;
    }
    public void setC(int y){
        this.y=y;
    }
    public void setB(boolean z){
        this.z=z;
    }

}

助けていただければ幸いです。

4

2 に答える 2

4

アルゴリズムなしでそれを解決する方法は？モデルは小さく、プログラミングなしで解決できます。最初の2つの共食いは反対側に移動し、次に1つはボートで戻って、もう1つの共食いを反対側に移動します。これで、反対側に3つの共食いがあります。そして2人の宣教師が反対側に行きます（今は2cと2mが反対側にあります）。今回cは片方mが戻ってきて（そもそも2cと2m）、また反対側に2m（反対側が3m、片方がc）、反対側のcだけが戻ってきて運びます反対側に2つのc（反対側に2cと3m）、再び1つのcが戻ってきて、最新のcを反対側に移動します。

DFSのようなアルゴリズムでそれをシミュレートする方法は？有向グラフを作成します。2^6の位置（{1,2,3,4,5,6}のすべての可能なサブセット）があり、使用可能な移動を使用してある位置から別の位置に移動できる場合、それらは互いに関連しています。一部のノードはデッドノード（片側でより多くの共食いを引き起こすノード）です。グラフからこのノードを削除し、ノード0{}からノード63{1,2に移動する方法があるかどうかを確認するタスクがあります。 、3,4,5,6}。これは、BFS、DFSなどの多くの方法で解決できます。

于 2012-03-24T11:47:46.710 に答える
4

あなたが言及したアルゴリズムを使用するために、あなたは問題の状態空間が何であるかを理解する必要があります。状態とは、問題の状況（開始状況、最終状況、または中間状況）の完全な説明です。秘訣は、状態が問題の解決策であるかどうか、そうでない場合は次に何をすべきかを判断できるように、状態に十分な情報を含めることです。あなたの場合、状態を表す1つの可能な方法は、3つの変数を使用することです。整数mは川の開始側にいる宣教師の数を示し、整数cは開始側にいる人食い人の数を示し、ブール値bボートがどちら側にあるかを示します。与えられた値（m、c、b）、実行できるアクションと、これによって発生する他の状態を判別できます。あなたが言及するアルゴリズムは、実際にはそのような接続状態のセットを検索するためのアルゴリズムです。

于 2012-03-24T11:50:57.477 に答える