Network search games with immobile hider, without a designated searcher starting point
Network search games with immobile hider, without a designated searcher starting point
复制标题
带有固定隐藏器的网络搜索游戏，没有指定的搜索者起点
DOI：
10.1007/s00182-008-0116-7
复制
发表时间：
2008
影响因子：
0.6
通讯作者：
S. Gal
中科院分区：
文献类型：
--
作者：
S. Alpern;V. Baston;S. Gal
在Isaacs提出的(零和)搜索对策Γ(G，x)中，搜索者在网络G中选取一点H，搜索者在网络G中选取一条单位速度路径S(T)，其中S(0)=x，最大化搜索者的收益是搜索者找到隐藏者所需的时间T=T(S，H)*=min{t：S(T)*=H}。关于这种博弈的广泛理论已经在文献中得到了发展。本文考虑了相关对策Γ(G)，其中去掉了S(0)=x的要求，允许搜索者自主选择起点。对于G是树的重要情形，Dagan和Gal已经解决了这个问题，而对于带有欧拉网络的树，Alpern已经解决了这个问题。在这里，我们利用由Reijnierse和Potters提出并由Gal完成的关于固定开始对策Γ(G，x)的理论，将这些结果推广到更广泛的网络类别。我们的结果可能更容易被解释为确定从任意起点搜索网络的最佳最坏情况方法。
In the (zero-sum) search game Γ(G, x) proposed by Isaacs, the Hider picks a point H in the network G and the Searcher picks a unit speed path S(t) in G with S(0) = x. The payoff to the maximizing Hider is the time T = T(S, H) = min{t : S(t) = H} required for the Searcher to find the Hider. An extensive theory of such games has been developed in the literature. This paper considers the related games Γ(G), where the requirement S(0) = x is dropped, and the Searcher is allowed to choose his starting point. This game has been solved by Dagan and Gal for the important case where G is a tree, and by Alpern for trees with Eulerian networks attached. Here, we extend those results to a wider class of networks, employing theory initiated by Reijnierse and Potters and completed by Gal, for the fixed-start games Γ(G, x). Our results may be more easily interpreted as determining the best worst-case method of searching a network from an arbitrary starting point.