خوارزمية تحسين التوزيع

Question

أحاول تصنيف والتوصل إلى حل معقول للمشكلة التالية (المستخرجة من مشكلة العالم الحقيقي).

المشكلة

تخيل ستاكوفيرفلو التي تقدم اشتراك حيث يمكن للشركات شراء عدد العاشر من مرات الظهور شهريا لمجموعة من العلامات.

على سبيل المثال ، قد تكون مهتما بتشغيل إعلان يحتوي على 50000 ظهور على العلامات التالية: javascipt, typescript, react, nextjs, nodejs, webpack.

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

كيف ينبغي ستاكوفيرفلو تحسين التوزيع حتى يتمكنوا من بيع / تقديم أكبر عدد ممكن من مرات الظهور?

من أجل البساطة ، افترض:

• نحن نعرف عدد مرات الظهور التي تتلقاها كل علامة شهريا في وقت مبكر ولا يتغير
• كل ظهور ينتمي فقط إلى علامة واحدة

بحثي

أعتقد أن هذا قد يكون مشابها لـ حقيبة ظهر أو بن التعبئة مشاكل.

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

1. احصل على جميع "الاشتراكات" النشطة (مرات الظهور والعلامات) ، مرتبة حسب تاريخ الإنشاء
2. لكل "اشتراك" ، احصل على العلامة الأولى و" استهلك " أكبر عدد ممكن من مرات الظهور.إذا كان الاشتراك لا يزال يحتوي على مرات ظهور متبقية ، فانتقل إلى العلامة التالية.
3. كرر مع الاشتراك التالي

قد تلعب بها شيء من هذا القبيل:

==Inventory==

Tag          Impressions
javascipt    2000
typescript   5000
react        5000
nextjs       5000


== Subscriptions ==

Acme:  8000  (javacript, typescript, react, nextjs)
Stark: 5000  (javacript, typescript)

== Allocation Results ==

Acme: 
 - javacript:  2000
 - typescript: 5000
 - react:      1000

Stark: 
 - javacript:  0
 - typescript: 0

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

هل هناك اسم رسمي لهذه المشكلة وماذا الحل الأمثل تبدو وكأنها?

Answer 1

وأعتقد أن هذا هو في الواقع "مجرد" أقصى مطابقة ثنائية العلاقة ، والتي يمكن حلها على النحو الأمثل في O س (/ه / \ الجذر التربيعي {/الخامس/})) الوقت باستخدام خوارزمية هوبكروفت-كارب.

على جانب واحد ، لديك قمة لكل انطباع مطلوب (على سبيل المثال ، العميل أ يطالب 50000 إما "جافا سكريبت" أو "تيبسكريبت" ، والعملاء ب يطالب 10000 "جافا سكريبت" ، لذلك 60000 القمم في كل شيء) ، وعلى الجانب الآخر لديك قمة لكل الانطباع الموردة (مثلا ، 30000 المسمى "جافا سكريبت" و 15000 المسمى "تيبسكريبت" ، لذلك 45000 القمم في كل شيء).ارسم حافة من كل انطباع مطلوب إلى كل انطباع مقدم من نوع يلبي قيود نوع الانطباع (لذلك سيكون هناك 45000 حافة تترك كل من رؤوس العميل أ ، و 15000 حافة تترك كل من العملاء ب) ، وحلها.

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

Answer 2

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

سيكون النهج المعقول لحلها في الممارسة هو استخدام البرمجة الخطية الصحيحة.