-1

一般的なコンテナーの問題を考えてみましょう。

コンテナは3つあり、1つは10リットル、1つは7リットル、もう1つは4リットルです。10 リットルのコンテナは空で、7 リットルと 4 リットルのコンテナは満杯です。a) 注ぐ容器が空になるか、b) 受け取る容器がいっぱいになるまで、ある容器の内容物を別の容器に注ぐだけで、別の状態に到達できる方法を列挙してください.

宿題 (私は既に完了しています) のために、このクラスの問題をグラフとして解釈する方法と、解を見つけるためにグラフで実行するアルゴリズムについて話し合うことになっていました。

私の質問は、特定の初期条件が与えられた場合に、3 つのコンテナーのすべての可能な状態のグラフをどのように作成できるかということです。コンテナーの特定のセットには N 個の可能な状態が存在する可能性がありますが、初期条件からは到達できない M 個の互いに素な状態があると思います。では、有効なグラフの N - M 個の頂点と、それらの頂点を結ぶエッジをどのように見つけるのでしょうか?

4

1 に答える 1

0

グラフにはノードエッジがあります。

ノードは状態を意味します。つまり、すべてのコンテナの状態

エッジは、状態間の (有効な) 遷移を意味します。

状態を変更するすべての方法を列挙できる場合、ノードから他のノードへのすべての発信エッジを列挙できます。

例としてコンテナーを使用します。

状態:10リットル容器(若干量入り)、7リットル容器(若干量入り)、4リットル容器(若干量入り)

状態遷移関数:

  • 4リットルの容器の中身を7リットルの容器に注ぐ
  • 7リットルの容器の中身を10リットルの容器に注ぐ
  • 4リットルの容器の中身を10リットルの容器に注ぐ
  • 7リットルの容器の中身を4リットルの容器に注ぐ
  • 10リットルの容器の中身を4リットルの容器に注ぐ
  • 10リットルの容器の中身を7リットルの容器に注ぐ

これらの関数の制約: 注ぐコンテナが空になるか、受け取るコンテナがいっぱいになるまで注ぐ。

n 個のコンテナがあり、これらのコンテナ間の潜在的な (n は 2 を選択) 相互作用があります。

これらの関数のいずれかを呼び出すと、別の状態に移行する場合があります。

各エッジ遷移に関連付けられたコストを定義できます。このような単純な問題では、すべてのエッジ遷移関数は同じコスト (1) を持ちますが、地図上の都市間を移動するような実際の例では、コストはエッジに沿って移動する必要がある距離になる場合があります。

おそらく、4 リットルの容器からの注ぎ出しを最小限に抑えたいと思うでしょう。4 リットルのコンテナを他のコンテナに注ぐことを伴うすべてのエッジに対して、1 ではなく 2 のエッジ ウェイトを割り当てることができます。

ノードとエッジに関してグラフを定義したので、それを検索できます。

おそらく、あなたが言及したような開始状態があります (10 リットルのコンテナーは空で、7 リットルと 4 リットルのコンテナーは満杯です)。そして、別の状態 (10 リットルのコンテナーは満杯、7 リットルのコンテナーは空、4 リットルのコンテナーは 1 リットル) に到達したいと考えています。初期状態からグラフを検索し、ゴールに到達したら検索を停止できます

従来のグラフ検索手法には、幅優先検索 (BFS) と深さ優先検索 (DFS) があります。ウィキペディアに行ってそれらを学びましょう。A* のような他のグラフ検索手法では、目標状態に最速で到達しようとするヒューリスティックまたは経験則が定義されています。ヒューリスティックには、目標に到達するまでの時間を見積もることが含まれます。特定の問題に対するヒューリスティックを定義するためのあらゆる種類の研究があります (ヒューリスティックを考え出すのは非常に難しい場合があります!)。

後で検索するグラフを実際に作成するには、前述の BFS または DFS メソッドを使用します。簡単に言えば、初期条件を記述するノードを作成し、それにすべての状態遷移関数を適用して、到達可能なすべてのノードを生成します。これらのノードをリストに配置します (これらは、生成されたがまだ展開されていないノードです)。リスト内の各要素について、同じ方法で展開します。展開が完了したノードを閉じたリストに配置して、同じノードを 2 回生成しないようにします。

于 2013-02-22T21:37:05.810 に答える