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

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

  • نوع فایل : کتاب
  • زبان : انگلیسی
  • ناشر : Elsevier
  • چاپ و سال / کشور: 2018

توضیحات

رشته های مرتبط  مدیریت
گرایش های مرتبط  تحقیق در عملیات
مجله نشریه اروپایی تحقیقات کاربردی – European Journal of Operational Research
دانشگاه Department of Statistics and Operations Research – Tel Aviv University

منتشر شده در نشریه الزویر
کلمات کلیدی بهینه سازی ترکیبی، تحقیق دو بخشی، درخت های الفبایی

Description

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.
اگر شما نسبت به این اثر یا عنوان محق هستید، لطفا از طریق "بخش تماس با ما" با ما تماس بگیرید و برای اطلاعات بیشتر، صفحه قوانین و مقررات را مطالعه نمایید.

دیدگاه کاربران


لطفا در این قسمت فقط نظر شخصی در مورد این عنوان را وارد نمایید و در صورتیکه مشکلی با دانلود یا استفاده از این فایل دارید در صفحه کاربری تیکت ثبت کنید.

بارگزاری