Searching a Variable Speed Network
Searching a Variable Speed Network
复制标题
搜索变速网络
DOI：
10.1287/moor.2013.0634
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
T. Lidbetter
中科院分区：
文献类型：
--
作者：
S. Alpern;T. Lidbetter
一个点根据某种未知的概率分布位于网络上。从网络的指定根开始，搜索者以取决于其位置和方向的速度移动以找到该点。他寻求随机搜索算法，使预期搜索时间最小化。这相当于将问题建模为零和捉迷藏游戏，其值称为网络的搜索值。本文对树的搜索值作了一个新的直接的推导，证明了它等于树的最小遍历时间与一个称为其斜率的量之和的一半。树的倾斜度是从根到叶节点所花费的时间与从叶节点到根所花费的时间之间的差在叶节点上的平均值。这种差异可以解释为叶节点的高度，假设上坡比下坡慢。然后，我们应用这个公式，以获得许多结果一般网络。我们还介绍了一种新的一般方法，比较搜索值的网络，不同的一个弧。一些简单的网络具有非常复杂的最优策略，需要混合连续的纯策略。我们的许多结果推广了S. Gal，但并非所有这些结果都可以推广。
A point lies on a network according to some unknown probability distribution. Starting at a specified root of the network, a Searcher moves to find this point at speeds that depend on his location and direction. He seeks the randomized search algorithm that minimizes the expected search time. This is equivalent to modeling the problem as a zero-sum hide-and-seek game whose value is called the search value of the network. We make a new and direct derivation of an explicit formula for the search value of a tree, proving that it is equal to half the sum of the minimum tour time of the tree and a quantity called its incline. The incline of a tree is an average over the leaf nodes of the difference between the time taken to travel from the root to a leaf node and the time taken to travel from a leaf node to the root. This difference can be interpreted as height of a leaf node, assuming uphill is slower than downhill. We then apply this formula to obtain numerous results for general networks. We also introduce a new general method of comparing the search value of networks that differ in a single arc. Some simple networks have very complicated optimal strategies that require mixing of a continuum of pure strategies. Many of our results generalize analogous ones obtained for constant velocity (in both directions) by S. Gal, but not all of those results can be extended.