هل هناك خوارزمية للعثور على أفضل مجموعة من الأزواج من الرموز في رسم بياني مرجح دون تكرار؟
-
27-09-2019 - |
سؤال
هل هناك أي خوارزمية فعالة للعثور على مجموعة الحواف ذات الخصائص التالية ، في رسم بياني مرجح كامل مع عدد متساوٍ من القمم.
- تحتوي المجموعة على أصغر وزن حافة أقصى لأي مجموعة تتسرب من المعايير الأخرى الممكنة
- يتم توصيل كل قمة الرأس بحافة واحدة بالضبط في المجموعة
جميع الأوزان إيجابية
لا يمكن أن يفكر DI في قوة أفضل من القوة الغاشمة ، لكنني لا أدركها على أنها NP بشدة.
المحلول
طريقة واحدة لحل هذه المشكلة في وقت الحدود هي كما يلي:
- فرز الأوزان الحافة في وقت O (e log e)
- لكل حافة ، قم بتعيينه على وزن زائف E '= 2^{الموضع في الطلب} في ~ o (e) الوقت
- ابحث عن الحد الأدنى لمطابقة الوزن المثالي بين الأوزان الزائفة في وقت مثل O (v^3) (اعتمادًا على الخوارزمية التي تختارها ، قد تكون أبطأ أو أسرع)
هذا يقلل من أكبر حافة تحتوي على المطابقة المثالية ، وهو بالضبط ما تبحث عنه في وقت مثل O (v^3).
وترد أدناه مصادر لكيفية القيام الجزء 3 أدناه
[1] http://www2.isye.gatech.edu/~wcook/papers/match_ijoc.pdf
[2] http://www.cs.illinois.edu/class/sp10/cs598csc/lectures/lecture11.pdf
[3] http://www.cs.ucl.ac.uk/staff/v.kolmogorov/papers/blossom5.ps
مع Sample C ++ مصدر متاح في http://ciju.wordpress.com/2008/08/10/min-cost-perfect-gatching/
نصائح أخرى
جرب هذا (لقد اعتقدت هذا الأمر فقط ، لذا لم أحصل على دليل على أنه سيعطي إجابة مثالية أو ما إذا كان سيؤدي إلى حل في كل حالات):
- ابحث عن أثقل رؤوس V (A ، B)
- إزالة Vertice V من الرسم البياني
- إذا كان A متصلاً فقط بفيروس واحد آخر T (A ، C) ، فقم بإزالة جميع الحواف الأخرى المتصلة بـ C ، كرر الخطوة 3 مع تلك الحواف أيضًا
- إذا كان B متصلاً فقط بدفتر واحد آخر (B ، D) ، فقم بإزالة جميع الحواف الأخرى المتصلة بـ D ، كرر الخطوة 4 مع تلك الحواف أيضًا
- كرر من الخطوة رقم 1