私は現実世界の問題を次の質問に抽象化しています。
- Xは、文字のすべての可能な順列のプールです。
- Yは文字列のプールです。
- Fは、Xから候補xを取得し、xがYに属するかどうかに応じてブール値を返す関数です。
Fは高価で、Xは巨大です。Yからできるだけ多くの結果を抽出するための最も効率的な方法は何ですか？誤検知は問題ありません。
3 に答える
2
この種の問題に対するほとんどのソリューションはドメイン固有であるため、この質問にうまく答える方法は実際にはありません。
ここで質問を試してみてください: https://cstheory.stackexchange.com/
しかし、あなたが話している可能性の範囲の例を挙げると、巡回セールスマンの問題も似ているようで、多くの場合、「自己組織化マップ」で解決されます: http://www.youtube.com/watch?v=IA6eGYMyr1A
もちろん、巡回セールスマンの問題に対して人々が思いつく「解決策」は、最良の解決策である必要はなく、単に良い解決策である必要はありません...したがって、あなたの質問は、これがあなたの状況に当てはまるかどうかを示していません。いいえ。
ある種のより効率的なブルート フォーシング手法を求めているように聞こえますが、何もありません。
別の例として、パスワードをクラックする場合 (質問に似ているようです)、人々は最初に「一般的に使用される単語/パスワード」を試してから、総当たり攻撃に頼ることがよくありますが、これもドメイン固有のソリューションです。
于 2011-06-15T03:15:23.820 に答える
1
Delta ベースのスコア計算を実装することで、F のコストを削減します。次に、メタヒューリスティック (または分岐限定) を使用して、できるだけ多くの Y を見つけます (たとえば、Drools Plannerを使用します)。
于 2011-06-21T09:00:06.180 に答える
0
安価で、x が y に属しているかどうかもテストする別の関数 G を導入します。F が true を返すときは常に G は true を返す必要があり、F が false を返すときは true を返すことができます。最初に G でテストし、G が true を返す場合にのみ F でテストします。
あなたの定式化の一般性を考えると、これ以上具体的なことを言う方法がわかりません。
于 2011-06-15T05:14:10.550 に答える