موضوع مقاله: جستجوی بازه‌ای | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # جستجوی بازه‌ای | مقدمه: به عنوان مثال، اگر S، مجموعه‌ای از نقاط باشد که هریک متناظر با مختصات یک شهر است، یک نوع مسئلهٔ هندسی مورد نظر، یافتن شهرهایی که در محدودهٔ طول و عرض جغرافیایی داده شده واقع‌اند، می‌باشد. | ## بخش 1: جستجوی بازه‌ای | مسئلهٔ جستجوی بازه‌ای و داده ساختارهایی که آن را حل می‌کنند، مسئله‌ای اساسی در هندسه محاسباتی است. این مسئله در حوزه‌هایی مانند سیستم‌های اطلاعات جغرافیایی (GIS)، طراحی به کمک کامپیوتر (CAD) و پایگاه داده‌ها کاربرد دارد. انواع صورت‌های گوناگونی از این مسئله وجود دارد که به تبع آن داده ساختارهای گوناگونی مورد استفاده قرار داده می‌گیرند.Agarwal, P. 1–56 برای داشتن راه‌حل بهینه، موارد مختلفی باید مدنظر قرار داده شوند از جمله: نوع اشیای مورد جستجو: الگوریتم‌ها بر اساس نوع اشیای مورد بررسی انتخاب می‌شوند، برای مثال می‌توان نقاط، خطوط، چندضلعی‌ها را مورد بررسی قرار داد. بازه‌هایی که تاکنون بیشتر مورد بررسی قرار گرفته‌اند و مسائل حل شده با آن‌ها مستطیل‌های محوری (جستجوی بازه‌ای قائم)، کره‌ها و دایرهها، نیم‌فاصلهله‌ها هستند. سؤال مطرح شده: اگر بخواهیم لیست اشیایی را که مجدودهٔ سؤالات را تقسیم می‌کنند گزارش کنیم، آنگاه مسئله تبدیل به یک گزارش بازه‌ای خواهد شد. اگر بخواهیم تنها تعداد اشیایی که با بازه تقاطع دارند را بررسی کنیم، آنگاه با مسئلهٔ شمارش بازه‌ای مواجه‌ایم. | ## بخش 2: جستجوی بازه‌ای | تفاوت جستجوی بازه‌ای پویا با جستجوی بازه‌ای ایستا: در حالت ایستا، مجموعهٔ S، از ابتدا مشخص است و تا پایان تغییری نمی‌کند. مفهوم جستجوی بازه‌ای آفلاین: هم مجموعهٔ اشیا و هم مجموعهٔ سؤالات از ابتدا مشخص هستند. اگر اندازهٔ خروجی را k در نظر بگیریم، جان بنتلی با استفاده از یک درخت کی‌دی توانست در زمان (پیچیدگی زمانی) و با حافظهٔ این مسئله را حل کند.Bentley, Jon (1975). در حالی‌که در مدل ماشین اشاره‌گر نتایج بالا حاصل شده بودند، با تغییر مدل به مدل رَم، پیشرفت‌های بیشتری نیز حاصل شد. برنارد چازل توانست با استفاده از داده ساختاری به نام درخت بازه‌ای فشرده، در و با حافظهٔ مسئلهٔ شمارش بازه‌ها را حل کند. لازم است ذکر شود که کمی بعد، جوزف جاجا و دیگران توانستند این مسئله را در زمان بهتری نیز حل کنند. در صورتی که سر یا ته یکی از بازه‌ها بی‌نهایت باشد، مسئله سه‌بعدی خواهد بود و در صورتی که هر دوی آنها بی‌نهایت باشند، مسئله دوبعدی است. | ## بخش 3: جستجوی بازه‌ای | جستجوی بازه‌ای پویا در حالی‌که در جستجوی بازه‌ای ایستا مجموعهٔ S از پیش تعیین شده‌است، در جستجوی بازه‌ای پویا با حذف یا اضافه شدن نقاط مواجه می‌شویم. هر دو نسخهٔ افزایشی و کاهشی در زمان قابل حل هستند، اما هنوز مشخص نیست که آیا جستجوی بازه‌ای کلی را نیز می‌توان با این پیچیدگی زمانی حل کرد یا خیر.Willard, Dan (1985). اگر برای هر دسته یک رنگ در نظر بگیریم، آنگاه صورت مسئله تبدیل به تعداد رنگ‌های موجود در آن بازه می‌شود. اگر از z به سمت چپ بازه (به سمت u) حرکت کنیم ، زیردرخت فرزند چپ را به بازه‌ی کنونی اضافه میکنیم. بالعکس، اگر از z به سمت راست بازه (به سمت v) حرکت کنیم، زیردرخت فرزند چپ را به بازه‌ی کنونی میفزاییم. چون درخت ما یک درخت دودویی جستجوی متوازن است، این عملیات حداکثر به اندازه‌ ارتفاع درخت یعنی به طول می‌انجامد. کاربردها جستجوی بازه‌ای و جستجوی بازه‌ای قائم، علاوه بر هندسهٔ محاسباتی، در سؤالات بازه‌ای خصوصاً در پایگاه‌های داده کاربردهای فراوانی دارند. | ## جمع‌بندی | برای مثال مشخص کردن سطرهایی از پایگاه دادهٔ حساب‌های بانکی با جستجوی بازه‌ای مدل می‌شود و مشخص کردن سطرهایی از پایگاه دادهٔ حساب‌های بانکی که متعلق به افراد بین سنین ۲۰ تا ۳۰ است و موجودی حساب آنها بین ۱۰۰۰ تا ۲۰۰۰ دلار است، با جستجوی بازه‌ای رنگی دوبعدی مدل می‌شود که سن و موجودی حساب این دو بعد می‌باشند.