Search for an immobile hider in a known subset of a network (Q2328862): Difference between revisions

The paper under review is to concern with the problem of finding an unknown hiding point x on a known metric network \(Q\) by tracing out a path at unit speed. The hiding point x might be the midpoint of an arc, not necessary a node; arcs \(\alpha\) have given lengths \(\lambda (\alpha)\) as the closed interval \([0, \lambda (\alpha)]\); extend \(\lambda\) to the Lebesgue measure on this closed interval on all of metric network \(Q\). Minimizing the time \(T\) required to reach \(x\) is the problem which is equivalent to minimizing the length of the search path ending at \(x\). The paper under review provides a new concept of a signed metric \(d_H(a, b)\) of \(Q\) and the \(H\)-radius \(\rho_H (S) =\min_{a\in H} \max_{b\in S} d_H(a, b)\). \textit{S. Gal} [Search games. New York etc.: Academic Press (1980; Zbl 0439.90102)] originally showed that the value \(V\) of the game \(G(Q, H, S)\) is \(\lambda (Q)\) for \(H=Q\) and \(S\) a singleton. The main result Theorem 3 of the paper gives that the value \(V\) of the game \(G(Q, H, S)\) is \(\lambda (H) - d_H (S)/2 = \lambda (H) - \rho _H (S)\). Section 2 presents the literature on searching problem, by Gal [loc. cit.] on a tree, by \textit{J. H. Reijnierse} and \textit{J. A. M. Potters} [Int. J. Game Theory 21, No. 4, 385--394 (1993; Zbl 0774.90102)] on weakly cyclic network, and enlarging the searcher's starting set \(S\) to all of \(Q\) by \textit{A. Dagan} and \textit{S. Gal} [Networks 52, No. 3, 156--161 (2008; Zbl 1180.91056)]. Section 3 initiates the \(H\)-distance \(d_H\), the \(H\)-diameter of \(S\) and the \(H\)-radius of \(S\), and presents Theorem 3 the main result of the paper. Section 4 begins various forms and contexts as Theorem 12.3.1 of \textit{R. Isaacs} [Differential games. Moskau: Verlag `Mir' (1965; Zbl 0152.38407)] and the proof of Theorem 3 for comparing the length of a path starting and ending at points of \(S\) and the time taken for the path \(P\) to reach the point \(x\) for the searcher, the optimal strategy for the hider in Section 5 gets the other side of the inequality to complete the proof of Theorem 3. Section 6 gives a family of examples to illustrate various cases of optimal strategies in Theorem 3 for \(r=s=3.5, r=1/2\) and \(s=2, r=1/4\) and \(s=1/2\) cases. The conclusion in the last section summarize a complete solution to the problem for trees. It remains open to amenable generalization on expanding search, variable speed search, turning costs, and combined search and travel costs.