SEARCH PROBLEM WITH TWO LEVELS OF EXAMINATION COSTS
Kensaku Kikuta · Scientiae mathematicae Japonicae · 2009
There is an (immobile) object in a node except for a specified node, with a priori probabilities. A seeker starts at the specified node and examines each node until he finds an object, traveling along edges. Associated with an examination of a node is the examination cost, and associated with a movement from a node to a node is a traveling cost. A strategy for the seeker is an ordering of nodes in which the seeker examines each node. The purpose of the seeker is to find a strategy which minimizes the expected cost. Necessary conditions for a strategy to be optimal are presented. Special cases are solved. 1 Introduction and preliminaries. An optimization problem studied in this paper is a search problem on a finite and connected graph: There is an (immobile) object in a node except for a specified node, with a priori probabilities. A seeker starts at the specified node and examines each node until he finds an object, traveling along edges. Associated with an examination of a node is the examination cost, and associated with a movement from a node to a node is a traveling cost. A strategy for the seeker is an ordering of nodes in which the seeker examines each node. The purpose of the seeker is to find a strategy which minimizes the expected cost for finding the object. (Gluss 1961) studied this problem and found a solution approximately when the graph is linear and the seeker is at a terminal node at first. (Kikuta 1990) studied this problem when the graph is a rooted tree with two branches and the seeker is at the root at first. (Lossner and Wegener 1982) studies a more general problem and got sufficient conditions in which critical quantities are given for finding a node to be examined in the next step. Our problem treats a special case of its general model and this paper intends to analyze properties of optimal strategies in more detail, which depends on special structure of the underlying network. In (Alpern and Gal 2003), a game version of this problem is commented. (Ruckle 1983) introduces many search games on graphs. It is difficult to find an exact analytical solution for this problem. On the other hand, imagine a search for the traces of a lost ship in the sea. In some regions, they could search only by patrol boats, and in other regions they must use helicopters as well as patrol boats. It costs much when they must use helicopters and boats. When they commit helicopters, extra set-up cost is required. In this paper we assume that the nodes are classified into two groups depending on the examination costs, and then the edges are also classified into three groups depending on the examination costs and the traveling costs. Necessary conditions are presented for a strategy to be optimal. Properties of optimal strategies are induced from the necessary conditions.