论文标题
在线搜索最大通量
Online Search with Maximum Clearance
论文作者
论文摘要
我们研究移动代理必须在有界或无限的环境中找到隐藏目标的设置，而没有有关HIDER位置的信息。特别是，我们考虑在线搜索，其中搜索策略的性能通过其最坏情况的竞争比率进行评估。我们介绍了一个多标准搜索问题，其中搜索者在其分配的搜索时间上有预算，目的是设计具有竞争力高效，尊重预算并最大化总搜索的策略。我们为线条和星环境提供了分析上最佳的策略，并为通用网络提供了有效的启发式方法。
We study the setting in which a mobile agent must locate a hidden target in a bounded or unbounded environment, with no information about the hider's position. In particular, we consider online search, in which the performance of the search strategy is evaluated by its worst case competitive ratio. We introduce a multi-criteria search problem in which the searcher has a budget on its allotted search time, and the objective is to design strategies that are competitively efficient, respect the budget, and maximize the total searched ground. We give analytically optimal strategies for the line and the star environments, and efficient heuristics for general networks.
