نمایش مبدأ برای جستجوی مینیمم بازه‌ای

[[File:LowesCommon.png|thumb|left|300x200px|alt=A Constructing the corresponding cartesian tree to solve a range minimum query.|مسئله جستجوی مینیمم بازه‌ای کاهش یافته به مسئله پایین‌ترین جد مشترک]]

در علوم کامپیوتر، یک جستجوی میبنیمم بازه‌ای (Range minimum query) الگوریتمی برای یافتن کوچکترین عنصر در یک زیر آرایه (بازه‌ای از یک آرایه) با عناصر قابل مقایسه است.

الگوریتم جستجوی مینیمم بازه‌ای در علوم و [[مهندسی کامپیوتر]] کاربردهای فراوانی دارند. از جمله آنان می‌توان به یافتن [[:en:Lowest common ancestor|پایین‌ترین والد مشترک]] (مثلا در درخت یا هرم یا …) یا [[:en:LCP array|طولانی‌ترین پیشوند مشترک]] (LCP) اشاره کرد. ([[:en:LCP array|لینک خارجی LCP array]])

== تعریف ==
با توجه به یک آرایه [A[1 … n از n اشیاء از یک مجموعه منظم([[خوش ترتیب]]) (مانند اعداد)، جستجوی مینیمم بازه‌ای [RMQ A(l,r) =arg min A[k (با ۱ ≤ l ≤ k ≤ r ≤ n ) موقعیت([[اندیس (معدن)|اندیس]] ) کوچکترین عنصر را در زیربازه‌ی مشخص شده [A[l … r بازمی‌گرداند.

به عنوان مثال ، وقتی {{ریاضی|1=''A'' = [۰٬۵٬۲٬۵٬۴٬۳٬۱٬۶٬۳]}}، آنگاه پاسخ به سؤال از دامنه {{ریاضی|1=''A''[۳ … ۸] = [۲٬۵٬۴٬۳٬۱٬۶]}} برای زیر مجموعه A برابر است با ۷. زیرا A[7] = ۱. و پاسخ، موقعیت کوچکترین عنصر در زیربازهٔ مشخص شده را به ما می‌دهد.
(البته اینجا اندیس‌ها را برای سادگی از یک شروع کردیم. اما در واقعیت از ۰ آغاز می‌شوند)

== الگوریتم‌ها ==
=== راه حل بدیهی ===
در یک مجموعه رایج، آرایه A استاتیک است، یعنی عناصر در طی یک سری پرس و جوها درج یا حذف نمی‌شوند؛ و جستجوهای داده شده باید به صورت درجا پاسخ داده شوند (یعنی کل مجموعه نمایش داده‌ها از قبل با الگوریتم مشخص نیست) در این حالت، پیش پردازش مناسب آرایه در یک داده ساختار، پاسخ سریع تر پرس و جو را تضمین می‌کند. یک راه حل ساده این است که پاسخ تمام جستجوهای ممکن را از قبل حساب کنیم، یعنی مینیمم تمام زیر مجموعه‌های A، و این موارد را در یک آرایه B ذخیره کنید به طوری که [B[i, j] = min(A[i…j) ؛ سپس با استفاده از جستجوی آرایه در B یک جستجوی مینیمم در زمان ثابت حل می‌شود. تعداد (Θ(n² جستجوی مختلف روی آرایه‌ای به طول n وجود دارد، و پاسخ به این سوالات را می‌توان در زمان (Θ(n² توسط [[برنامه‌نویسی پویا]] بدست آورد.

=== راه حل با استفاده از زمان ثابت و حافظه خطی ===
{| class="wikitable floatleft" style="text-align:center"
|+ جدول نتیجه برای {{ریاضی|1=''A'' = [۰٬۵٬۲٬۵٬۴٬۳٬۱٬۶٬۳]}}
! colspan="2" rowspan="2" |
! colspan="4" | {{Mvar|k}}
|-
! ۰
! ۱
! ۲
! ۳
|-
! rowspan="9" | {{Mvar|l}}
! ۱
| ۱
| ۱
| ۱
| ۱
|-
! ۲
| ۲
| ۳
| ۳
| ۷
|-
! ۳
| ۳
| ۳
| ۳
| ۷
|-
! ۴
| ۴
| ۵
| ۶
| ۷
|-
! ۵
| ۵
| ۶
| ۷
| ۷
|-
! ۶
| ۶
| ۷
| ۷
| ۷
|-
! ۷
| ۷
| ۷
| ۷
| ۷
|-
! ۸
| ۸
| ۷
| ۷
| ۷
|-
! ۹
| ۹
| ۷
| ۷
| ۷
|}

مانند راه حل بالا، پاسخ دادن به این سؤالات در زمان ثابت با نتایج از پیش محاسباتی حاصل می‌شود. با این حال، این آرایه جستجوهای مینیمم از پیش محاسبه شده را برای محدوده‌هایی که اندازه آن‌ها توانی از ۲ است برای همه عناصر ذخیره می‌کند. برای هر موقعیت شروع i به تعداد (Θ(log n از این جستجوها وجود دارد، بنابراین اندازه جدول برنامه‌نویسی پویا B برابر با (Θ (n log n است. هر عنصر [B [i, j دارای اندیس مینیمم محدوده [A [i … i + 2^j-1 است. جدول به کمک خاصیت بازگشت از اندیس‌های مینیمم‌ها پر شده‌است.

اگر {{ریاضی|''A''[''B''[''i'', ''j''<nowiki>-1]] ≤ </nowiki>''A''[''B''[''i''+2<sup>''j''-1</sup>, ''j''<nowiki>-1]]</nowiki>}}،

آن گاه {{ریاضی|''B''[''i'', ''j''] {{=}} ''B''[''i'', ''j''-1]}}.

در غیر این صورت، {{ریاضی|''B''[''i'', ''j''] {{=}} ''B''[''i''+2<sup>''j''-1</sup>, ''j''-1]}}.

اکنون با تقسیم آن به دو پرس و جو جداگانه می‌توان به پرس و جو (RMQ A(l,r پاسخ داد: یکی پرس و جو از پیش محاسبه شده با دامنه از l تا بالاترین مرز کوچکتر از r (که طول این بازه توانی از ۲ است). مورد دیگر عبارت است از یک بازه با همان طول که r آن را به عنوان مرز سمت راست خود دارد. این فواصل ممکن است با هم هم پوشانی داشته باشند، اما با توجه به اینکه مینیمم به جای جمع، محاسبه می‌شود، این مهم نیست. نتیجه کلی را می‌توان در زمان ثابت بدست آورد زیرا می‌توان به این دو پرس و جو در زمان ثابت پاسخ داد و تنها کاری که باقی مانده‌است ، انتخاب عنصر کوچکتر بین دو عنصر جواب این دو نتیجه است. (که حتی ممکن است یکی باشند)

=== راه حل با استفاده از زمان لگاریتمی و حافظه خطی ===
این راه حل RMQ را در '''(O(log n''' پاسخ می‌دهد. داده ساختار آن حافظه‌ای از مرتبهٔ '''(O(n''' می‌گیرد و از این داده ساختار نیز می‌توان برای پاسخ به جستجوها در زمان ثابت استفاده کرد. این آرایه ابتدا از نظر مفهومی به بلوک‌هایی با اندازه '''<math>s = \frac{log(n)}{4}</math>''' تقسیم می‌شود. سپس عنصر مینیمم برای هر بلوک در '''(O(n''' محاسبه می‌شود و مینیمم‌ها در یک آرایه جدید ذخیره می‌شوند.

اکنون RMQها را می‌توان با مراجعه به بلوک‌های حاوی مرز سمت چپ و راست بازه داده شده در طرفین، و تمام بلوک‌های موجود در زمان لگاریتمی پاسخ دهید:

دو بلوک حاوی مرزها را می‌توان به سادگی جستجو کرد. عناصر خارج از مرز حتی لازم نیست مورد بررسی قرار گیرند. این کار در زمان لگاریتمی قابل انجام است.

مینیمم تمام بلوک‌هایی که به‌طور کامل در محدوده موجود است و دو مینیمم ذکر شده در بالا، برای پاسخ به پرس و جو باید مقایسه شوند. از آنجا که آرایه به بلوک‌هایی با اندازه '''<math>\frac{log(n)}{n}</math>''' تقسیم شده‌است، حداکثر '''<math>4\frac{n}{log(n)}</math>''' بلوک وجود خواهند داشت که کاملاً در داخل محدوده قرار دارند.

با استفاده از راه حل خطی می‌توان مینیمم کلی را در بین این بلوک‌ها پیدا کرد. این داده ساختار دارای اندازه '''(O(<math>\frac{n}{log(n)}</math> * log(<math>\frac{n}{log(n)}</math>))''' است.

به عنوان مثال، با استفاده از آرایه [A = [۰٬۵٬۲٬۵٬۴٬۳٬۱٬۶٬۳ و اندازه بلوک ۳ (فقط برای اهداف مصور) آرایه مینیمم [A' = [۰٬۳٬۱ را برمی‌گرداند.

=== راه حل با استفاده از زمان ثابت و حافظه خطی ===
با استفاده از راه حل فوق ، زیر محدوده‌های داخل بلوک‌هایی که به‌طور کامل در آن محدوده قرار ندارند ، هنوز هم باید در زمان ثابت پاسخ داده شوند. حداکثر دو بلوک وجود دارد: بلوک حاوی l و بلوک حاوی r . با نگه داشتن درختان دکارتی برای تمام بلوک‌های موجود در آرایه ، زمان ثابت حاصل می‌شود. تعدادی از مشاهدات:
* بلوک‌های دارای درختان [[یک‌ریختی گراف|ایزومورفیک یا یکریخت]] دکارتی نتیجه یکسان را برای همه جستجوهای موجود در آن بلوک می‌دهند.
* تعداد درختان مختلف دکارتی از s گره برابر است با Cs که s'امین عدد کاتالان است.
* بنابراین، تعداد درختان مختلف دکارتی برای بلوک‌ها در محدوده '''{{ریاضی|4<sup>''s''</sup>}}''' قرار دارد.

برای هر درخت این چنینی، نتیجه احتمالی برای همه سؤالات باید ذخیره شود. این به ورودی‌های از مرتبه '''{{math|''s''<sup>2</sup>}}''' یا {{math|{{ریاضی|''O ''}}(log{{sup|2}} ''n'')}} بستگی دارد. این بدان معنی است که اندازه کلی جدول '''(O(n''' است.

برای جستجوی بهینهٔ نتایج، درخت دکارتی (ردیف) مربوط به یک بلوک خاص باید در زمان ثابت مورد قرار گیرد. راه حل این است که نتایج را برای کلیه درختان در یک آرایه ذخیره کرده و یک تصویرسازی و طرح‌ریزی منحصر به فرد از درختان باینری به اعداد صحیح برای آدرس دهی پیدا کنید. این کار را می‌توان با انجام یک [[پیمایش درخت]] روی درخت و اضافه کردن گره‌های برگ بدست آورد به طوری که هر گره موجود در درخت دکارتی دقیقاً دو فرزند داشته باشد. سپس عدد صحیح با به نمایش گذاشتن هر گره درونی به عنوان یک بیت ۰ و هر برگ به عنوان بیت ۱ در یک بیت کلمه (با [[:en:Tree traversal#Breadth-first search / level order|عبور دوباره درخت به صورت سطح به سطج]]) ایجاد می‌شود. این برای هر درخت به اندازه '''<math>\frac{log(n)}{4}</math>''' منجر می‌شود. برای فعال کردن دسترسی تصادفی در زمان ثابت به هر درخت، درختانی که در آرایه اصلی موجود نیستند نیز باید در آرایه درج شوند. آرایه‌ای با شاخص‌های به طول '''<math>\frac{log(n)}{4}</math>''' بیت، اندازه‌ای از مرتبهٔ '''<sup><math>\frac{log(n)}{4}</math></sup> 2''' دارند.

[[پرونده:Example_of_Cartesian_Trees.png|بندانگشتی| نمونه درختان دکارتی برای {{ریاضی|''A'' {{=}} [۰٬۵٬۲٬۵٬۴٬۳٬۱٬۶٬۳]}}. توجه کنید که درخت اول و سوم دارای یک طرح مشابه هستند، بنابراین دقیقاً دو مجموعه نمایش داده شده از پیش محاسبه شده در جدول در سمت چپ وجود دارد.]]

{| class="wikitable" style="text-align:center"
|+ نتایج پیش پردازش برای درخت دکارتی روی لیست A {{math|''A'' {{=}} [۰٬۵٬۲٬۵٬۴٬۳٬۱٬۶٬۳]}}
|-
! rowspan="2" | Index || colspan="3" | 1 || colspan="3" | 2 || colspan="3" | ۳
|-
! ۱ || ۲ || ۳ || ۱ || ۲ || ۳ || ۱ || ۲ || ۳
|-
| 0 || colspan="9" {{sdash}}
|-
| 23 (Bitword 0010111) || 1 || 2 || 3 || {{sdash}} || 2 || 3 || {{sdash}} || {{sdash}} || ۳
|-
| 39 (Bitword 0100111) || 1 || 1 || 1 || {{sdash}} || 2 || 3 || {{sdash}} || {{sdash}} || ۳
|-
| 127 || colspan="9" {{sdash}}
|}

== کاربردها ==
RMQها به عنوان ابزاری برای بسیاری از کارها در تطابق دقیق و تقریبی رشته استفاده می‌شوند. چندین کاربرد را می‌توان در مقاله‌های فیشر و هون (۲۰۰۷) یافت.<ref name="fischer07"><cite class="citation conference">Fischer, Johannes; Heun, Volker (2007). ''A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array''. Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. LNCS. '''4614'''. Springer. pp. &nbsp;459–470. [[Digital object identifier|doi]]:[[doi:10.1007/978-3-540-74450-4_41|10.1007/978-3-540-74450-4_41]].</cite><templatestyles src="Module:Citation/CS1/styles.css"></templatestyles></ref> {{Rp|3}}

=== محاسبه پایین‌ترین جد مشترک در یک درخت ===
RMQها می‌توانند برای [[حل مسئله]] پایین‌ترین جد مشترک<ref name="bender-jalg">{{Cite journal|last=Bender|first=Michael A.|last2=Farach-Colton|first2=Martín|author-link2=Martin Farach-Colton|last3=Pemmasani|first3=Giridhar|last4=Skiena|first4=Steven|author-link4=Steven Skiena|last5=Sumazin|first5=Pavel|year=2005|title=Lowest common ancestors in trees and directed acyclic graphs|url=http://www.cs.sunysb.edu/~bender/pub/JALG05-daglca.pdf|journal=Journal of Algorithms|volume=57|issue=2|pages=75–94|doi=10.1016/j.jalgor.2005.08.001}}</ref> استفاده شوند و به عنوان ابزاری برای بسیاری از کارها در [[الگوریتم جستجوی رشته|تطابق]] دقیق و تقریبی [[الگوریتم جستجوی رشته|رشته استفاده می‌شوند]]. query {{ریاضی|LCA<sub>''S''</sub>(''v'', ''w'')}} از یک درخت ریشه دار {{ریاضی|''S'' {{=}} (''V'', ''E'')}} و دو گره {{ریاضی|''v'', ''w'' ∈ ''V''}} عمیق‌ترین گره {{Mvar|u}} (که ممکن است {{Mvar|v}} یا {{Mvar|w}} باشد) را در مسیرهای ریشه به هر دو {{Mvar|w}} بازمی‌گرداند؛ و {{Mvar|v}} گابوو ، بنتلی و تارجان (۱۹۸۴) نشان دادند که مسئله LCA می‌تواند در زمان خطی به مسئله RMQ تقلیل یابد. از این رو نتیجه می‌گیرد که مانند مسئله RMQ، مسئله LCA می‌تواند در زمان ثابت و حافظهٔ خطی حل شود.<ref name="fischer07"><cite class="citation conference">Fischer, Johannes; Heun, Volker (2007). ''A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array''. Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. LNCS. '''4614'''. Springer. pp. &nbsp;459–470. [[Digital object identifier|doi]]:[[doi:10.1007/978-3-540-74450-4_41|10.1007/978-3-540-74450-4_41]].</cite><templatestyles src="Module:Citation/CS1/styles.css"></templatestyles></ref>

الگوریتم جستجوی مینیمم بازه‌ای در علوم و مهندسی کامپیوتر کاربردهای فراوانی دارند. از جمله آنان می‌توان به یافتن [[:en:Lowest common ancestor|پایین‌ترین والد مشترک]] (مثلا در درخت یا هرم یا …) یا [[:en:LCP array|طولانی‌ترین پیشوند مشترک (LCP)]] اشاره کرد.

=== محاسبه طولانی‌ترین پیشوند مشترک در یک رشته ===
این مفهوم در برنامه‌های بسیاری بکار می‌رود.

در زمینه نمایه سازی متن، از RMQها می‌توان برای یافتن LCP (طولانی‌ترین پیشوند مشترک) استفاده کرد، جایی که {{ریاضی|LCP<sub>''T''</sub>(''i'', ''j'')}} LCP پسوندهایی را که در شاخص‌های {{Mvar|i}} و {{Mvar|j}} در {{Mvar|T}} شروع می‌شود {{ریاضی|LCP<sub>''T''</sub>(''i'', ''j'')}} محاسبه می‌کند. برای این کار ابتدا آرایه پسوند {{Mvar|A}} و آرایه پسوند معکوس {{ریاضی|''A''<sup>−1</sup>}} را محاسبه می‌کنیم. سپس LCP آرایه {{Mvar|H}} را به کمک LCP پسوندهای مجاور در {{Mvar|A}} محاسبه می‌کنیم. پس از محاسبه این ساختارهای داده، و پردازش RMQ کامل می‌شود، طول LCP عمومی را می‌توان در زمان ثابت با فرمول محاسبه کرد: {{ریاضی|1=LCP(''i'', ''j'') = RMQ{{sub|H}}(''A''{{sup|-1}}[''i''] + 1, ''A''{{sup|-1}}[''j''])}}، جایی که ما برای سادگی فرض می‌کنیم که {{ریاضی|1=''A''{{sup|-1}}[''i''] + 1 <= ''A''{{sup|-1}}[''j'']}} (در غیر این صورت مبادله می‌کنیم).<ref name="10.1007/11780441_5">{{Cite book|last=Fischer, J. and V. Heun|authorlink=|year=2006|title=Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE|work=Combinatorial Pattern Matching|volume=4009|pages=36–48|doi=10.1007/11780441_5|series=Lecture Notes in Computer Science|isbn=978-3-540-35455-0}}</ref>

== جستارهای وابسته ==
=== انگلیسی ===
* [[:en:All nearest smaller values|یافتن نزدیکترین عناصر کوچکتر]]
* [[:en:Dynamic programming|برنامه‌نویسی پویا]]
* [[:en:Tree Traversal|پیمایش درخت]]
* [[:en:Range query (data structures)|جستجوی بازه‌ای (داده ساختار)]]
* [[:en:Maxima and minima|بیشینه و کمینه]]

=== فارسی ===
* [[بیشینه و کمینه]]
* [[برنامه‌نویسی پویا]]
* [[پیمایش درخت]]

== منابع ==
{{چپ‌چین}}
* {{Cite journal|last=Berkman|first=Omer|last2=Vishkin|first2=Uzi|author-link2=Uzi Vishkin|year=1993|title=Recursive Star-Tree Parallel Data Structure|url=http://www.dtic.mil/get-tr-doc/pdf?AD=ADA227803|journal=SIAM Journal on Computing|volume=22|issue=2|pages=221–242|doi=10.1137/0222017}}
* {{Cite report|last1=Johannes Fischer|title=Optimal Succinctness for Range Minimum Queries}}
<references group="" responsive="0"/><ref name="fischer07"><cite class="citation conference">Fischer, Johannes; Heun, Volker (2007). ''A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array''. Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. LNCS. '''4614'''. Springer. pp. &nbsp;459–470. [[Digital object identifier|doi]]:[[doi:10.1007/978-3-540-74450-4_41|10.1007/978-3-540-74450-4_41]].</cite><templatestyles src="Module:Citation/CS1/styles.css"></templatestyles></ref>{{پانویس|۲}}
{{پایان چپ‌چین}}

== پیوند به بیرون ==
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Range_Minimum_Query_(RMQ) An article on Range Minimum Queries on TopCoder]
* [http://wcipeg.com/wiki/RMQ Range Minimum Query article on PEGWiki / P3G]
* [http://web.stanford.edu/class/archive/cs/cs166/cs166.1146/lectures/00/Small00.pdf Stanford CS166 RMQ introduction slides]
[[رده:الگوریتم‌های جستجو]]