2

グループに分割されたセット (またはグラフ) があるとします。2 つのパーティション間の遷移の数を見つけることに興味があります。遷移には、1 つのパーティションから要素を取り出して別のパーティション (またはシングルトン パーティション自体) に移動することが含まれます。

たとえば、パーティション間に 1 つの遷移があります。

1 2 | 3と 1 | 2 | 3

しかし ～の1 2 3 4間1 2 | 3 | 4

トランジションの最小数は 2 だと思います。

私の質問は、パーティションのペアとセットを指定して、それらの間の遷移状態の数を返すことができるアルゴリズムはありますか?

このセットが実際にはグラフを表すというさらに複雑な問題があり、すべてのパーティション (および遷移パーティション) を接続する必要があります (つまり、3 によってブロックされていない 1 と 2 の間に間接接続または直接接続が存在しない場合、1 2 | 3 は無効になります)シングル パーティション) ですが、このトピックについて本当に理解していない限り、おそらくそれを無視することができます。

ありがとう

メモとして、私は自分で考えた方法を持っています。これは、基本的にパーティション A のすべての隣接 (つまり、1 つの遷移内で見つけることができるすべてのパーティション) を見つけ、パーティション B に対して同じことを行い、これらがこれらの間に重複している場合隣接する 2 つのセットがある場合、それらは 1 つの遷移先にあります。ただし、この方法はすぐに非常に高価になります。

4

1 に答える 1

1

私はあなたの方法を少し拡張し、基本的にグラフを作成してグラフ検索を行います。グラフの頂点はセットの有効な分割であり、エッジは遷移です。実際には、作成と検索を同時に行うことができ、検索に必要なグラフの部分のみを作成できます。

これを行うには、A* (またはその他の最適優先検索) を使用し、各ステップで現在のパーティションのすべての近傍を生成します。注意が必要な部分は、A* 検索に最適なヒューリスティックを決定することです。おそらく、すべての遷移が接続されたパーティションになると仮定することで、遷移の数を見積もることができます (基本的に、制約を無視します)。

これは明らかにコストがかかりますが、ベスト ファースト検索を使用し、進行中にグラフを生成することで、時間とスペースを節約できます。

于 2010-08-22T04:58:59.720 に答える