2

次のクラスの問題の名前を探しているので、効果的なアルゴリズムと詳細情報をグーグルで検索できます。

{-1, 0, 1} の 3 文字のアルファベットがあります。

長さ 24 のすべての文字列を効果的に生成する必要があります。これらのほとんどは {0} ですが、0 ～ 8 個の {1,-1} 文字が特定のパターンで分散されています。(パターンには、{-1} の数とペアリングに関する制限があります)。私の基準を満たす文字列の総数はかなり控えめで、約 128,000 です。

では、このクラスの問題/アルゴリズムの名前は何ですか?

4

3 に答える 3

3

これに対して明確に定義された「アルゴリズムクラス」があるかどうかはわかりません。それは単なる組み合わせ論の演習です。生成は次の 3 つのステップで実行できます。

  1. すべての 24 ビット数値を 8 ビット以下のセットで生成します (いくつかのルックアップ テーブルを事前に計算すると、これを少し高速化できる場合があります)。
  2. n ビットが設定された 24 ビットの数値ごとに、すべての n ビットの数値を反復します。
  3. n ビット数の k 番目のビットが 0 の場合、24 ビット数の k 番目のセット ビットは -1 として出力され、それ以外の場合は 1 として出力されます。

手順 2 ～ 3 をもう少しうまく説明するには、24 ビットの数値に 4 ビットが設定されており、次のように見えるとします。

0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0

0 0 0 0次に、 からまでの 16 個の 4 ビット数値すべてを反復処理します1 1 1 1。たとえば、次のようになります。

0 0 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 -1 0 0 0 0
0 1 1 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0 -1 0 0 0 0
0 1 0 0 gives the string  0 0 0 -1 0 0 0 0 0 0 0 0  1 -1 0 0 0 0 0 -1 0 0 0 0
1 1 1 1 gives the string  0 0 0  1 0 0 0 0 0 0 0 0  1  1 0 0 0 0 0  1 0 0 0 0
于 2009-06-23T16:05:17.153 に答える
1

作業コードは研究論文へのリンクよりも優先される傾向があるため、前回とは完全に別の答えです。このコードは物理フォーラムで見つけたため、自分でクレジットすることはできません。修正しただけで、g ++でコンパイルされ、定数に変更されました。 24で8ビットを探します。8ビットがオンになっている24ビット文字列すべてを非常にすばやく列挙します。これらは約735,000個しかありません。これらの「テンプレート」は、ゼロ以外の文字の唯一の有効なパターンを示しています。次に、これらの735,000の回答をそれぞれ取得し、-/ +記号を使用して、それぞれが基準を満たしているかどうかを判断する必要がありますが、この方法では、2,000億ではなく、73.5万の可能な解決策から始めます。

#include <stdio.h>

 int main()
 {
 int size = 24;
 int pop = 8;

 int n = ((1 << pop) - 1) << (size - pop);

 while(true) {
    printf( "%x\n",n);

    int lowest = n & -n;

     if(lowest > 1) {
        n = n ^ lowest ^ (lowest >> 1);
        continue;
     }

     int high = n & (n + lowest);
     if(high == 0) break;

     int low = n ^ high;

     low = (low << 2) + 3;

     while((low & high) == 0) low <<= 1;
     n = high ^ low;
  }
 }
于 2009-06-23T17:10:00.883 に答える
1

これを 1 回だけ解決する必要がある場合は、力ずくで解決して、結果をアプリケーションのルックアップ テーブルに入れることができます。チェックする 0、1、-1 の 24 ビット シーケンスは 1 兆未満です。

おそらく私の計算が間違っているか、実行時に問題を動的に解決する必要がある場合、問題をそれぞれが -1、0、1 に制限された 24 個の変数のシステムと見なし、制約充足問題としてアプローチします。何らかの方法で制約を列挙できると仮定します。ただし、私の懸念は、サブセットだけでなくすべてのソリューションを確認する必要があるため、問題空間を徹底的に検索する必要があることです。

Enumerating All Solutions for Constraint Satisfaction Problemsという論文はあなたの好みに合っているようです。論文の全文にアクセスして、それが役立つかどうかを確認することはできませんが.

私は一緒に間違った木を吠えているかもしれませんが、おそらくこれは出発点です

于 2009-06-23T16:41:34.607 に答える