4

数独パズルを生成するためのランダム化された再帰バックトラッキング アルゴリズムがあります (こちらを参照)。平均して十分に高速に動作しますが、最悪の場合の実行時間は容認できないほど遅くなります。以下は、100 回の試行の実行時間 (ミリ秒単位) のヒストグラムです (「More」は約 200,000 ミリ秒です!)。

ここに画像の説明を入力

tミリ秒後に単純にタイムアウトし、新しいランダム シードで再起動することで、アルゴリズムを改善したいと考えています。これが無限に繰り返されるのを防ぐために、n回試行したら停止するか、試行が失敗するたびにtを増やします。tが中央値よりもはるかに大きい場合、その後の試行ではるかに高速に実行できる可能性が高くなります 。

質問:

  1. 異なるプロセッサのタイムアウト期間tを調整するにはどうすればよいですか? 各実行前にプロセッサのパフォーマンスをベンチマークする高速で信頼性の高い方法はありますか? または、以前のすべての実行の平均実行時間を使用するなど、複数回の実行でプロセッサに適応する必要がありますか? 関連する場合は、Androidでこれを実行しています。
  2. ランタイムの分布におけるロングテールを完全に回避するためのより良い戦略はありますか?
4

2 に答える 2

2

アルゴリズムは再帰的であるため、最大再帰深度を確立してみませんか？特定のランダムシードが、ロングテールに当たるのに十分な高さであると経験的に確立した再帰深度につながる場合は、その時点で中止します。

視覚的な概算では、4500ミリ秒後、特定のシードに対する投資から大きな利益を得られないように見えます。そのベンチマークを再実行し、再帰の深さも追跡して、その数を確認します。ただし、100を超えるサンプルを実行します。

そのソリューションはCPU速度に依存しません。

于 2013-01-10T21:36:21.923 に答える
1

  1. はい、あります。信頼区間と呼ばれます。前処理（またはオンザフライ）でアルゴリズムを数回実行することにより、実行時間の中央値が 存在する間隔xをx％の信頼度（パラメーターはここで）で決定できます。間隔のサイズを次のように減らすことができます。アルゴリズムの実行回数を 増減します。もちろん、アルゴリズム自体を実際に実行できない場合は、あるマシンでベンチマークを実行して信頼区間を見つけ（そうさせてください）、別のアルゴリズムのタイミングを指定した関数を作成することができます（タイミングはsです）。 ）別のマシン（M）で、マシンMの間隔を予測します。
    x

    If(I,s)
    検出sは同様の方法で行われます-信頼区間を使用します。

  2. あなたのアプローチはうまくいくようです、私はおそらく同じことをするでしょう-私は最初に小さな係数を設定し、失敗するたびにそれを増やします。これは、ネットを介したパッケージの許容転送速度を見つけるための（ネットワークの分野からの）TCPプロトコルの輻輳制御にいくらか似ていることに注意してください。

于 2013-01-10T21:41:42.933 に答える