الكشف عن الحفظ أو خسائر أو مكاسب في صياغة اللعبة مع البنود وصفات

Question

لنفترض أن لدينا تصميم لعبة مثل ماين كرافت حيث لدينا الكثير من العناصر $i_1,i_2,...,i_n\في$ و مجموعة من الوصفات $r_1,r_2,...,r_m $.وصفات وظائف $r:(أنا\تايمز\mathbb{N})^n ightarrow أنا\تايمز\mathbb{N}$, ذلك أنها تأخذ بعض العناصر غير سلبية صحيح الأوزان و ينتج عدد صحيح كمية من عنصر آخر.

على سبيل المثال, وصفة كعكة في ماين كرافت هو:

3 حليب + 3 القمح + 2 سكر + 1 بيضة $ ightarrow$ 1 كعكة

...وصفة المشاعل هو:

1 عصا + 1 الفحم $ ightarrow$ 4 المشاعل

بعض الوصفات يمكن أن يكون حتى عكسها ، على سبيل المثال:9 الماس $\leftrightarrow$ 1 الماس كتلة

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

هل هناك خوارزمية فعالة التي يمكن أن تقرر إذا كان مجموعة من وصفات:

• الحفاظ على العناصر ؟
• تفقد البنود الكفاءة?
• اكتساب العناصر ؟

هل هناك خوارزمية فعالة التي يمكن أن تجد إشكالية وصفات إذا اللعبة هو متوازن?

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

ونحن يمكن أن ترميز وصفات في مصفوفة $\mathbf{R}^{m \مرات n}$ حيث صفوف تتوافق مع وصفات والأعمدة تتوافق مع البنود.عمود إدخالات سلبية إذا كان عنصر يستهلكها وصفة إيجابية إذا كانت تنتجها وصفة ، وصفر إذا كان غير المستخدمة.مشابهة معروفة مصفوفة طريقة الرسم البياني دورة كشف يمكننا رفع $\mathbf{R}$ إلى بعض الطاقة العالية والحصول على مبالغ من كل صف لمعرفة إذا كان البند المجاميع مستمرة البقاء متوازنة ، أو الذهاب سلبيا.ومع ذلك, أنا لست على ثقة من أن هذا يعمل دائما.

أي مناقشة أو رمز ، أو أوصى القراءة عن تقديره للغاية.

Answer 1

وهذا ينبغي أن تكون قابلة للحل مع البرمجة الخطية.

خلفية الإعداد

اسمحوا الدولة ناقلات يكون متجه من إحصاء عدد كل عنصر لديك.إذا كان من الممكن العناصر الحليب, القمح, السكر, البيض, كعكة, الماس, ثم حكم

3 حليب + 3 القمح + 2 سكر + 1 بيضة $ ightarrow$ 1 كعكة

يؤثر على حالة ناقلات بإضافة $(-3,-3,-2,-1,1,0)$ من أجل ذلك.لذلك اسمحوا $a_i$ للدلالة على تغيير ناقل عن $i$ال القاعدة.

تكتسب العناصر

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

$$a_1 x_1 + \النقاط + a_n x_n \ "جنرال إلكتريك" (0,0,\النقاط,0), x_1 \قه 0, \النقاط ، x_n \ "جنرال إلكتريك" 0$$

مثل أن $a_1 x_1 + \النقاط + a_n x_n>(0,0,\النقاط,0)$.هنا $\قه$ ويعرف على ناقلات pointwise (أي ، $u \قه v$ المنتدى $u_i\قه v_i$ يحمل كل $i$) و كذلك بالنسبة $>$.هذا يمكن التعبير عن الخطية البرنامج:يمكنك تحقيق أقصى قدر من مجموع إحداثيات $a_1 x_1 + \النقاط + a_n x_n$, رهنا التفاوت أعلاه.لذلك ، يمكن حلها في وقت متعدد الحدود باستخدام البرمجة الخطية حلالا.هذا يخبرك ما إذا كان هناك طريقة للحصول على بعض البند دون بد.

لماذا هو ادعاء صحيح ؟ حسنا, إذا كان هناك حلا ممكنا الخطية البرنامج ، فإنه يوفر وسيلة لزراعة عدد من البند دون بد.ولا سيما إذا كنت تبدأ مع عدد كبير جدا من كل عنصر ، ثم تطبيق المادة 1 $x_1$ مرات القاعدة 2 $x_2$ مرات ، وما إلى ذلك ، عليك في نهاية المطاف مع دولة جديدة ناقلات يختلف من حيث بدأت من قبل $a_1 x_1 + \النقاط + a_n x_n$, الذي هو على الأقل في كل مكون و بدقة أكبر في عنصر واحد على الأقل.وعلاوة على ذلك, إذا كنت تبدأ مع عدد كبير بما فيه الكفاية من العناصر ، لن "الذهاب سلبية" في أي خطوة وسيطة في تطبيق القواعد.ملاحظة أنه إذا كان هناك حل لهذه الخطية البرنامج ، هناك حل في الارقام الحقيقية التي ينتج حلا في الاعداد الصحيحه (ضرب المناسبة ثابتة واضحة القواسم).

على العكس من ذلك ، إذا كان هناك طريقة لزراعة عدد من البند دون الالتزام ، ثم هناك حل البرنامج الخطي:فقط اسمحوا $x_i$ حساب عدد مرات القاعدة $i$ يتم تطبيق هذا الأسلوب, و سترى أن هذا ينتج صالح حل البرنامج الخطي.

فقدان العناصر

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

$$a_1 x_1 + \النقاط + a_n x_n \le (0,0,\النقاط,0), x_1 \قه 0, \النقاط ، x_n \ "جنرال إلكتريك" 0$$

مثل أن $a_1 x_1 + \النقاط + a_n x_n<(0,0,\النقاط,0)$.يجب عليك التحقق من بلدي المنطق لم اطلع على هذه بعناية.

الحفظ

أخيرا, إذا كان هناك أي طريقة للحصول على العناصر دون الالتزام أو تفقد البنود دون الالتزام ، ثم أعتقد أنه يترتب على ذلك أن قيمة الحفظ.

Answer 2

مشكلتك أي ما يعادل سؤال عما إذا كان هناك مزيج خطي من ناقلات الصف من $ \ mathbb r ^ {m \ times n} $ matrix التي لديها كل شيء معاملات إيجابية ومبالغ إلى متجه فيها (أ) كل عنصر $ \ ge 0 $ and (b) عنصر واحد على الأقل هو $> 0 $ .

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

أعتقد أن هذا يمكن حلها بواسطة البرمجة الخطية: قم بإجراء متغير لكل معامل، إضافة $ \ GE 0 $ قيود لكل عنصر في ناقل الإخراج (كل العنصر هو منتج نقطة من متغيرات المعاملات والمعاملات المستمرة من الوصفات)، وأكثر $ \ GE 0 $ القيود لكل متغير معامل، وتعيين الوظيفة لتعظيم أن تكون مجموع جميع العناصر. لجعلها تحدها، اضبط مجموع متغيرات المعاملات إلى بعض الثابت، على سبيل المثال 1. IFF قيمة الحل هي $> 0 $ ، لديك عدم الحفظ!

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