二分探索を現実の世界に適用しようとしたとき、私はがっかりしました。シナリオは次のとおりです。
無線で通信するデバイスの範囲をテストする必要があります。通信は迅速に行う必要がありますが、ある程度まで（たとえば、約3分）、低速の送信は許容されます。送信が失敗するまで200フィートごとに、最大1600フィートまで成功するかどうかをテストする必要があります。200フィートごとにテストが実行され、実行には3分かかります。
二分探索が障害点を見つける最も効率的な方法であると素朴に想定しましたが、200フィート/分の移動速度と3分のテスト時間を考慮してください。500フィートで送信の失敗が発生した場合、以下に示すように、バイナリ検索は障害点を見つけるための最も効率的な手段ではありません。
歩き回ってすべてのポイントをテストするだけで、12分しかかからず、より早く解決策が見つかりますが、バイナリ検索とテストには16分かかります。
私の質問：移動時間が重要な場合、ソリューションへの最も効率的なパスをどのように計算しますか？これは何と呼ばれますか（たとえば、バイナリ旅行検索など）？
二分探索は確かにO(1)アクセス時間に基づいています。たとえば、リンクリストを検索するポイントバイナリはほとんどありません[ただし、注1を参照]。これは、離散区間のみをテストする価値があると想定しているため、基本的にはこれを実行していることです。より正確な答えを探している場合は、二分探索で任意の精度が可能になりますが、精度のビットごとに1つの追加テストが必要になります。
最大値が何であるかさえわからないとします。次に、真ん中がどこにあるかわからないため、真ん中で最初にテストすることはできませんでした。代わりに、限界を指数探索することができます（これは一種の二分探索です）。でテストを開始しx、次に2x、4x最大値よりも大きいポイントに到達するまで（信号はそれほど遠くまで到達しません）。（xこれは、興味深いと思う最小の答えです。言い換えると、の最初のテストでx信号が到達しないことが示された場合は、停止します。）このフェーズの終わりに、ある整数に対して、になります。答えはとの間にあることがわかります。2ixi2i-1x2ix
これで、実際にバイナリ検索を実行できます。最初は。を逆方向に移動します。そこから、前方または後方に移動する可能性がありますが、確実に移動し、次の反復で移動します。2i-2x2i-3x2i-4x
したがって、全体として、最初のフェーズ（最大値を検索）では、に歩いてテストを行いました。2番目のフェーズであるバイナリリファインメントでは、合計を歩き、テストを実行します。との間のある時点で終了するので、最悪の場合、最後のポイントを歩いたことになります（そして、せいぜい、歩いたことになります）。実行するテストの数は、の1つのテスト内になります。2ixi(2i-1-1)xi-1d2i-12i3d3d/22*ceil(log2(d/x)) - 12*log2(d/x)
では、どのような状況で二分探索アルゴリズムを実行する必要がありますか？基本的に、それは移動時間とテスト時間の比率、および答えの望ましい精度に依存します。単純なシーケンシャルアルゴリズムは、サイズの移動とテストのd後に位置を見つけます。上記の二分探索アルゴリズムは、せいぜい移動した後に位置を見つけますが、テストの周りだけを実行します。大まかに言えば、テストに移動コストの2倍以上の費用がかかり、予想される距離が精度よりも十分に大きい場合は、二分探索を選択する必要があります。d/xxd/xd3d2 log(d/x)d/x
あなたの例では、200フィートの精度の結果が必要なようです。移動時間は1分、テスト時間は3分で、移動時間の2倍以上になります。したがって、（場合のように）精度の倍数の少数で答えが見つかると予想されない限り、二分探索を優先する必要があります。バイナリアルゴリズムは4つのテストと1000フィートの移動を使用しますが（シーケンシャルアルゴリズムの3つのテストと600フィートと比較して）、精度を50フィートに改善すると、バイナリアルゴリズムにさらに4つのテストと150フィートの移動が追加されるだけです。シーケンシャルアルゴリズムには20回のテストが必要です。
注1：実際には、テストのコストが高い場合は、上記のアルゴリズムを正確に使用して、リンクリストを二分探索することが理にかなっている場合があります。テストのコストがリスト内のインデックスに比例しないと仮定すると、検索の複雑さはO(N)線形検索とバイナリ検索の両方になりますが、バイナリ検索はO(log N)テストとO(N)ステップを実行し、シーケンシャル検索はO(N)テストを実行しますとO(N)ステップ。十分に大きいNの場合、これは重要ではありませんが、実際のサイズのNの場合、これは非常に重要になる可能性があります。
実際には、ここで二分探索を適用できますが、いくつかの変更があります。中心ではなく、訪問する最適な位置を計算する必要があります。
int length = maxUnchecked - minChecked;
whereToGo = minChecked + (int)(length * factorIncrease) + stepIncrease;
通信が失敗する最初の位置を見つける必要があるため、時々戻る必要があります。その後、他の戦略を使用するのに最適です。
int length = maxUnchecked - minChecked;
int whereToGo = 0;
if ( increase )
whereToGo = minChecked + (int)(length * factorIncrease) + stepIncrease;
else
whereToGo = minChecked + (int)(length * factorDecrease) + stepDecrease;
したがって、私たちのタスク-そのような最適なfactorIncrease、factorDecrease、stepIncrease、stepDecreaseを見つけるために、f（failPos）の合計の値は最小になります。どのように？n（全長/ 200.0f）が小さい場合は、フルブルートフォースが役立ちます。それ以外の場合は、遺伝的アルゴリズムまたは単純なsmthを使用してみることができます。
ステップ精度=1、ステップ制限= [0、n）。ファクターeps-1/（4 * n）、ファクター制限-[0,1）。
さて、これを実証するための簡単なコード（c＃）：
class Program
{
static double factorIncrease;
static int stepIncrease;
static double factorDecrease;
static int stepDecrease;
static bool debug = false;
static int f(int lastPosition, int minChecked, int maxUnchecked, int last, int failPos, bool increase = true, int depth = 0)
{
if ( depth == 100 )
throw new Exception();
if ( maxUnchecked - minChecked <= 0 ) {
if ( debug )
Console.WriteLine("left: {0} right: {1}", minChecked, maxUnchecked);
return 0;
}
int length = maxUnchecked - minChecked;
int whereToGo = 0;
if ( increase )
whereToGo = minChecked + (int)(length * factorIncrease) + stepIncrease;
else
whereToGo = minChecked + (int)(length * factorDecrease) + stepDecrease;
if ( whereToGo <= minChecked )
whereToGo = minChecked + 1;
if ( whereToGo >= maxUnchecked )
whereToGo = maxUnchecked;
int cur = Math.Abs(whereToGo - lastPosition) + 3;
if ( debug ) {
Console.WriteLine("left: {2} right: {3} whereToGo:{0} cur: {1}", whereToGo, cur, minChecked, maxUnchecked);
}
if ( failPos == whereToGo || whereToGo == maxUnchecked )
return cur + f(whereToGo, minChecked, whereToGo - 1, last, failPos, true & increase, depth + 1);
else if ( failPos < whereToGo )
return cur + f(whereToGo, minChecked, whereToGo, last, failPos, true & increase, depth + 1);
else
return cur + f(whereToGo, whereToGo, maxUnchecked, last, failPos, false, depth + 1);
}
static void Main(string[] args)
{
int n = 20;
int minSum = int.MaxValue;
var minFactorIncrease = 0.0;
var minStepIncrease = 0;
var minFactorDecrease = 0.0;
var minStepDecrease = 0;
var eps = 1 / (4.00 * (double)n);
for ( factorDecrease = 0.0; factorDecrease < 1; factorDecrease += eps )
for ( stepDecrease = 0; stepDecrease < n; stepDecrease++ )
for ( factorIncrease = 0.0; factorIncrease < 1; factorIncrease += eps )
for ( stepIncrease = 0; stepIncrease < n; stepIncrease++ ) {
int cur = 0;
for ( int i = 0; i < n; i++ ) {
try {
cur += f(0, -1, n - 1, n - 1, i);
}
catch {
Console.WriteLine("fail {0} {1} {2} {3} {4}", factorIncrease, stepIncrease, factorDecrease, stepDecrease, i);
return;
}
}
if ( cur < minSum ) {
minSum = cur;
minFactorIncrease = factorIncrease;
minStepIncrease = stepIncrease;
minFactorDecrease = factorDecrease;
minStepDecrease = stepDecrease;
}
}
Console.WriteLine("best - mathmin={4}, f++:{0} s++:{1} f--:{2} s--:{3}", minFactorIncrease, minStepIncrease, minFactorDecrease, minStepDecrease, minSum);
factorIncrease = minFactorIncrease;
factorDecrease = minFactorDecrease;
stepIncrease = minStepIncrease;
stepDecrease = minStepDecrease;
//debug =true;
for ( int i = 0; i < n; i++ )
Console.WriteLine("{0} {1}", 3 + i * 4, f(0, -1, n - 1, n - 1, i));
debug = true;
Console.WriteLine(f(0, -1, n - 1, n - 1, n - 1));
}
}
したがって、いくつかの値（f ++ --factorIncrease、s ++ --stepIncrease、f-- --factorDecrease）：
n = 9 mathmin = 144, f++: 0,1(1) s++: 1 f--: 0,2(2) s--: 1
n = 20 mathmin = 562, f++: 0,1125 s++: 2 f--: 0,25 s--: 1
実際に最適化したいものによっては、最適な検索パターンを見つける方法があるかもしれません。多くの検索戦略で最も遅いケースは休憩が最後にあるときであり、バイナリ検索は実際にはここでかなり良いので、最悪の場合の時間を最適化したくないと思います-方向を変えずに最後まで歩きます、そしてあなたはあまり多くの停止をしません。
さまざまな二分木を検討し、葉に到達するまでにかかる平均時間を計算することもできます。二分探索は一種のツリーであるため、歩きながらテストを行います。これは、各ノードに少なくとも1つのリーフが接続されている非常に不均衡なツリーです。
そのような木に沿って進むときは、常にあなたが歩いている線の一方の端またはもう一方の端から始め、測定を行う前にある程度の距離を歩き、結果と木に応じて、停止するか、より短い時間でプロセスを繰り返します線、あなたがそれの一方の端またはもう一方の端にいるところ。
これにより、動的計画法を使用して攻撃できるものが得られます。最大Nセグメントの長さの問題を解決したと仮定します。これにより、これらの長さの最適なソリューションのコストがわかります。これで、N+1セグメントの最適なソリューションを見つけることができます。N+1の可能な方法でN+1セグメントを2つの部分に分割することを検討してください。そのような方法ごとに、決定ポイントに移動して測定を行うコストを計算し、決定ポイントの両側にあるセグメントの2つのセクションについて、可能な限り最良のソリューションのコストを追加します。それらのセクションで終わる確率。これらのN+1の可能な方法を検討することにより、N + 1セグメントを分割する最良の方法とそのコストを考え出し、実際にあるセクションの数に最適な解決策を見つけるまで続けることができます。