Pythonの検索アルゴリズムを使用して3つの狼と3つの羊のパズルを解決します

Question

私はこの質問を長い間考えていて、解決する方法を見つけられませんでした。

問題は、次の通りです：私たちはサイドに3つの小羊と狼3を持っているし、我々は彼らが反対側に川を通過させるために必要があり

。初めに、私はこれらの困難な状況で停止するまで、それは簡単に見えた：

• 狼は子羊がより多くまたはオオカミに等しくすることができることを意味し、子羊を超えることはできません。
• 動物を反対側に運ぶボートは2以上を運ぶことができません
• ボートは常に動物を運んでいなければなりません。つまり、空のボートを動かすことはできません。

質問は、私たちのすべては、あなたがここに入力としてグラフを提供し、そしてまで、これらのアルゴリズムは動作しないことを知っているなど*またはBFSなどの

、検索アルゴリズムによって解かなければなりません問題です。

3匹の羊と3匹の狼からグラフを作成する方法は？

私はそれについて何回も、私の心に唯一の方法がすべての可能性によって来た。私にとってはいいとは言えますが、問題はまだ同じで、それを実装する方法や、このグラフをアルゴリズムに渡すためのPythonコードとして記述するのでアルゴリズムが解決できるので、まだ進歩していません。

Answer 1

左のバンクに何匹の子羊とオオカミがいるのか、そしてそのボートにそのボートがあるかどうかを表すノードがあるとします（左の場合は「0」、右は「1」）。

最初のノードは、次のとおりです。

Node 0 : { lambs:3, wolves:3, boat:0 } 

ここからが要件を満たしている任意のノードに移動することができます。したがって、新しいノードは{boat:1}（それは反対側に行きました）を持っていなければならず、それには1つまたは2つの子羊と1つまたは2つのオオカミが必要です。

次の可能なノードは、次のとおりです。

Node 1 : { lambs:2, wolves:3, boat:1 } // boat took one lamb 
Node 2 : { lambs:1, wolves:3, boat:1 } // boat took two lambs 
Node 3 : { lambs:2, wolves:2, boat:1 } // boat took one lamb and one wolf 
Node 4 : { lambs:3, wolves:1, boat:1 } // boat took two wolves 
Node 5 : { lambs:3, wolves:2, boat:1 } // boat took one wolf 

のように。可能な移動のツリーを探索するときにこれらを動的に生成することができます。 そして、Erickはコメントの中で指摘しているように、これらのいくつかはルールに従って正当ではないので、グラフ内にあってはいけません。わたしはそれをあなたに任せて理解する。

終了ノードは次のとおりです。

Node N : { lambs:0, wolves:0, boat:1 } 

キーテイクアウトは、あなたが可能な状態のない川の両側や動物とのグラフ間のグラフを必要とするということです。そして、各州は「世界」モデルのすべてを捕らえる必要があります。擬似C＃コードで

：*もBFS

public class Node 
{ 
    public int LambsOnLeft {get; set;} 
    public int WolvesOnLeft {get; set;} 
    public int Boat {get; set;} 

    public IEnumerable<Node> NextStates() 
    { 
     if (Boat == 0) // on left 
     { 
       // boat takes one lamb from left to right 
      if (LamsOnLeft > 0 && LambsOnLeft-1 >= WolvesOnLeft)  
       yield return new Node(LambsOnLeft-1, WolvesOnLeft, 1); 
      } 
      if (LambsOnLeft > 1 && LambsOnLeft-2 >= WolvesOnLeft) 
       yield return new Node(LambsOnLeft-2, WolvesOnLeft, 1); 
      } 
      // take one wolf 
      if (WolvesOnLeft > 0) 
       yield return new Node(LambsOnLeft, WolvesOnLeft-1, 1); 
      // take two wolves 
      if (WolvesOnLeft > 1) 
       yield return new Node(LambsOnLeft, WolvesOnLeft-1, 1); 
      ... 
     } 
    } 
}