Search on lines and graphs

In this paper we investigate discrete linear search and graph search problems. It is well-known that the Bounded Discrete Linear Search Problem (BDLSP) can be solved efficiently using a dynamic programming approach. However, we show that its generalization to the graph case-the Graph Search Problem (GSP)-is NP-complete. We further consider the Discrete Linear Search Problem with unbounded search domain (UBDLSP). We first establish that for an optimal policy to exist for a general UBDLSP it is both necessary and sufficient for the double-sided mean of its underlying distribution to be finite. Then, we consider a special class of UBDLSPs-symmetric UBDLSPs-and prove the expanding property of optimal policies for symmetric UBDLSPs. Based on the expanding property, we devise a procedure to approximate, by solving a sequence of finite-truncated BDLSPs, the optimal costs. We prove that the sequence of approximated optimal costs converges to the true optimal cost.