برمجة الرسم البياني الديناميكي

Error

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

إذا كان الرسم البياني يحتوي على دورات (لا يوجد تصنيف طوبولوجي) ، فيمكن أن تساعد حيلتان:

1) احسب الديناميكيات n مرة ، حيث n هو عدد الرؤوس في الرسم البياني (بالقياس مع خوارزمية Ford-Bellman). لكن هذا يزيد من التقارب ونادرًا ما يكون فعالًا بشكل عام.

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