خوارزمية شجرة الوصل

• إذا كان الرسم البياني موجهاً، فقم بتعديله ليصبح غير موجه.
• قدّم الأدلة.
• قم بتقسيم الرسم البياني إلى مثلثات لجعله وتريًا.
• قم بإنشاء شجرة وصل من الرسم البياني المثلثي (سنسمي رؤوس شجرة الوصل " العقد الفائقة ").
• انشر الاحتمالات على طول شجرة الوصل (عن طريق نشر الاعتقاد )

لاحظ أن هذه الخطوة الأخيرة غير فعّالة للرسوم البيانية ذات عرض الشجرة الكبير . يتطلب حساب الرسائل المراد تمريرها بين العقد الفائقة إجراء تجزئة دقيقة للمتغيرات في كلتا العقدتين. وبالتالي، فإن تطبيق هذه الخوارزمية على رسم بياني بعرض شجرة k سيستلزم عملية حسابية واحدة على الأقل، تستغرق وقتًا أُسّيًا بالنسبة لـ k. إنها خوارزمية تمرير رسائل . ^{[ 3 ]} تتطلب خوارزمية هوجين عددًا أقل من العمليات الحسابية لإيجاد حل مقارنةً بخوارزمية شيفر-شينوي.

• تم حسابها بشكل متكرر ^{[ 3 ]}
• تؤدي عمليات التكرار المتعددة لخوارزمية Shafer-Shenoy إلى خوارزمية Hugin ^{[ 4 ]}
• تم العثور عليها بواسطة معادلة تمرير الرسائل ^{[ 4 ]}
• لا يتم تخزين جهود الفصل ^{[ 5 ]}

خوارزمية شيفر-شينوي هي حاصل ضرب مجموع شجرة الوصل. ^{[ 6 ]} تُستخدم هذه الخوارزمية لأنها تُشغّل البرامج والاستعلامات بكفاءة أعلى من خوارزمية هوجين. تُتيح هذه الخوارزمية إجراء حسابات الشروط لدوال الاعتقاد . ^{[ 7 ]} وتُعدّ التوزيعات المشتركة ضرورية لإجراء الحسابات المحلية. ^{[ 7 ]}

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

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

تتمثل الخطوة الثالثة في ضمان تحويل الرسوم البيانية إلى رسوم بيانية وترية إذا لم تكن كذلك بالفعل. هذه هي الخطوة الأساسية الأولى في الخوارزمية، وتعتمد على النظرية التالية: ^{[ 8 ]}

نظرية: بالنسبة للرسم البياني غير الموجه ، G، فإن الخصائص التالية متكافئة:

• الرسم البياني G مُثلّث.
• يحتوي الرسم البياني للزمرة G على شجرة تقاطع.
• يوجد ترتيب حذف لـ G لا يؤدي إلى أي حواف إضافية.

وبالتالي، من خلال تثليث الرسم البياني، نتأكد من وجود شجرة الوصلات المقابلة. إحدى الطرق الشائعة للقيام بذلك هي تحديد ترتيب حذف للعقد، ثم تشغيل خوارزمية حذف المتغيرات . تنص خوارزمية حذف المتغيرات على أنه يجب تشغيل الخوارزمية في كل مرة يكون هناك استعلام مختلف. ^{[ 1 ]} سيؤدي هذا إلى إضافة المزيد من الحواف إلى الرسم البياني الأولي، بحيث يكون الناتج رسمًا بيانيًا وتريًا . جميع الرسوم البيانية الوترية لها شجرة وصلات. ^{[ 4 ]} الخطوة التالية هي بناء شجرة الوصلات . للقيام بذلك، نستخدم الرسم البياني من الخطوة السابقة، ونشكل الرسم البياني للزمرة المقابلة له . ^{[ 9 ]} الآن، تقدم لنا النظرية التالية طريقة لإيجاد شجرة وصلات: ^{[ 4 ]}

النظرية: بالنظر إلى رسم بياني مثلثي، قم بترجيح حواف الرسم البياني للزمرة حسب عدد عناصرها، |A∩B|، لتقاطع الزمرتين المتجاورتين A و B. عندئذٍ، فإن أي شجرة ممتدة ذات وزن أقصى للرسم البياني للزمرة هي شجرة وصل.

لذا، لبناء شجرة وصل، يكفي استخراج شجرة ممتدة ذات وزن أقصى من الرسم البياني للزمرة. ويمكن القيام بذلك بكفاءة، على سبيل المثال، بتعديل خوارزمية كروسكال . وتتمثل الخطوة الأخيرة في تطبيق نشر الاعتقاد على شجرة الوصل المُستخرجة. ^{[ 10 ]}

الاستخدام: يُستخدم مخطط شجرة الوصلات لتمثيل احتمالات المسألة. ويمكن تحويل الشجرة إلى شجرة ثنائية لتكوين البنية الفعلية للشجرة. ^{[ 11 ]} يُمكن إيجاد استخدام محدد في المشفرات التلقائية ، التي تجمع بين المخطط وشبكة التمرير على نطاق واسع تلقائيًا. ^{[ 12 ]}

انتشار الاعتقاد الحلقي: طريقة مختلفة لتفسير الرسوم البيانية المعقدة. يُستخدم انتشار الاعتقاد الحلقي عندما تكون هناك حاجة إلى حل تقريبي بدلاً من الحل الدقيق . ^{[ 13 ]} وهو استدلال تقريبي . ^{[ 3 ]}

تكييف مجموعة القطع: يُستخدم مع مجموعات أصغر من المتغيرات. يسمح تكييف مجموعة القطع برسوم بيانية أبسط وأسهل في القراءة، لكنها ليست دقيقة تمامًا . ^{[ 3 ]}