...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Control and Optimization >Search games with multiple hidden objects
【24h】

Search games with multiple hidden objects

机译：搜索带有多个隐藏对象的游戏

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider a class of zero-sum search games in which a Searcher seeks to minimize the expected time to find several objects hidden by a Hider. We begin by analyzing a game in which the Searcher wishes to find k balls hidden among n > k boxes. There is a known cost of searching each box, and the Searcher seeks to minimize the total expected cost of finding all the objects in the worst case. We show that it is optimal for the Searcher to begin by searching a k-subset H of boxes with probability ν(H), which is proportional to the product of the search costs of the boxes in H. The Searcher should then search the n - k remaining boxes in a random order. A worst-case Hider distribution is the distribution ν. We distinguish between the case of a smart Searcher who can change his search plan as he goes along and a normal Searcher who has to set out his plan from the beginning. We show that a smart Searcher has no advantage. We then show how the game can be formulated in terms of a more general network search game, and we give upper and lower bounds for the value of the game on an arbitrary network. For 2-arc connected networks (networks that cannot be disconnected by the removal of fewer than two arcs), we solve the game for a smart Searcher and give an upper bound on the value for a normal Searcher. This bound is tight if the network is a circle.
机译：我们考虑一类零和搜索游戏，搜索者在其中寻求最大程度地减少寻找被藏身者隐藏的对象的预期时间。我们首先分析一个游戏，搜索者希望在n> k个盒子中找到k个隐藏的球。搜索每个框的成本是已知的，并且搜索器将在最坏的情况下最小化查找所有对象的总预期成本。我们表明，对于搜索者而言，最佳方法是首先搜索概率为ν（H）的盒子的k个子集H，该子集H与盒子中H的搜索成本的乘积成比例。然后，搜索者应搜索n -以随机顺序剩余k个盒子。最坏情况的Hider分布是分布ν。我们区分了聪明的Searcher和可以从头开始制定计划的普通Searcher的情况，后者可以随其改变搜索计划。我们表明，聪明的搜索者没有优势。然后，我们展示了如何根据更通用的网络搜索游戏来表述游戏，并给出了在任意网络上游戏价值的上限和下限。对于2弧形连接的网络（无法通过移除少于两个弧线而无法断开的网络），我们为智能搜索器解决了该游戏，并为普通搜索器提供了一个上限。如果网络是一个圆，则此边界是紧密的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号