شجرة البحث الثنائية المثلى

في مسألة الأمثلية الساكنة كما حددها كنوت ، ^{[ 2 ]} لدينا مجموعة من n عنصرًا مرتبًا ومجموعة من${\displaystyle 2n+1}$الاحتمالات. سنرمز للعناصر${\displaystyle a_{1}}$خلال${\displaystyle a_{n}}$والاحتمالات${\displaystyle A_{1}}$خلال${\displaystyle A_{n}}$و${\displaystyle B_{0}}$خلال${\displaystyle B_{n}}$.${\displaystyle A_{i}}$هل احتمال إجراء بحث عن عنصر ما هو${\displaystyle a_{i}}$(أو بحث ناجح ). ^{[ 3 ]} لـ${\displaystyle 1\leq i<n}$،${\displaystyle B_{i}}$هل احتمال إجراء بحث عن عنصر بين${\displaystyle a_{i}}$و${\displaystyle a_{i+1}}$(أو بحث غير ناجح )، ^{[ 3 ]}${\displaystyle B_{0}}$هل احتمال إجراء بحث عن عنصر أقل من قيمة معينة؟${\displaystyle a_{1}}$، و${\displaystyle B_{n}}$هل احتمال إجراء بحث عن عنصر أكبر من${\displaystyle a_{n}}$. هؤلاء${\displaystyle 2n+1}$تشمل الاحتمالات جميع عمليات البحث الممكنة، وبالتالي فإن مجموعها يساوي واحدًا.

تُعرف مسألة الأمثلية الثابتة بأنها مسألة تحسين لإيجاد شجرة البحث الثنائية التي تقلل من متوسط ​​وقت البحث، مع الأخذ في الاعتبار${\displaystyle 2n+1}$الاحتمالات. بما أن عدد الأشجار الممكنة على مجموعة من n عنصرًا هو${\displaystyle {2n \choose n}{\frac {1}{n+1}}}$[ ^{2 ]} وهو أسي في n ، ^فإن البحث بالقوة الغاشمة ليس حلاً ممكناً في العادة.

في عام 1971، نشر كنوت خوارزمية برمجة ديناميكية بسيطة نسبيًا قادرة على بناء الشجرة المثلى إحصائيًا في زمن O ( n² ^{) فقط. [ 2 ]} في هذا العمل، قام كنوت بتوسيع وتحسين خوارزمية البرمجة الديناميكية التي قدمها إدغار جيلبرت وإدوارد ف. مور في عام 1958. ^{[ 4 ]} تطلبت خوارزمية جيلبرت ومور${\displaystyle O(n^{3})}$الوقت و${\displaystyle O(n^{2})}$تم تصميم هذه المساحة لحالة خاصة من إنشاء أشجار البحث الثنائية المثلى (المعروفة باسم مشكلة الشجرة الأبجدية المثلى ^{[ 5 ]} ) والتي لا تأخذ في الاعتبار سوى احتمالية عمليات البحث غير الناجحة، أي${\textstyle \sum _{i=1}^{n}A_{i}=0}$. اعتمد عمل كنوت على الرؤية التالية: تُظهر مشكلة الأمثلية الثابتة بنية فرعية مثالية ؛ أي إذا كانت شجرة معينة مثالية بشكل ثابت لتوزيع احتمالي معين، فيجب أن تكون الأشجار الفرعية اليسرى واليمنى مثالية بشكل ثابت أيضًا لمجموعاتها الفرعية المناسبة من التوزيع (المعروفة باسم خاصية الرتابة للجذور).

لتوضيح ذلك، انظر إلى ما يسميه كنوت "طول المسار الموزون" للشجرة. طول المسار الموزون لشجرة مكونة من n عنصرًا هو مجموع أطوال جميع${\displaystyle 2n+1}$مسارات البحث الممكنة، مُرجّحة باحتمالاتها الخاصة. الشجرة ذات أقصر طول مسار مُرجّح هي، بحكم التعريف، الأمثل إحصائيًا.

_{لكن لأطوال المسارات الموزونة خاصية مثيرة للاهتمام. لنفترض أن E هو} طول المسار الموزون لشجرة ثنائية، _وEL هو طول المسار الموزون لشجرتها الفرعية اليسرى، و ER هو طول المسار الموزون لشجرتها الفرعية اليمنى. ولنفترض أيضًا أن W هو مجموع جميع الاحتمالات في الشجرة. لاحظ أنه عند ربط أي من الشجرتين الفرعيتين بالجذر، يزداد عمق كل عنصر من عناصره (وبالتالي كل مسار من مسارات البحث فيه) بمقدار واحد. لاحظ أيضًا أن عمق الجذر نفسه يساوي واحدًا. هذا يعني أن الفرق في طول المسار الموزون بين الشجرة وشجرتيها الفرعيتين هو بالضبط مجموع كل احتمال في الشجرة، مما يؤدي إلى العلاقة التكرارية التالية:

