当我试图将二分搜索应用到现实世界时，它让我失望了。场景如下。
我需要测试通过无线电通信的设备的范围。通信需要快速进行，但可以容忍缓慢的传输，直到某个时间点（例如，大约 3 分钟）。我需要测试传输是否每 200 英尺成功一次，直到失败，最多 1600 英尺。每 200 英尺将进行一次测试，需要 3 分钟才能执行。
我天真地假设二分搜索将是找到故障点的最有效方法，但考虑到 200 英尺/分钟的行进速度和 3 分钟的测试时间。如果在 500 英尺处发生传输失败，则二分查找不是查找故障点的最有效方法，如下所示。
简单地走走并测试每个点会更快地找到解决方案，只需要 12 分钟，而二进制搜索和测试需要 16 分钟。
我的问题：当旅行时间很重要时，您如何计算最有效的解决方案路径？这叫什么（例如，二元旅行搜索等）？
二分搜索确实是基于O(1)访问时间的；例如，对链表进行二进制搜索几乎没有意义[但请参见注 1]，这基本上就是您正在做的事情，因为您似乎假设只有离散间隔值得测试。如果您正在寻找更准确的答案，您会发现二分搜索允许任意精度，但每精度位需要进行一次额外的测试。
假设您甚至不知道最大值可能是多少。然后你不能先在中间测试，因为你不知道中间在哪里。相反，您可以对限制进行指数搜索（这是一种由内而外的二进制搜索）；您首先在 处进行测试，x然后在 处进行测试，直到达到大于最大值的点（信号没有达到那么远）。（是你觉得有趣的最小答案；换句话说，如果第一次测试显示信号没有到达，那么你将停止。）在这个阶段结束时，你将在，对于某个整数，并且你会知道答案在和之间。2x4xxx2ixi2i-1x2ix
现在您实际上可以进行二分搜索了，从. 从那里，您可能会前进或后退，但您肯定会旅行，下一次迭代您将旅行，依此类推。2i-2x2i-3x2i-4x
所以总而言之，在第一阶段（搜索最大值），您走到，并进行了测试。在第二阶段，二元细化，您总共走并做测试。你最终会到达 和 之间的某个点，所以在最坏的情况下你会走过最后一点（最好的情况下，你会走过）。您将完成的测试数量将在 1 次测试范围内。2ixi(2i-1-1)xi-1d2i-12i3d3d/22*ceil(log2(d/x)) - 12*log2(d/x)
那么什么情况下应该做二分查找算法呢？基本上，它取决于旅行时间和测试时间的比例，以及所需的答案精度。简单的顺序算法在大小移动和测试d后找到位置；上面的二进制搜索算法最多在旅行后找到位置，但只在测试周围进行。粗略地说，如果测试花费的成本是旅行成本的两倍以上，并且预期距离远大于精度，那么您应该更喜欢二分搜索。d/xxd/xd3d2 log(d/x)d/x
在您的示例中，您似乎想要精度为 200 英尺的结果；行程时间1分钟，考试时间3分钟，是行程时间的两倍多。因此，您应该更喜欢二分搜索，除非您希望以少量的精度倍数找到答案（就像这种情况一样）。请注意，尽管二进制算法使用了 4 次测试和 1000 英尺的行程（与顺序算法的 3 次测试和 600 英尺相比），但将精度提高到 50 英尺只会在二进制算法中增加 4 次测试和 150 英尺的行程，而顺序算法将需要 20 次测试。
注意 1：实际上，如果测试的成本很高，则使用上述算法对链表进行二进制搜索可能是有意义的。假设测试的成本与列表中的索引不成正比，搜索的复杂性将是O(N)线性搜索和二分搜索，但二分搜索会做O(log N)测试和O(N)步骤，而顺序搜索会做O(N)测试和O(N)步骤。对于足够大的 N，这无关紧要，但对于实际大小的 N，它可能很重要。
根据您实际想要优化的内容，可能有一种方法可以制定出最佳搜索模式。我想你不想优化最坏情况的时间，因为对于许多搜索策略来说最慢的情况是在休息的最后一刻，而二分搜索在这里实际上相当不错——你走到最后而不改变方向，而且你不会做太多的停留。
您可能会考虑不同的二叉树，并且可能会计算出找到叶子所需的平均时间。二分搜索是一种树，边走边测试也是如此——一棵非常不平衡的树，其中每个节点至少有一个叶子连接到它上面。
沿着这样一棵树前行时，您总是从正在行走的路线的一端或另一端开始，在进行测量之前先走一段距离，然后根据结果和树，停止或重复该过程并缩短线，你在它的一端或另一端。
这为您提供了可以使用动态编程进行攻击的东西。假设您已经解决了最多 N 段长度的问题，因此您知道这些长度的最佳解决方案的成本。现在您可以为 N+1 段制定最佳解决方案。考虑以 N+1 种可能的方式将 N+1 个片段分成两部分。对于每一种这样的方式，计算出移动到其决策点并进行测量的成本，然后将决策点两侧的段的两个部分的最佳可能解决方案的成本相加，可能加权以考虑最终进入这些部分的可能性。通过考虑这 N+1 种可能的方式，您可以找出拆分 N+1 段的最佳方式及其成本，并继续下去，直到您为实际拥有的段数找到最佳解决方案。
实际上，二进制搜索可以应用在这里，但有一些变化。我们必须计算的不是中心，而是要访问的最佳位置。
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）很小，完整的蛮力将帮助你。否则，您可以尝试使用遗传算法或其他简单的方法。
步长精度 = 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