首页> 外文会议>Principles and practice of constraint programming >Bounding an Optimal Search Path with a Game of Cop and Robber on Graphs
【24h】

Bounding an Optimal Search Path with a Game of Cop and Robber on Graphs

机译:在图上用Cop和Robber博弈界定最优搜索路径。

获取原文
获取原文并翻译 | 示例

摘要

In search theory, the goal of the Optimal Search Path (OSP) problem is to find a finite length path maximizing the probability that a searcher detects a lost wanderer on a graph. We propose to bound the probability of finding the wanderer in the remaining search time by relaxing the problem into a stochastic game of cop and robber from graph theory. We discuss the validity of this bound and demonstrate its effectiveness on a constraint programming model of the problem. Experimental results show how our novel bound compares favorably to the DMEAN bound from the literature, a state-of-the-art bound based on a relaxation of the OSP into a longest path problem.
机译:在搜索理论中,最佳搜索路径(OSP)问题的目标是找到一条有限长度的路径,以最大化搜索者在图上检测到丢失的流浪者的可能性。我们建议通过将问题放宽到图论中的警察和强盗的随机博弈中来限制在剩余搜索时间内找到流浪者的概率。我们讨论此边界的有效性,并在问题的约束编程模型上证明其有效性。实验结果表明,我们的新型绑定与文献中的DMEAN绑定相比具有优势,DMEAN绑定是基于OSP松弛到最长路径问题的最新绑定。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号