توزيع الموارد من مقدمي الخدمات إلى الحد الأقصى لعدد أجهزة الاستقبال

Question

تنظر هناك مدينة بها $ n $ المحتاجين إلى الإنترنت وهناك $ M $ مقدمي الإنترنت في المدينة.هنا في المدينة كل مقيم يحتاج إلى الإنترنت وكل مقيم يعرف ما هو متاح له للمقدمين.لترك رسميا $ i $ لديه قائمة بمقدمي الخدمات $ a_i $ .أيضا كل مزود لديه أقصى عدد من الاتصالات التي يمكن أن يعطيها، وهذا هو، مزود $ I $ يمكن أن يكون لديك في MAX $ k_i$ الاتصالات.ابحث عن الطريقة المثلى لتزويد الإنترنت بحيث يكون عدد السكان الذين يتناولون الإنترنت كحد أقصى.

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

Answer 1

هذه المشكلة هي حالة مشكلة التدفق القصوى .

لنفترض أننا نحتاجنا إلى مزودي الإنترنت $ p_1، p_2، \ cdots، p_m $ والمقيمين $ r_1، r_2، \ cdots، r_n $ . النظر في شبكة التدفق المحددة كما يلي.

• العقد هي $ S، \ p_1، p_2، \ cdots، p_m، \ r_1، r_2، \ cdots، r_n، \ t $ ، حيث $ S $ و $ T $ هي عقدان إضافيان يقفان للمصدر والوعة.
• هناك حافة بين $ S $ وكل $ p_i $ مع السعة $ k_i $ .
• هناك حافة بين $ p_i $ و $ r_j $ مع السعة 1 إذا $ p_i $ يمكن أن توفر الإنترنت إلى $ r_j $ .
• هناك حافة بين كل $ r_j $ و $ T $ مع السعة 1.

ما نريده هو العثور على أقصى تدفق من $ S $ إلى $ t $ . < / ص>

هناك

هناك العديد من الخوارزميات لحل مشكلة التدفق الأقصى في الوقت متعدد الحدود. على سبيل المثال، خوارزمية FORD-FULKERSON و خوارزمية دينيك شعبية جدا. يمكن العثور على شفرة المصدر التي تنفذ تلك الخوارزميات في مختلف لغات البرمجة بسهولة.

كل تلك الخوارزمية سوف تنتج تدفقا متكاملا أقصى تدفق، لذلك لن نشعر بالقلق في حالة تنص التدفق الأقصى المحسوب على أن بعض المزود يجب أن يوفر 0.42 أو $ \ frac {\ sqrt2} 2 $ الإنترنت إلى بعض المقيمين. يمكنك التحقق من نظرية التدفق التكامل .