A Combinatorial Model of Two-Sided Search
A Combinatorial Model of Two-Sided Search
复制标题
双边搜索的组合模型
DOI：
10.1007/978-3-662-49192-8_12
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
V. Lebedev
中科院分区：
文献类型：
--
作者：
Harout K. Aydinian;F. Cicalese;C. Deppe;V. Lebedev
我们研究了一种新的组合群测试模型：待发现的项目（即目标）占据图中的一个未知节点。在每个时刻，我们可以测试（或查询）节点的一个子集，并了解目标是否占用了这些节点中的任何一个。在测试结果可用后，目标可以立即移动到与其当前位置相邻的任何节点。当我们能够以某种预定义的精度（预先确定的参数）定位对象时，搜索就结束了，即指示一组[Formula: see text]节点，其中包含对象的位置。本文研究了与上述模型相关的两类问题：(i)存在上述意义上的搜索策略的精度参数的最小值是什么；（ii）在给定精度的情况下，能确定目标位置的最少测试次数是多少？我们将路径、循环和树作为基础图来研究这些问题，并为上述问题提供严密的答案。我们还考虑了该问题的一个限制变体，其中目标的移动次数是有界的。
We study a new model of combinatorial group testing: the item to be found (a.k.a. the target) occupies an unknown node in a graph. At each time instant, we can test (or query) a subset of the nodes and learn whether the target occupies any of such nodes. Immediately after the result of the test is available, the target can move to any node adjacent to its present location. The search finishes when we are able to locate the object with some predefined accuracy [Formula: see text] (a parameter fixed beforehand), i.e., to indicate a set of [Formula: see text] nodes that includes the location of the object. In this paper we study two types of problems related to the above model: (i) what is the minimum value of the accuracy parameter for which a search strategy in the above sense exists; (ii) given the accuracy, what is the minimum number of tests that allow to locate the target. We study these questions on paths, cycles, and trees as underlying graphs and provide tight answers for the above questions. We also consider a restricted variant of the problem, where the number of moves of the target is bounded.