کاربردهای تحقیق در عملیات پژوهش های دو بخشی Operations Research Applications of Dichotomous Search

1. Introduction Dichotomous search, as the name indicates, refers to algorithmic procedures that search for a target in an unknown location within an interval (the interval of uncertainty, or the search interval) by repeatedly dividing the interval into two parts. At each iteration, the searcher selects a point in the search interval and places there a query, determining at which side of the chosen point the target is located. This approach is ubiquitous and it is applied naturally not just by sophisticated scientists but also in everyday intuitive trial and error experimentation. In the simplest form of dichotomous search, the searcher has no prior information on where the target is located (or assumes it is uniform over the interval of uncertainty), and the goal is to minimize the worst-case or expect cost of the search. In this simplest form, dichotomous search is reduced to the well-known binary search where the search interval is repeatedly halved. This survey focuses on more sophisticated implementations of dichotomous search, for example when there is some prior information on the target location, when facing search constraints, or under specific forms of the objective function. Formally, we consider search over ordered sets. The generic form of such a problem is the following: An object (the target, or the search key) lies at location x in the initial interval of uncertainty, {1, . . . , N}. Queries for the object are sequentially conducted. Queries are comparison questions, presenting an integer y and returning whether or not x ≤ y, thus creating a smaller interval of uncertainty. The objective is to minimize the expected cost of the search. The literature on dichotomous search comes from several disciplines – computer science, applied mathematics, operations research, statistics, industrial engineering and economics. This paper surveys dichotomous search problems and solutions in the area of Operations Research. For completeness we also briefly describe the closely-related theoretical contributions in other areas, mainly Computer Science. There are two relevant earlier surveys concerning dichotomous search. Nagaraj (1997) surveys the literature on computational methods for optimal binary trees, focusing on efficient algorithms, bounds and approximations. For completeness we briefly describe this necessary background. The more recent survey Rytter (2005) concentrates on Huffman tree problems, while very briefly relating to the alphabetic tree problem. It also includes a detailed illustration of the proof of the algorithm of Garsia and Wachs (1977) for the alphabetic tree problem. Our mode of description differs from the above-mentioned surveys. We cover the literature by classifying it into sub-topics and focusing on each contribution separately. We add pointers to relevant results that focus on other variations of the problem. The order in each part is chronological, naturally creating a logical flow of the developments.