خوارزمية للعثور على أفضل الطرق لتوزيع الطعام في اللعبة

Question

أقوم بتصميم لعبة بناء المدينة ودخلت مشكلة.

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

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

المهمة: أخبر كل منطقة حيث يجب أن يحصلوا على طعامهم أثناء قضاء الوقت على أقل الوقت وتقليل الازدحام على طرق المدينة.

مثال خريطة

لنفترض أن المناطق الصفراء تحتاج إلى 7 و 7 و 4 تفاح وفقًا لذلك. الحبال المزرق لها 7 و 11 تفاح وفقًا لذلك.

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

هنا ، يتم احتلال الطرق الرأسية لأول مرة إلى الحد الأقصى ، ثم يتم إرسال العمال الباقين إلى المسارات القطرية.

سؤال

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

Answer 1

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

Answer 2

هذا ال مشكلة التدفق القصوى المتعددة المصادر متعددة الفروق والتي يمكن تحويلها بسهولة إلى مشكلة في التدفق القصوى البسيطة عن طريق إنشاء مصدر فائق وحوض فائق كما هو موضح في الرابط. هناك العديد من الكفاءة حلول إلى أقصى قدر من مشاكل التدفق.

Answer 3

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

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

Answer 4

وأنا أتفق مع لاري و Mathmike ، يبدو بالتأكيد أن هذه المشكلة هي تخصص لتدفق الشبكة.

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

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

هذا ينتقل إلى جذر المشكلة - بشكل عام ، من الأسهل العثور على الحلول المثلى في مشاكل الرسم البياني ومن حيث Dev Game ، على الأرجح على الأرجح ، ربما تكون جيدة بما فيه الكفاية.

تحرير: أراد أن يشير أيضًا إلى أن رابط Mathmike لـ Wikipedia يتحدث أيضًا عنه الحد الأقصى لمشكلة التدفق مع قدرات الرأس حيث يمكن اعتبار كل من حبيباتك كبرودات ذات سعة محدودة.

Answer 5

شيء عليك أن تلاحظه ، هو أن لعبتك مستمرة. إذا كان لديك حل x في الوقت t ، ويحدث بعض التغييرات الصغيرة (على سبيل المثال: يقوم اللاعب ببناء طريق آخر ، أو تكتسب إحدى المدن المزيد من السكان) ، وهو الحل الذي تمنحكه خوارزميات Max Flow قد يتغير بشكل كبير, ، ولكن ربما تريد أن يكون الحل في T+1 مشابهًا لـ X. حل مختلف تمامًا في كل خطوة زمنية غير واقعية (تم تصميم طريق جديد في الطرف الجنوبي من الخريطة ، وجميع الطرق تلقائيًا إعادة تلقائيًا محسوب).

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

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

Answer 6

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

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

2. لا أحب الطرق الطويلة المربكة مع الكثير من المنعطفات. عند التخطيط لرحلة ، قد تعاقب أولئك الذين يعانون من حواف كثيرة.

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

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