${\displaystyle E=E_{L}+E_{R}+W}$

يؤدي هذا التكرار إلى حل طبيعي للبرمجة الديناميكية. لنفترض${\displaystyle E_{ij}}$ليكن طول المسار الموزون لشجرة البحث المثلى إحصائياً لجميع القيم بين a _i و a _j ، ولتكن${\displaystyle W_{ij}}$ليكن الوزن الإجمالي لتلك الشجرة، وليكن${\displaystyle R_{ij}}$ليكن فهرس جذرها. يمكن بناء الخوارزمية باستخدام الصيغ التالية:

${\displaystyle {\begin{aligned}E_{i,i-1}=W_{i,i-1}&=B_{i-1}\operatorname {for} 1\leq i\leq n+1\\W_{i,j}&=W_{i,j-1}+A_{j}+B_{j}\\E_{i,j}&=\min _{i\leq r\leq j}(E_{i,r-1}+E_{r+1,j}+W_{i,j})\operatorname {for} 1\leq i\leq j\leq n\end{aligned}}}$

إن التنفيذ الساذج لهذه الخوارزمية يستغرق في الواقع O ( n ³ ) من الوقت، لكن ورقة كنوت تتضمن بعض الملاحظات الإضافية التي يمكن استخدامها لإنتاج خوارزمية معدلة تستغرق O ( n ² ) من الوقت فقط.

بالإضافة إلى خوارزمية البرمجة الديناميكية، اقترح كنوت قاعدتين استدلاليتين لإنتاج أشجار بحث ثنائية شبه مثالية . وكانت دراسة أشجار البحث الثنائية شبه المثالية ضرورية لأن تعقيد الوقت والمساحة في خوارزمية كنوت قد يكون باهظًا عندما${\displaystyle n}$كبير بشكل ملحوظ. ^{[ 6 ]}

يمكن النظر إلى قواعد كنوت على النحو التالي:

• القاعدة الأولى (الجذر الأقصى): ضع الاسم الأكثر تكرارًا في جذر الشجرة، ثم تابع بالمثل على الأشجار الفرعية.
• القاعدة الثانية (التقسيم الثنائي): اختر الجذر بحيث يتم مساواة الوزن الإجمالي للشجرة الفرعية اليسرى واليمنى قدر الإمكان، ثم تابع بالمثل على الأشجار الفرعية.

تُنفذ طرق كنوت الاستدلالية أشجار البحث الثنائية شبه المثلى في${\displaystyle O(n\log n)}$الوقت و${\displaystyle O(n)}$الفضاء. وقد اقترح كورت ميلهورن تحليلًا إضافيًا حول مدى بُعد طرق كنوت الاستدلالية عن الحل الأمثل . ^{[ 6 ]}

في حين أن الوقت O ( n ² ) الذي تستغرقه خوارزمية كنوت أفضل بكثير من الوقت الأسي المطلوب للبحث بالقوة الغاشمة، إلا أنه لا يزال بطيئًا جدًا ليكون عمليًا عندما يكون عدد العناصر في الشجرة كبيرًا جدًا.

في عام 1975، نشر كورت ميلهورن بحثًا يُثبت خصائص مهمة تتعلق بقواعد كنوت. تُشير نتائج ميلهورن الرئيسية إلى أن قاعدة واحدة فقط من قواعد كنوت الاستدلالية (القاعدة الثانية) تُنتج دائمًا أشجار بحث ثنائية شبه مثالية. من ناحية أخرى، قد تؤدي قاعدة الجذر الأقصى في كثير من الأحيان إلى أشجار بحث "سيئة" للغاية استنادًا إلى الحجة البسيطة التالية. ^{[ 6 ]}

يترك

${\textstyle {\begin{aligned}n=2^{k}-1,~~A_{i}=2^{-k}+\varepsilon _{i}~~\operatorname {with} ~~\sum _{i=1}^{n}\varepsilon _{i}=2^{-k}\end{aligned}}}$

و

${\textstyle {\begin{aligned}\varepsilon _{1},\varepsilon _{2},\dots ,\varepsilon _{n}>0~~\operatorname {for} ~~1\leqq i\leqq n~~\operatorname {and} ~~B_{j}=0\operatorname {for} ~~0\leqq j\leqq n.\end{aligned}}}$

