2

特定のルールを満たす20個の要素のすべての可能な順列を見つける必要があります。たとえば、要素1を位置3,4、6、7、8、12、および17に配置することはできません。要素2を位置1、2、7、10、19に配置することはできません。現在、私はすべての可能な順列を通過し、ルールが満たされているかどうかをチェックする再帰関数を使用しています。これは10個の要素（10！順列）で完全に正常に機能しますが、ご想像のとおり、アルゴリズムは20個の要素では使用できなくなります。不要な順列をスキップするより効率的なアプローチを知っている人はいますか？（20！= 2.4E18の可能な順列から、1〜2Mioのみがルールを満たすと思います。

これは私が今使っているものです（パスカルコード）：

 procedure permu(p:feldtyp; ka:bereich); 
 var
   i,h : bereich; 
 label skip;
 begin 
   if ka=teams then begin 

    //execute certain tests, skip the output part if the tests fail 
    for i:=1 to ka do if ((hh11[P[i]]+hh21[i])<>(ka-1)) or 
      ((patterns[h1[P[i]]][teams-1]=patterns[h2[i]][1]) and ((patterns[h1[P[i]]][teams-1]=patterns[h1[P[i]]][1])=(patterns[h2[i]][teams-1]=patterns[h2[i]][1]))) or 
      ((patterns[h1[P[i]]][teams-1]<>patterns[h2[i]][1]) and ((patterns[h1[P[i]]][teams-1]=patterns[h1[P[i]]][1])<>(patterns[h2[i]][teams-1]=patterns[h2[i]][1]))) or 
      ((patterns[h1[P[i]]][teams-1]<>patterns[h2[i]][1]) and ((patterns[h1[P[i]]][teams-1]=patterns[h1[P[i]]][1]) and (patterns[h2[i]][teams-1]=patterns[h2[i]][1]))) or 
      ((patterns[h1[P[i]]][teams-1]=patterns[h2[i]][1]) and ((patterns[h1[P[i]]][teams-2]=patterns[h1[P[i]]][teams-3]) or (patterns[h2[i]][2]=patterns[h2[i]][3]))) or 
      ((patterns[h1[P[i]]][teams-1]=patterns[h1[P[i]]][teams-2]) and (patterns[h2[i]][1]=patterns[h2[i]][2])) 
    then goto skip; 

    //all tests passed, write permutation
    // ...
    skip:
  end 
  else begin 
    for i := ka to teams do begin 
      h := P[i]; 
      P[i] := p[ka]; 
      P[ka] := h; 
      permu(p, ka+1); 
    end;
  end;
end;

（「teams」は定数20、「h1」、「h2」は別の場所で定義されたいくつかの配列[1..20]です。さらに、ルールを導出するために使用されるグローバル2次元配列「patterns」が定義されています。この配列n行19列の大きな0-1行列として見ることができます）

4

1 に答える 1

0

n!多項式にはほど遠いため、実行時間は大きくなるほど大幅に増加しますn。「どの番号がどのスロットに移動できる/できない」というパターンがある場合は、その構造を使用してアルゴリズムを改善できますが、問題はそうではありません。

その手助けになるものがあるかもしれません。まず第一に、配置する数字を反復します。スロットを埋めるのではありません。

数字のそれぞれについて、1, .., nそれらが入ることができるスロットのリンクされたリストを使用します。番号 3 は、スロット 3、16、7、6 にのみ入ることができます。これは、n=3 のリンク リストです。

nすべての要素の「中央」配列 (直接アクセス) を維持します。x などの数値をスロット p に配置すると、その中央の配列の p 番目の要素が反転されます。

番号を並べ替えてn、リストの一番上がスロットの最小数に入ることができる番号であり、一番下がスロットの最大数に入ることができる番号です。

リストの一番上にある番号から始めて、これらのリンクされたリストを使用して順列を取り続けます。番号を空のスロットに配置します。これにより、最適ではあるが指数関数的な時間で解が得られます。問題は指数関数的です。

サブ最適化アルゴリズムを多項式時間で実行することもできますが、すべての順列が許可されるとは限りません。

于 2012-11-23T04:31:48.307 に答える