دانلود رایگان مقاله کاربردهای تحقیق در عملیات تحقیقات دو بخشی

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.