مع الأخذ في الاعتبار طول المسار المرجح${\displaystyle P}$من الشجرة التي تم إنشاؤها بناءً على التعريف السابق، لدينا ما يلي:

$\begin{aligned}P&=\sum _{i=1}^{n}A_{i}(a_{i}+1)+\sum _{j=1}^{n}B_{j}b_{j}\\&=\sum _{i=1}^{n}A_{i}i\\&\geqq 2^{-k}\sum _{i=1}^{n}i=2^{-k}{\frac {n(n+1)}{2}}\geqq {\frac {n}{2}}.\end{aligned}}}$

وبالتالي، ستكون الشجرة الناتجة عن قاعدة الجذر الأقصى شجرة تنمو فقط على الجانب الأيمن (باستثناء أعمق مستوى في الشجرة)، وسيحتوي الجانب الأيسر دائمًا على عقد طرفية. ويبلغ طول مسار هذه الشجرة حدًا معينًا.${\textstyle \Omega ({\frac {n}{2}})}$وعند مقارنتها بشجرة بحث متوازنة (ذات مسار محدود بـ${\textstyle O(2\log n)}$^{[ 6 ]} )، سيكون أداؤها أسوأ بكثير لنفس توزيع التردد.

بالإضافة إلى ذلك، قام ميلهورن بتحسين عمل كنوت وقدم خوارزمية أبسط بكثير تستخدم القاعدة الثانية وتقارب أداء الشجرة المثلى إحصائيًا في وقت قصير جدًا .${\displaystyle O(n)}$[ ^{6 ]} تتبع الخوارزمية ^{نفس فكرة قاعدة التنصيف ،} حيث تختار جذر الشجرة لتحقيق توازن دقيق بين الوزن الإجمالي (باحتمالية) للأشجار الفرعية اليسرى واليمنى. ثم تُطبق هذه الاستراتيجية بشكل متكرر على كل شجرة فرعية.

يمكن ملاحظة أن هذه الاستراتيجية تُنتج تقريبًا جيدًا بشكل بديهي من خلال ملاحظة أن أوزان الأشجار الفرعية على طول أي مسار تُشكل ما يُقارب تسلسلًا متناقصًا هندسيًا. في الواقع، تُنتج هذه الاستراتيجية شجرةً يكون طول مسارها الموزون على الأكثر

${\displaystyle 2+(1-\log({\sqrt {5}}-1))^{-1}H=2+{\frac {H}{1-\log({\sqrt {5}}-1)}}}$

حيث H هي إنتروبيا توزيع الاحتمال. بما أنه لا يمكن لأي شجرة بحث ثنائية مثالية أن تحقق أداءً أفضل من طول مسار مرجح قدره

${\displaystyle (1/\log 3)H={\frac {H}{\log 3}}}$

هذا التقريب دقيق للغاية. ^{[ 6 ]}

في الحالة الخاصة التي يكون فيها كل${\displaystyle A_{i}}$إذا كانت القيم صفرًا، فيمكن إيجاد الشجرة المثلى في وقت${\displaystyle O(n\log n)}$أُثبت ذلك لأول مرة من قِبل تي سي هو وآلان تاكر في ورقة بحثية نشراها عام ١٩٧١. وقد قام غارسيا وواكس بتبسيط هذه الخوارزمية لاحقًا، وهي خوارزمية غارسيا-واكس ، التي تُجري المقارنات نفسها بالترتيب نفسه. تعتمد الخوارزمية على استخدام خوارزمية جشعة لبناء شجرة ذات ارتفاع مثالي لكل ورقة، ولكن بترتيب غير صحيح، ثم بناء شجرة بحث ثنائية أخرى بنفس الارتفاعات. ^{[ ٧ ]}

توجد عدة تعريفات مختلفة للأمثلية الديناميكية، وكلها متكافئة فعليًا ضمن عامل ثابت من حيث زمن التشغيل. ^{[ 8 ]} طُرحت هذه المشكلة ضمنيًا لأول مرة من قِبل سليتور وتارجان في ورقتهم البحثية حول الأشجار المتفرعة ، ^{[ 9 ]} لكن ديمين وآخرون قدموا صياغة رسمية جيدة جدًا لها. ^{[ 8 ]}

