كيف يمكنني العثور على جميع المسارات من خلال مجموعة من العقد المحددة في DAG؟

Question

لدي قائمة بالعناصر (العقد الزرقاء أدناه) التي تم تصنيفها بواسطة مستخدمي تطبيقي.يمكن تجميع الفئات نفسها وتصنيفها بنفسها.

يمكن تمثيل الهيكل الناتج كـ الرسم البياني الحلقي الموجه (DAG) حيث تكون العناصر عبارة عن أحواض في أسفل هيكل الرسم البياني وتكون الفئات العليا هي المصادر.لاحظ أنه على الرغم من أن بعض الفئات قد تكون محددة جيدًا، إلا أن الكثير منها سيكون محددًا من قبل المستخدم وقد يكون فوضويًا للغاية.

مثال:

_{(مصدر: theuprightape.net)}

على هذا الهيكل، أريد تنفيذ العمليات التالية:

• العثور على جميع العناصر (المصارف) أسفل عقدة معينة (جميع العناصر في أوروبا)
• ابحث عن جميع المسارات (إن وجدت) التي تمر عبر مجموعة العقد n (جميع العناصر المرسلة عبر SMTP من example.com)
• ابحث عن جميع العقد التي تقع أسفل مجموعة العقد بأكملها (التقاطع:الأطعمة البني غوييش)

الأول يبدو واضحًا تمامًا:ابدأ من العقدة، واتبع جميع المسارات الممكنة إلى الأسفل واجمع العناصر هناك.ومع ذلك، هل هناك نهج أسرع؟ربما يساعد تذكر العقد التي مررت بها بالفعل على تجنب التكرار غير الضروري، ولكن هل هناك المزيد من التحسينات؟

كيف اتعامل مع الثاني؟يبدو أن الخطوة الأولى ستكون تحديد ارتفاع كل عقدة في المجموعة، وذلك لتحديد أي عقدة (عقدة) يجب أن تبدأ ثم العثور على جميع المسارات الموجودة أسفل تلك التي تتضمن بقية المجموعة.ولكن هل هذا هو النهج الأفضل (أو حتى الجيد)؟

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

Answer 1

يبدو لي أنها في الأساس نفس العملية لجميع الأسئلة الثلاثة.أنت تسأل دائمًا "ابحث عن كل X أسفل العقدة (العقد) Y، حيث يكون X من النوع Z".كل ما تحتاجه هو آلية عامة لـ "تحديد موقع جميع العقد أسفل العقدة" (يحل السؤال الثالث) وبعد ذلك يمكنك تصفية النتائج لـ "نوع العقدة = الحوض" (يحل السؤال الأول).بالنسبة للسؤال الثاني، لديك نقطة البداية (مجموعة العقد الخاصة بك) ونقطة النهاية (أي حوض أسفل نقطة البداية) لذا فإن مجموعة الحلول الخاصة بك هي جميع المسارات من عقدة البداية المحددة إلى الحوض.لذا أود أن أقترح أن ما لديك في الأساس هو شجرة، وستكون الخوارزميات الأساسية لاجتياز الشجرة هي الحل الأمثل.

Answer 2

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

انظر أيضا روبرت تارجان الخوارزميات الأساسية.