A general framework for searching on a line
A general framework for searching on a line
复制标题
在线搜索的通用框架
DOI：
10.1016/j.tcs.2017.08.023
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
J. Carufel
中科院分区：
文献类型：
--
作者：
P. Bose;J. Carufel
考虑下面的经典搜索问题：目标位于距离原点D处的直线上。从原点开始，搜索者必须以最小的竞争成本找到目标。文献中研究的经典竞争成本是搜索者与D之间的距离之比。注意，当D没有给出下界时，该问题不存在竞争搜索策略。因此，所有竞争搜索策略都需要某种形式的d下界。我们开发了一个通用框架，最优地解决了这个搜索问题的几个变体。框架允许我们实现最优竞争等先前研究变异的搜索成本:(1)目标是固定的,每一步搜索者的成本是一个常数乘以步骤的长度,(2),目标是固定的,搜索者的成本每一步一步的长度加上一个固定的常数(通常称为成本),(3)目标运动和搜索者的成本每一步一步的长度。我们的主要贡献是，该框架允许我们为该问题的变体推导出最优竞争搜索策略，这些问题在文献中没有解决方案，例如：(1)目标是固定的，搜索者在每一步的成本是α 1 x+ β 1，从原点移动距离x和α 2 x+ β 2，返回常数为α 1， α 2, β 1，β 2,(2)，其中目标在移动，搜索者在每一步的成本是一个常数乘以步骤的长度加上一个固定的常数回合成本。请注意，后一种变体可以有几种解释，这取决于回合成本代表什么。例如，如果回合成本代表搜索者转弯所需的时间，那么这就会对移动目标的位置产生影响。另一方面，转弯成本可以表示瞬时转弯所需的燃料量，从而不影响目标的位置。我们的框架解决了所有这些变化。
Consider the following classical search problem: a target is located on a line at distance D from the origin. Starting at the origin, a searcher must find the target with minimum competitive cost. The classical competitive cost studied in the literature is the ratio between the distance travelled by the searcher and D. Note that when no lower bound on D is given, no competitive search strategy exists for this problem. Therefore, all competitive search strategies require some form of lower bound on D. We develop a general framework that optimally solves several variants of this search problem. Our framework allows us to achieve optimal competitive search costs for previously studied variants such as:(1) where the target is fixed and the searcher's cost at each step is a constant times the length of the step,(2) where the target is fixed and the searcher's cost at each step is the length of the step plus a fixed constant (often referred to as the turn cost),(3) where the target is moving and the searcher's cost at each step is the length of the step. Our main contribution is that the framework allows us to derive optimal competitive search strategies for variants of this problem that do not have a solution in the literature such as:(1) where the target is fixed and the searcher's cost at each step is α 1 x+ β 1 for moving distance x away from the origin and α 2 x+ β 2 for moving back with constants α 1, α 2, β 1, β 2,(2) where the target is moving and the searcher's cost at each step is a constant times the length of the step plus a fixed constant turn cost. Notice that the latter variant can have several interpretations depending on what the turn cost represents. For example, if the turn cost represents the amount of time for the searcher to turn, then this has an impact on the position of the moving target. On the other hand, the turn cost can represent the amount of fuel needed to make an instantaneous turn, thereby not affecting the target's position. Our framework addresses all of these variations.