مشكلة مسار القدرات القصوى مع القيود

Question

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

Answer 1

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