Revisiting the Problem of Searching on a Line
Revisiting the Problem of Searching on a Line
复制标题
重新审视直线搜索问题
DOI：
10.1007/978-3-642-40450-4_18
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Stephane Durocher
中科院分区：
文献类型：
--
作者：
P. Bose;J. Carufel;Stephane Durocher
当给定搜索器初始位置与目标之间的距离 D 的上限和下限时，我们重新讨论在一条线上的未知位置搜索目标的问题。在这项工作之前，对于最坏情况下任何搜索策略可实现的最佳竞争比，仅知道渐进界限。我们提出了可实现的精确最佳竞争比的第一个严格界限，根据 D 的给定范围进行参数化，以及实现该竞争比的最佳搜索策略。我们证明这种最优策略是唯一的，并且一般情况下无法精确计算。我们描述了可以准确计算最优策略的条件，如果不能，我们会解释如何有效地使用数值方法。此外，我们回答了几个相关的开放问题，并讨论了如何将这些结果推广到 m 条射线，对于任何 m ≥ 2。
We revisit the problem of searching for a target at an unknown location on a line when given upper and lower bounds on the distance D that separates the initial position of the searcher from the target. Prior to this work, only asymptotic bounds were known for the optimal competitive ratio achievable by any search strategy in the worst case. We present the first tight bounds on the exact optimal competitive ratio achievable, parametrized in terms of the given range for D, along with an optimal search strategy that achieves this competitive ratio. We prove that this optimal strategy is unique and that it cannot be computed exactly in general. We characterize the conditions under which an optimal strategy can be computed exactly and, when it cannot, we explain how numerical methods can be used efficiently. In addition, we answer several related open questions and we discuss how to generalize these results to m rays, for any m ≥ 2.