مطابقة قيم قمة مع مجموع الأوزان الحافة على الرسم البياني Bipartite

Question

في وقت سابق من هذا الأسبوع، سألت > هذا السؤال (يرجى مراجعة): < / ص>

تخيل Stackoverflow بدأ تقديم اشتراك فيه الشركات يمكن شراء رقم X من الانطباعات شهريا لمجموعة من العلامات.

على سبيل المثال، قد تكون مهتما بتشغيل إعلان 50000 انطباعات حول العلامات التالية: JAVASCHT، DIDVENTS، رد فعل، nextjs، nodejs، webpack.

stackoverflow "وعود" سوف تحصل على 50000 انطباعات، لكنها حرية توزيعها عبر العلامات المذكورة أعلاه ولكنهم يرغبون (يمكن أن يكون حتى 100٪ إلى علامة واحدة).

أحد الحلول المقدمة اقترح استخدام خوارزمية Hopcroft-Karp، التي تمكنت منذ ذلك الحين بنجاح تنفيذ.

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

المشكلة هي العدد الضخم من الحواف التي يجب تهيئةها. خذ المثال أدناه:

giveacodicetagpre.

إذا قامنا بإنشاء قمة لتمثيل كل وحدة، فسوف نواجه الأمر مع رسم بياني يحتوي على 101 حواف (7 * 11 + 4 * 6)!

p>

المشكلة التي أعمل فيها هي أوامر ذات حجم أكبر، لذلك يصبح هذا بسرعة غير واقعية.

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

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

p>

الهدف هو ضبط أوزان الحواف بحيث:

• على اليسار، فإن مجموع الحواف يساوي قيمة قمة الرأس
• على اليمين، فإن مجموع الحواف أقل من أو يساوي قيمة قمة الرأس

أدناه هو مثال على أحد الحلول:

href="https://i.stack.imgur.com/7iy71.png" er="nofollow noreferrer">

أنا التخمين (على أمل) هذه مشكلة معروفة بالفعل، والتي يوجد أيضا حل موثق جيدا (من الناحية المثالية غير الصعب)!

ربما من الممكن تعديل خوارزمية Hopcroft-Karp للعمل من أجل هذا؟

Answer 1

لدي أخبار سيئة. ليس هناك أمل في وجود خوارزمية أسوأ وقت التشغيل هو متعدد الحدود في حجم الرسم البياني المرجح (ما لم يكن P= NP، والذي يبدو غير مرجح).

مشكلتك صعبة مثل مشكلة Neapsack، والتي لا تحتوي على خوارزمية في كثير الحدود (ما لم يكن P= NP) عند تمثيل الإدخال في ثنائي. تحتوي مشكلة Neapsack على خوارزمية زمنية زائفة، مما يعني أن هناك خوارزمية توقيتها هو متعدد الحدود في الأرقام (ولكن ليس وقت متعدد الحدود في حجم الإدخال). في الإعداد الخاص بك، يتحول إلى خوارزمية في خوارزمية توقيتها هو متعدد الحدود في حجم الرسم البياني غير المرجح (مع عدد كبير من الحواف) ولكن ليس متعدد الحدود في حجم الرسم البياني المرجح (مع عدد صغير من الحواف).

يمكنك المحاولة مع التعبير عن هذا كمثيل برمجة خطية عددا صحيحا (ILP)، ثم يحل مع حلالطيل ILP. من الممكن أن تسفر عن حل أكثر كفاءة. الفكرة الأساسية هي تقديم متغير عدد صحيح $ x_ {i، j} $ التي تحسب عدد مرات الانطباعات المقدمة للشركة $ i $ في علامة $ J $ ؛ ثم يمكنك تقديم عدد قليل من عدم المساواة الخطية لالتقاط متطلبات المشكلة.