5

一連の数値{0、1、2、4、5 ...}と各要素の相対位置に関する一連の条件が与えられた場合に、有効な順列が存在するかどうかをチェックするアルゴリズムを探しています。条件は常にタイプ「元の配列の位置iの要素は位置jまたはzの要素の隣（隣接）でなければなりません」です。
順列の最後と最初の要素は隣接していると見なされます。

簡単な例を次に示します。

数値を{0、1、2、3}
とし、一連の条件を設定します。a0はa1の隣にある必要があり、a0はa2の隣にある必要があり、a3はa1の隣にある必要があります
。この例の有効な解決策は{0、 1,3,2}。

このソリューションの回転/対称性も有効なソリューションであることに注意してください。そのような解決策が存在することを証明する必要があります。

同じセットを使用する別の例：
a0はa1の隣にある必要があり、a0はa3の隣にある必要があり、a0はa2の隣にある必要があります。

番号は2つの番号にしか隣接できないため、この例の有効な解決策はありません。

私が今思いつくことができる唯一のアイデアは、ある種のバックトラックを使用することです。
解決策が存在する場合、これは静かに速く収束するはずです。解決策が存在しない場合、考えられるすべての順列をチェックすることを回避する方法を想像することはできません。すでに述べたように、回転や対称性は特定の順列の結果に影響を与えないため、可能性の数を減らすことができるはずです。

4

3 に答える 3

1

基本的に、あなたは数の連鎖を作ることができるかどうか知りたいです。各番号をチェーンに入れて、番号と最大2つの隣接番号を追跡します。ルールを使用してチェーンを結合します。2つのチェーンを結合すると、2つのルーズエンド（隣接）を持つチェーンになります。あなたがルーズエンドを使い果たすことなくすべてのルールを通り抜けることができれば、それはうまくいきます。

于 2012-05-09T00:56:30.667 に答える
1

これをグラフ問題として定式化します。隣り合う必要のある番号のすべてのペアを接続します。最終的には、接続されたコンポーネントの束になります。各コンポーネントにはいくつかの順列があり（それらをミニ順列と呼びます）、コンポーネントの順列を持つことができます。

グラフを作成するときは、各コンポーネントが一連のルールに従っていることを確認してください。サイクルがない、頂点が2つを超える頂点がないなどです。

于 2012-05-09T03:25:29.300 に答える
0

少し変更を加えてグラフソリューションを実装しました。

ノードに隣接ノードが多すぎる場合、アルゴリズムは1つのエッジをドロップし、グラフを再度チェックします。次に、バックトラッキングを使用してロールバックし、次のエッジをドロップできるかどうかを確認します...この方法では、私が書いたブルートフォース方法と同じ結果が得られます。

複雑さの点では、このソリューションはブルートフォースよりも優れているようですが、20を超える数値（ブルートフォースの場合は8つのみ）で実行することはできません。ある意味では、このようなグラフは実際に有効な順列のサブセットを一度に生成できるため、これは論理的です。さらに、最悪の場合、エッジのセット全体でいくつかの構成を見つけることと同等です。結局、バックトラックです。

回転は順列の有効性に影響を与えないので、a0を最初の位置に固定することを考えていました（これは、a0が最初の位置になるまで有効な順列を回転させるだけで実現できます）。そこからの解決策。

DPを使用すると、指数関数的な複雑さよりも優れたものが得られる可能性があります。しかし、私はまだどこから始めればよいのかわからないと言わなければなりません:)

于 2012-05-09T16:53:32.480 に答える