في مسألة الأمثلية الديناميكية، لدينا سلسلة من عمليات الوصول x ₁ ، ... ، x _m على المفاتيح 1 ، ... ، n. لكل عملية وصول، لدينا مؤشر إلى جذر شجرة البحث الثنائية الخاصة بنا ويمكننا استخدام المؤشر لتنفيذ أي من العمليات التالية:

1. انقل المؤشر إلى الابن الأيسر للعقدة الحالية.
2. انقل المؤشر إلى الابن الأيمن للعقدة الحالية.
3. انقل المؤشر إلى العنصر الأصل للعقدة الحالية.
4. قم بإجراء دوران واحد على العقدة الحالية وعقدتها الأصلية.

(إن وجود العملية الرابعة، التي تعيد ترتيب الشجرة أثناء عمليات الوصول، هو ما يجعل هذه المسألة مشكلة أمثلية ديناميكية .)

في كل عملية وصول، يمكن لخوارزمية شجرة البحث الثنائية لدينا تنفيذ أي تسلسل من العمليات المذكورة أعلاه طالما أن المؤشر ينتهي في النهاية على العقدة التي تحتوي على القيمة المستهدفة xᵢ _. الوقت الذي تستغرقه خوارزمية شجرة البحث الثنائية الديناميكية لتنفيذ تسلسل من عمليات الوصول يعادل إجمالي عدد هذه العمليات التي تُنفذ خلال ذلك التسلسل. وبالنظر إلى أي تسلسل من عمليات الوصول على أي مجموعة من العناصر، يوجد حد أدنى لإجمالي عدد العمليات المطلوبة لتنفيذ تلك العمليات. ونسعى إلى الاقتراب من هذا الحد الأدنى.

مع أنه من المستحيل تطبيق " خوارزمية الله " هذه دون معرفة مسبقة بتسلسل الوصول، يمكننا تعريف OPT(X) على أنه عدد العمليات التي ستنفذها الخوارزمية لتسلسل وصول X، ويمكننا القول إن الخوارزمية مثالية ديناميكيًا إذا كانت، لأي قيمة X، تنفذ X في زمن O (OPT(X)) (أي أن لها نسبة تنافسية ثابتة ). ^{[ 8 ]}

هناك العديد من هياكل البيانات التي يُفترض أنها تمتلك هذه الخاصية، ولكن لم يتم إثبات أي منها. ولا تزال مسألة وجود هيكل بيانات أمثل ديناميكيًا في هذا النموذج مفتوحة .

شجرة التفرع هي شكل من أشكال شجرة البحث الثنائية، ابتكرها دانيال سليتور وروبرت تارجان عام 1985، وتُنفذ عليها عمليات شجرة البحث القياسية.${\displaystyle O(\log(n))}$الوقت المستهلك. ^{[ 10 ]} يُفترض أنه الأمثل ديناميكيًا بالمعنى المطلوب. أي، يُعتقد أن شجرة التفرع تُنفذ أي تسلسل وصول طويل بما فيه الكفاية X في وقت O(OPT(X)). ^{[ 9 ]}

شجرة التانغو هي بنية بيانات اقترحها إريك دي. ديمين ، وديون هارمون، وجون إياكونو ، وميهاي باتراشكو في عام 2004 ، وقد ثبت أنها تؤدي أي تسلسل وصول طويل بما فيه الكفاية X في وقت${\displaystyle O(\log \log n\operatorname {OPT} (X))}$على الرغم من أن هذا ليس الأمثل ديناميكيًا، إلا أن النسبة التنافسية لـ${\displaystyle \log \log n}$لا يزال صغيرًا جدًا بالنسبة للقيم المعقولة لـ n. ^{[ 8 ]}

في عام ٢٠١٣، نشر جون إياكونو بحثًا يستخدم هندسة أشجار البحث الثنائية لتقديم خوارزمية مثالية ديناميكيًا، إن وُجدت خوارزمية مثالية ديناميكيًا لأي خوارزمية أخرى لأشجار البحث الثنائية. ^{[ ١١ ]} تُفسَّر العُقد كنقاط في بُعدين، وتسلسل الوصول الأمثل هو أصغر مجموعة شاملة مُرضية شجريًا من تلك النقاط. على عكس أشجار التفرع وأشجار التانغو، لا يُعرف أن بنية بيانات إياكونو قابلة للتنفيذ في وقت ثابت لكل خطوة من خطوات تسلسل الوصول، لذا حتى لو كانت مثالية ديناميكيًا، فقد تظل أبطأ من هياكل بيانات أشجار البحث الأخرى بمعامل غير ثابت.

الحد الأدنى للتداخل هو حد أدنى تقاربي على الأمثلية الديناميكية.