0

私たちの教授が私たちにくれた数学の課題について助けが必要です。どんな提案も役に立ちます。問題は：

N 人食い人種と M 宣教師がいます。すべての宣教師は、1 または任意の正の整数である強度属性を持っています。強さは、彼が戦うことができる人食い人種の数を示します。

基本的には、川の両側に 2 スロットのボートがあり、人食い人種が宣教師を食べないように、すべての人を反対側に移動する必要があります。

このためのプログラムをどのように作成しますか? 転送グループ化アルゴリズムは何でしょうか?

よろしくお願いします。

マーク。

4

1 に答える 1

1

問題を状態グラフとしてモデル化します。

ここで、状態は ({L,R} n ,{L,R} m ,{L,R}) です。

  • 最初nのエントリ: 宣教師ごとに 1 つ - 彼のいる場所: 川の左岸/右岸
  • 次に、mエントリ: カニバルごとに 1 つ - 彼がいる場所: 川の左岸/右岸
  • 最後のエントリはボートです

これらはあなたの頂点です - 宣教師の力が 1 つ (または複数) の側で十分でない無効な状態もトリムする必要があります。州ごとに計算するのは簡単です。

あなたのエッジは次のとおりです。

E = { (S1,S2) | Can move in one boat ride from S1 to S2 }

やるべきことはすべて残されています -最短経路アルゴリズム(L,L,....,L)を使用して、 からへの最短経路を見つけます(R,R,...,R)。

このタスクにはBFSを使用することも、双方向検索や、 A* Algorithmなどの情報に基づいたアルゴリズム (許容ヒューリスティックを使用) を使用することもできます。

PS。「グラフ」は単なる概念的なものであり、実際にはnext:S->2^S、状態を指定すると、この状態のすべての有効な後継者を返す関数があります (グラフの 1 つのエッジを使用してそれらに到達できる状態S)。これにより、その場で「グラフを生成」できます。

あなたのnext(S)関数は次のようなものでなければなりません（最適化なしの高レベルの擬似コード）：

next(S):
   let x be the bank where the boat is, and y the other bank
   for each person p1 on bank x:
      S' = S where boat and p1 moved from x to y
      if S' is valid according to strength limitations, yield S'
      for each p2 != p1 on bank x:
         S' = S where boat and p1 and p2 moved from x to y
         if S' is valid according to strength limitations, yield S'
于 2013-10-10T15:41:42.090 に答える