دورة أقصى وزن في الرسم البياني

Question

بالنظر إلى رسم بياني مرجح (موجه أو غير موجه) ، أحتاج إلى العثور على دورة الرسم البياني مع أقصى وزن.

وزن الدورة هو مجموع وزن حواف الرسم البياني.

يمكن أن تكون أي دورة ، وليس مجرد دورة أساسية يمكننا

• ابحث عن كل الدورة الأساسية (انظر خوارزميات لتحديد جميع قواعد الدورة في رسم بياني غير موجه )
• حساب وزن كل دورة قاعدة وابحث عن الحد الأقصى

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

هل لديك أي فكرة للعثور على أقصى دورة للوزن دون تعداد جميع الدورات؟

إذا كنت بحاجة إلى فرضية على الرسم البياني (أوزان الإيجابيات على سبيل المثال) ، فيرجى الإشارة إليها.

Answer 1

هذا هو np-hard.

يمكن تقليل مشكلة دورة هاميلتون إلى هذا.

بالنظر إلى الرسم البياني الذي نحتاج إلى التحقق مما إذا كانت هناك دورة هاميلتون أم لا ، قم بتعيين الوزن 1 إلى كل حافة.

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

Answer 2

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