البحث الشجري الموزع

خوارزمية البحث الشجري الموزع ( DTS ) هي فئة من الخوارزميات للبحث عن القيم بكفاءة وبطريقة موزعة. هدفها هو المرور عبر الشجرة من خلال العمل على فروع متعددة بالتوازي ودمج نتائج كل فرع في حل واحد مشترك، وذلك لتقليل الوقت المستغرق في البحث عن قيمة في بنية بيانات شجرية.

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

تم إنشاء خوارزمية البحث الشجري الموزع (المعروفة أيضًا باسم خوارزمية Korf-Ferguson) لحل المشكلة التالية: "بالنظر إلى شجرة ذات عامل تفرع وعمق غير منتظمين، ابحث فيها بالتوازي مع عدد عشوائي من المعالجات بأسرع ما يمكن".

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

تعتمد خوارزمية البحث المتقطع (DTS) على استخدام عدة عمليات، لكل منها عقدة ومجموعة من المعالجات، بهدف البحث في الشجرة الفرعية أسفل تلك العقدة. ثم تنقسم كل عملية إلى عدة عمليات فرعية منسقة، والتي بدورها تنقسم بشكل متكرر حتى يتم العثور على الطريقة المثلى للبحث في الشجرة بناءً على عدد المعالجات المتاحة لكل عملية. بمجرد انتهاء عملية ما، تعيد خوارزمية DTS توزيع المعالجات ديناميكيًا على عمليات أخرى للحفاظ على أعلى كفاءة ممكنة من خلال موازنة الأحمال بشكل جيد، خاصةً في الأشجار غير المنتظمة.

بمجرد أن تنتهي العملية من البحث، فإنها ترسل وتدمج بشكل متكرر الإشارة الناتجة إلى العملية الأصلية، حتى يتم دمج جميع الإجابات الفرعية المختلفة وحل المشكلة بأكملها. ^{[ 1 ]}

لا يمكن تطبيق DTS إلا في ظل شرطين رئيسيين: أن يكون هيكل البيانات المراد البحث فيه عبارة عن شجرة، وأن تستخدم الخوارزمية وحدة حسابية واحدة على الأقل (على الرغم من أنه لا يمكن اعتبارها موزعة إذا كانت هناك وحدة واحدة فقط).

يُعدّ توجيه الشبكات أحد أبرز الأمثلة على الاستخدام اليومي لتقنية DTS. يمكن تشبيه الإنترنت بشجرة عناوين IP ، ويمكن تشبيه بروتوكول التوجيه بكيفية عمل مكاتب البريد في العالم الحقيقي. ونظرًا لوجود أكثر من 4.3 مليار عنوان IP حاليًا، يعتمد المجتمع بشكل كبير على الوقت الذي تستغرقه البيانات للوصول إلى وجهتها. ولذلك، يقسم توجيه IP العمل إلى وحدات فرعية متعددة، لكل منها قدرات حسابية مختلفة، وتستخدم نتائج الوحدات الأخرى لإيجاد المسار بكفاءة عالية. هذا مثال على تقنية DTS التي تؤثر على أكثر من 43% من سكان العالم، لأسباب تتراوح بين الترفيه والأمن القومي. ^{[ 2 ]}

على الرغم من أن DTS هي حاليًا واحدة من أكثر الخوارزميات استخدامًا على نطاق واسع، إلا أن العديد من تطبيقاتها لها بدائل يمكن أن تتطور إلى حلول أكثر كفاءة وأقل استهلاكًا للموارد، إذا تم إجراء المزيد من الأبحاث عليها.

من الأمثلة الأكثر إثارة للجدل معالجة البيانات الضخمة. ففي تطبيقات مثل محرك بحث جوجل ، وفيسبوك، ويوتيوب ، يجب تحسين البحث للحفاظ على وقت الانتظار ضمن نطاق معقول. يمكن تحقيق ذلك باستخدام خوارزمية البحث الشجري المباشر (DTS)، ولكن تُستخدم خوارزميات أخرى بالتزامن معها (مثل تجزئة البيانات في قواعد بيانات SQL )، أو بالتزامن معها (تجمع خوارزمية Haystack الخاصة بفيسبوك بين البحث الشجري المتوازي، وتجزئة البيانات، وترتيب/فرز الذاكرة). ^{[ 3 ]}

لا توجد خلافات تُذكر حول خوارزمية DTS لكورف-فيرغسون، إذ تُعتبر شاملة وبسيطة في آنٍ واحد. وكثيراً ما تُستخدم كنقطة انطلاق للطلاب لاكتشاف أساسيات ومفاهيم حل المشكلات الموزعة.

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

• الشجرة (بنية البيانات)
• شجرة البحث
• شجرة البحث الثنائية
• اجتياز الأشجار
• البحث عن شجرة مونت كارلو
• الحوسبة المتوازية

• كولبروك أ.، بروير إي.، ديلاروكاس سي.، ويل دبليو.، "خوارزميات لأشجار البحث على بنى تمرير الرسائل" (1996)
• كولبروك أ.، سميث سي.، تطبيقات فعالة لأشجار البحث على بنى الذاكرة الموزعة المتوازية (1990)
• باير ر.، مكريت إي.، تنظيم وصيانة الفهارس المرتبة الكبيرة. أكتا إنفورماتيكا 1 (1972)
• كومر د.، شجرة بي المنتشرة في كل مكان (1979)