كيفية حساب المسار الحرج للرسم البياني غير الحلقي الاتجاهي؟

Question

ما هي أفضل طريقة (فيما يتعلق بالأداء) لحساب المسار الحرج للرسم البياني غير الحلقي الاتجاهي عندما يكون لعقد الرسم البياني وزن؟

على سبيل المثال، إذا كان لدي البنية التالية:

            Node A (weight 3)
               /            \
     Node B (weight 4)      Node D (weight 7)
     /               \
Node E (weight 2)   Node F (weight 3)

يجب أن يكون المسار الحرج A->B->F (الوزن الإجمالي:10)

Answer 1

ليس لدي أي فكرة عن "المسارات الحاسمة"، ولكنني أفترض أنك تقصد هذا.

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

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

ولكن لا يوجد شيء ينقذك حقًا من الاجتياز الكامل إذا لم تفعل ذلك.الترتيب لا يهم حقًا، طالما أنك تفعل ذلك اجتياز ولا تسلك نفس الطريق مرتين.

Answer 2

سأحل هذه المشكلة بالبرمجة الديناميكية.للعثور على الحد الأقصى للتكلفة من S إلى T:

• قم بفرز عقد الرسم البياني طوبولوجيًا كـ S = x_0، x_1، ...، x_n = T.(تجاهل أي عقد يمكن أن تصل إلى S أو يمكن الوصول إليها من T.)
• الحد الأقصى للتكلفة من S إلى S هو وزن S.
• بافتراض أنك قمت بحساب الحد الأقصى للتكلفة من S إلى x_i لكل i < k، فإن الحد الأقصى للتكلفة من S إلى x_k هو تكلفة x_k بالإضافة إلى التكلفة القصوى لأي عقدة ذات حافة إلى x_k.

Answer 3

هناك ورقة تدعي أن لديها خوارزمية لهذا:“المسار الحرج في شبكة النشاط مع قيود زمنية”.للأسف لم أجد رابط للنسخة المجانية.باختصار، لا يسعني إلا أن أؤيد فكرة التعديل http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm أو http://en.wikipedia.org/wiki/A*

تحديث:أعتذر عن التنسيق السيئ، حيث يبدو أن محرك تخفيض السعر من جانب الخادم معطل.

Answer 4

إجابتي الأولى لذا يرجى العذر عن أي شيء غير قياسي من خلال ثقافة تدفق المكدس.

أعتقد أن الحل بسيط.ما عليك سوى إلغاء الأوزان وتشغيل أقصر مسار كلاسيكي لـ DAG (تم تعديله لأوزان القمم بالطبع).يجب أن تعمل بسرعة إلى حد ما.(التعقيد الزمني لـ O(V+E) ربما)

أعتقد أنه يجب أن يعمل لأنه عندما تقوم بإلغاء الأوزان، فإن أكبرها سيصبح أصغر، وثاني أكبر سيكون ثاني أصغر وهكذا كما لو a > b ثم -a < -b.ثم يجب أن يكون تشغيل DAG كافيًا لأنه سيجد الحل لأصغر مسار للمسار المنفي وبالتالي العثور على أطول مسار للمسار الأصلي

Answer 5

جرب الطريقة أ*.

أ* خوارزمية البحث

في النهاية، للتعامل مع الأوراق، ما عليك سوى جعلها كلها تؤدي إلى نقطة أخيرة، لتعيينها كهدف.