グラフにはノードとエッジがあります。
ノードは状態を意味します。つまり、すべてのコンテナの状態
エッジは、状態間の (有効な) 遷移を意味します。
状態を変更するすべての方法を列挙できる場合、ノードから他のノードへのすべての発信エッジを列挙できます。
例としてコンテナーを使用します。
状態: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 回生成しないようにします。