2

私が抱えている問題に非常に近いこの投稿を読みましたが、一般化することはできませんでした。複数のCPUを使用してすべてのパスを検索することにより、巡回セールスマンを解決しようとしています。私が必要としているのは、パスプレフィックスを整数にエンコードし、それを各CPUに配布して、スキャンすることになっているパスを認識できるようにする方法です。たとえば、都市の数が10の場合、1つの可能な3プレフィックス（プレフィックスの長さが固定されて既知であると仮定）は4-10-3（10 * 9 * 8プレフィックスがある）であるため、それを受け取るCPUは次のようになります。 4-10-3で始まるすべてのパスを検索します。都市の数が非常に多いので、nを計算できません！したがって、上記の投稿は使用できません。

4

2 に答える 2

2

数としての順列の標準表現は、階乗数法で表されるレーマーコードを使用します。アイデアは、n個の要素のすべての順列をn個の数のシーケンスにマップできるということです。最初の数は0から（n-1）の範囲にあり、2番目の要素は0から（n-2）の範囲にあります。 、など。この数のシーケンスは、因数分解数システムで単一の整数として表すことができます。

私は、このトリックを、順列全体ではなく、順列の接頭辞で機能するように適応させることができるはずだと信じています。n個の要素があり、そのうちのk個の順列を選択するとします。これを行うには、部分置換のレーマーコードを計算することから始めます。n個の数値のシーケンスを取得する代わりに、k個の数値のシーケンスを取得します。たとえば、c a dから引き出された部分置換を考えるa b c d e f gと、レーマーコードは次のようになります。

  • cの2番目の（ゼロインデックス）要素ですa b c d e f g
  • aのゼロ番目（ゼロインデックス）要素ですa b d e f g
  • dの最初の（ゼロインデックス）要素ですb d e f g

したがって、レーマーコードはになります(2, 0, 1)。

このレーマーコードを入手したら、それを単一の整数としてエンコードしてみることができます。これを行うには、修正された階乗数法のエンコーディングを使用できます。具体的には、次のことを試してみてください。n個の要素があり、そのうちのk個の順列が必要な場合は、最後の要素に対して合計（n --k + 1）個の可能な選択肢があります。最後から2番目の要素には合計（n --k + 2）の選択肢があり、最後から3番目の要素には（n --k + 3）の選択肢があります。したがって、レーマーをとることができます。コードを記述し、次のようにします。

  1. 最後の桁は変更しないでください。
  2. 最後から2番目の要素に（n --k + 1）を掛けます。
  3. 最後から3番目の要素に（n --k + 1）（n --k + 2）4..を掛けます。
  4. 最初の要素に（n-k + 1）（n-k + 2）...（n-1）を掛けます
  5. これらの値を合計します。

これにより、順列の一意の整数コードが生成されます。

たとえば、レーマーコードは(2, 0, 1)、n = 7、k = 3でした。したがって、次のように計算します。

1 + 0×（7-3 + 1）+ 2×（7-3 + 2）（7-3 + 3）

= 1 + 2×（5×6）

= 5+2×30

= 61

このプロセスを逆にするには、整数を取得し、この手順を逆方向に実行して、部分的なレーマーコードを回復します。これを行うには、数値を取得し、（n --k + 1）（n --k + 2）...（n --1）で除算して、レーマーコードの最初の桁を取得することから始めます。次に、数値を（n --k + 1）（n --k + 2）...（n --1）で変更して、最初の桁を削除します。次に、数値を（n --k + 1）（n --k + 2）...（n --2）で除算して、レーマーコードの2桁目を取得し、modを（n --k + 1）（で除算します。 n --k + 2）...（n --2）2桁目をドロップオフします。レーマーコードのすべての桁が再構築されるまで、これを繰り返します。

たとえば、接頭辞61、n = 7、およびk = 3が与えられた場合、61を7×6 = 30で割ることから始めます。これにより、2、余り1が得られます。したがって、レーマーコードの最初の桁は2です。 30、数値1を返します。次に、6で除算します。これにより、0、余り1が得られます。したがって、2番目の桁は0です。最後に、残りの数値を読み取り、レーマーコードの最後の桁1を示します。 。レーマーコードを復元しました。このコード(2, 0, 1)から、順列を簡単に再構築できます。

お役に立てれば！

于 2013-01-05T19:36:43.373 に答える
1

ここでの最も簡単な方法は、順列の一部として扱わずにプレフィックスをマップすることです。プレフィックスを[0,10*9 * 8-1]にマップするのではなく、[0,10 * 10 * 10-1]にマップするため、プレフィックス0,4,5は番号45にマップされます。プレフィックス4,1,9は番号419にマップされます（もちろん、全体で10の都市があると仮定します）。

于 2013-01-05T19:37:05.560 に答える