موضوع مقاله: جستجوی مینیمم بازه‌ای | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # جستجوی مینیمم بازه‌ای | مقدمه: الگوریتم جستجوی مینیمم بازه‌ای در علوم و مهندسی کامپیوتر کاربردهای فراوانی دارند. | ## بخش 1: جستجوی مینیمم بازه‌ای | از جمله آنان می‌توان به یافتن پایین‌ترین والد مشترک (مثلا در درخت یا هرم یا …) یا طولانی‌ترین پیشوند مشترک (LCP) اشاره کرد. به عنوان مثال ، وقتی ، آنگاه پاسخ به سؤال از دامنه برای زیر مجموعه A برابر است با ۷. اما در واقعیت از ۰ آغاز می‌شوند) الگوریتم‌ها راه حل بدیهی در یک مجموعه رایج، آرایه A استاتیک است، یعنی عناصر در طی یک سری پرس و جوها درج یا حذف نمی‌شوند؛ و جستجوهای داده شده باید به صورت درجا پاسخ داده شوند (یعنی کل مجموعه نمایش داده‌ها از قبل با الگوریتم مشخص نیست) در این حالت، پیش پردازش مناسب آرایه در یک داده ساختار، پاسخ سریع تر پرس و جو را تضمین می‌کند. یک راه حل ساده این است که پاسخ تمام جستجوهای ممکن را از قبل حساب کنیم، یعنی مینیمم تمام زیر مجموعه‌های A، و این موارد را در یک آرایه B ذخیره کنید به طوری که [B[i, j] = min(A[i…j) ؛ سپس با استفاده از جستجوی آرایه در B یک جستجوی مینیمم در زمان ثابت حل می‌شود. تعداد (Θ(n² جستجوی مختلف روی آرایه‌ای به طول n وجود دارد، و پاسخ به این سوالات را می‌توان در زمان (Θ(n² توسط برنامه‌نویسی پویا بدست آورد. راه حل با استفاده از زمان ثابت و حافظه خطی + جدول نتیجه برای ۰ ۱ ۲ ۳ ۱ ۱ ۱ ۱ ۱ ۲ ۲ ۳ ۳ ۷ ۳ ۳ ۳ ۳ ۷ ۴ ۴ ۵ ۶ ۷ ۵ ۵ ۶ ۷ ۷ ۶ ۶ ۷ ۷ ۷ ۷ ۷ ۷ ۷ ۷ ۸ ۸ ۷ ۷ ۷ ۹ ۹ ۷ ۷ ۷ مانند راه حل بالا، پاسخ دادن به این سؤالات در زمان ثابت با نتایج از پیش محاسباتی حاصل می‌شود. با این حال، این آرایه جستجوهای مینیمم از پیش محاسبه شده را برای محدوده‌هایی که اندازه آن‌ها توانی از ۲ است برای همه عناصر ذخیره می‌کند. اکنون با تقسیم آن به دو پرس و جو جداگانه می‌توان به پرس و جو (RMQ A(l,r پاسخ داد: یکی پرس و جو از پیش محاسبه شده با دامنه از l تا بالاترین مرز کوچکتر از r (که طول این بازه توانی از ۲ است). مورد دیگر عبارت است از یک بازه با همان طول که r آن را به عنوان مرز سمت راست خود دارد. این فواصل ممکن است با هم هم پوشانی داشته باشند، اما با توجه به اینکه مینیمم به جای جمع، محاسبه می‌شود، این مهم نیست. نتیجه کلی را می‌توان در زمان ثابت بدست آورد زیرا می‌توان به این دو پرس و جو در زمان ثابت پاسخ داد و تنها کاری که باقی مانده‌است ، انتخاب عنصر کوچکتر بین دو عنصر جواب این دو نتیجه است. | ## بخش 2: جستجوی مینیمم بازه‌ای | (که حتی ممکن است یکی باشند) راه حل با استفاده از زمان لگاریتمی و حافظه خطی این راه حل RMQ را در (O(log n پاسخ می‌دهد. داده ساختار آن حافظه‌ای از مرتبهٔ (O(n می‌گیرد و از این داده ساختار نیز می‌توان برای پاسخ به جستجوها در زمان ثابت استفاده کرد. سپس عنصر مینیمم برای هر بلوک در (O(n محاسبه می‌شود و مینیمم‌ها در یک آرایه جدید ذخیره می‌شوند. اکنون RMQها را می‌توان با مراجعه به بلوک‌های حاوی مرز سمت چپ و راست بازه داده شده در طرفین، و تمام بلوک‌های موجود در زمان لگاریتمی پاسخ دهید: دو بلوک حاوی مرزها را می‌توان به سادگی جستجو کرد. مینیمم تمام بلوک‌هایی که به‌طور کامل در محدوده موجود است و دو مینیمم ذکر شده در بالا، برای پاسخ به پرس و جو باید مقایسه شوند. از آنجا که آرایه به بلوک‌هایی با اندازه تقسیم شده‌است، حداکثر بلوک وجود خواهند داشت که کاملاً در داخل محدوده قرار دارند. به عنوان مثال، با استفاده از آرایه [A = [۰٬۵٬۲٬۵٬۴٬۳٬۱٬۶٬۳ و اندازه بلوک ۳ (فقط برای اهداف مصور) آرایه مینیمم [A' = [۰٬۳٬۱ را برمی‌گرداند. راه حل با استفاده از زمان ثابت و حافظه خطی با استفاده از راه حل فوق ، زیر محدوده‌های داخل بلوک‌هایی که به‌طور کامل در آن محدوده قرار ندارند ، هنوز هم باید در زمان ثابت پاسخ داده شوند. با نگه داشتن درختان دکارتی برای تمام بلوک‌های موجود در آرایه ، زمان ثابت حاصل می‌شود. تعدادی از مشاهدات: بلوک‌های دارای درختان ایزومورفیک یا یکریخت دکارتی نتیجه یکسان را برای همه جستجوهای موجود در آن بلوک می‌دهند. برای جستجوی بهینهٔ نتایج، درخت دکارتی (ردیف) مربوط به یک بلوک خاص باید در زمان ثابت مورد قرار گیرد. | ## بخش 3: جستجوی مینیمم بازه‌ای | راه حل این است که نتایج را برای کلیه درختان در یک آرایه ذخیره کرده و یک تصویرسازی و طرح‌ریزی منحصر به فرد از درختان باینری به اعداد صحیح برای آدرس دهی پیدا کنید. این کار را می‌توان با انجام یک پیمایش درخت روی درخت و اضافه کردن گره‌های برگ بدست آورد به طوری که هر گره موجود در درخت دکارتی دقیقاً دو فرزند داشته باشد. سپس عدد صحیح با به نمایش گذاشتن هر گره درونی به عنوان یک بیت ۰ و هر برگ به عنوان بیت ۱ در یک بیت کلمه (با عبور دوباره درخت به صورت سطح به سطج) ایجاد می‌شود. برای فعال کردن دسترسی تصادفی در زمان ثابت به هر درخت، درختانی که در آرایه اصلی موجود نیستند نیز باید در آرایه درج شوند. توجه کنید که درخت اول و سوم دارای یک طرح مشابه هستند، بنابراین دقیقاً دو مجموعه نمایش داده شده از پیش محاسبه شده در جدول در سمت چپ وجود دارد. محاسبه پایین‌ترین جد مشترک در یک درخت RMQها می‌توانند برای حل مسئله پایین‌ترین جد مشترک استفاده شوند و به عنوان ابزاری برای بسیاری از کارها در تطابق دقیق و تقریبی رشته استفاده می‌شوند. query از یک درخت ریشه دار و دو گره عمیق‌ترین گره (که ممکن است یا باشد) را در مسیرهای ریشه به هر دو بازمی‌گرداند؛ و گابوو ، بنتلی و تارجان (۱۹۸۴) نشان دادند که مسئله LCA می‌تواند در زمان خطی به مسئله RMQ تقلیل یابد. الگوریتم جستجوی مینیمم بازه‌ای در علوم و مهندسی کامپیوتر کاربردهای فراوانی دارند. از جمله آنان می‌توان به یافتن پایین‌ترین والد مشترک (مثلا در درخت یا هرم یا …) یا طولانی‌ترین پیشوند مشترک (LCP) اشاره کرد. محاسبه طولانی‌ترین پیشوند مشترک در یک رشته این مفهوم در برنامه‌های بسیاری بکار می‌رود. در زمینه نمایه سازی متن، از RMQها می‌توان برای یافتن LCP (طولانی‌ترین پیشوند مشترک) استفاده کرد، جایی که LCP پسوندهایی را که در شاخص‌های و در شروع می‌شود محاسبه می‌کند. | ## جمع‌بندی | پس از محاسبه این ساختارهای داده، و پردازش RMQ کامل می‌شود، طول LCP عمومی را می‌توان در زمان ثابت با فرمول محاسبه کرد: ، جایی که ما برای سادگی فرض می‌کنیم که (در غیر این صورت مبادله می‌کنیم).