عمر علي مختار

جزاك الله خيراً .. حل جيد .. يقلل من عدد الإحتمالات التي نمر عليها في الكثير من الحالات .. لكن في أسوأ الإحتمالات حيث تكون قيمة X و Y و Z كبيرة جداً لا نجد إلا أن نمر على كل الإحتمالات لإستخراج أقل F(A,B,C) ..

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

السلام عليكم و رحمة الله و بركاته .. في إحدى البرامج واجهتني مشكلة يمكن تبسيطها في الآتي .. لدينا عدد N من المجموعات .. كل مجموعة بها عدد M من العناصر .. كل عنصر له 3 أرقام a و b و c .. المطلوب هو أن أختار عنصر واحد من كل مجموعة بحيث يكون مجموع الرقم a لكل العناصر المختارة أقل من X و مجموع b لكل العناصر المختارة أقل من Y و مجموع c لكل العناصر المختارة أقل من Z .. بالطبع سيكون لدينا الكثير من الإحتمالات و التوافيق التي توافق هذا الشرط .. و التوفيق الأفضل هو الذي إذا قمنا بالتعويض في F(A,B,C) و التي هي هذه المعادلة : h*A+i*B+ j*C نحصل على أقل قيمة .. حيث أن A هي مجموع الـ a لكل العناصر و هكذا B و C .. مثال : المجموعة الأولى : عنصر 1 : a = 7 , b = 5 , c = 11 عنصر 2 : a = 2 , b = 8 , c = 12 المجموعة الثانية : عنصر 1 : a = 3 , b = 5 , c = 22 عنصر 2 : a = 9 , b = 1 , c = 44 و بقية المدخلات : X = 15 Y = 14 Z = 50 h = 0.4 i = 0.3 j = 0.3 هنا كل التوافيق ستكون : عنصر 1 من مجموعة 1 مع عنصر 1 من مجموعة 2: مجموع الـ A سيكون 10 .. مجموع الـ B سيكون 10 و مجموع الـ C سيكون 33 و الحل مقبول حيث أن A أقل من X و B أقل من Y و C أقل من Z .. F(A,B,C) = 10*0.4 + 10*0.3 + 33*0.3 = 16.9 عنصر 2 من مجموعة 1 مع عنصر 1 من مجموعة 2 مجموع الـ A سيكون 5 .. مجموع الـ B سيكون 13 و مجموع الـ C سيكون 34 و الحل مقبول أيضاً .. F(A,B,C) = 5*0.4 + 13*0.3 + 34*0.3 = 11.55 و هنا هذا الحل أفضل من الحل السابق لأن قيمة الـ F أقل عنصر 1 من مجموعة 1 مع عنصر 2 من مجموعة 2 مجموع الـ A سيكون 16 .. مجموع الـ B سيكون 6 و مجموع الـ C سيكون 55 و هنا الحل غير مقبول حيث أن C أكبر من Z و A أكبر من X .. عنصر 2 من مجموعة 1 مع عنصر 2 من مجموعة 2 مجموع الـ A سيكون 11 .. مجموع الـ B سيكون 9 و مجموع الـ C سيكون 56 و هذا الحل غير مقبول أيضاً بسبب قيمة الـ C .. و هنا نكون قد توصلنا إلى أن إختيار عنصر 2 من مجموعة 1 مع عنصر 1 من مجموعة 2 هو الأحل الأفضل .. قمت بحل هذه المسألة بطريقة أشبه إلى حدٍ ما بالـ Brute Force .. تصل في أسوأ الحالات إلى O(M^N) .. هل لديكم من أفكار أخرى لحل هذه المشكلة ؟؟ و جزاكم الله خيراً ..

منذ عدة شهور كنت ألعب إحدى الألعاب الإستراتيجية .. و لفت نظري (أو بمعنى أصح كان يضايقني) أن الفريق الذي أتحكم به لا أستطيع السيطرة عليه بشكل كامل .. فعلى سبيل المثال عندما كان يحدث هجوم من الفريق الأخر (و الذي يتحكم فيه الذكاء الأصطناعي) كان علي أن أقوم بتوجيه كل جندي إلى مساره بنفسي لإني إذا تركته سيتحكم الحاسب به أوتوماتيكياً و ربما سار في طريق أخر يفسد الخطة و يمكن أن يهرب !! .. المهم أن مسألة التحكم الكامل في اللعبة بدقة كان هو ما أريده و لكنه لا يوجد بالشكل الذي ينبغي في الألعاب خاصة في الألعاب الإستراتيجية .. حينها خطرت ببالي فكرة تحل هذا المشكلة و هي أن اللاعب يقوم بكتابة أوامر و أكواد تصف كيف ستتصرف كائنات اللعبة و أثناء اللعبة يتم تنفيذ تلك الأوامر .. بدأت في تنفيذ لعبة بهذا المفهوم الذي ربما يكون جديداً أو على الأقل غير معروف في عالم الألعاب .. و بعد أن قمت بإستشارة إحدى الدكاترة في الجامعة عدلت المسار قليلاً .. و بعد بضعة أسابيع من العمل المتواصل خرج الإصدار التجريبي الأول إلى النور ! هذا الإصدار ليس لعبة بل هو برنامج يتيح للاعبين أن يقوموا بكتابة أكوادهم و إرسالها إلى خادم يقوم بعمل مباريات بين تلك الأكواد و تسجيل النتائج و هكذا .. إنظر إلى هذه الصورة : هذه أول لعبة من هذا النوع .. في هذا الملعب يقوم اللاعب الأزرق بضرب بالونات اللاعب الأخضر و العكس .. و الذي يقوم بإفناء بالونات الأخر يفوز في النهاية .. و توجد بها بعض القوانين مثل أن اللاعب إذا تجاوز الحدود البيضاء تقل نتيجته و إذا ضرب بالون بنفس لونه تقل نتيجته أيضاً .. و إذا ضرب بالون اللاعب الأخر تزيد نتيجته .. هذه اللعبة و غيرها من الألعاب التي ستصدر قريباً إن شاء الله يمكن للاعبين أن يلعبوها عن طريق هذا البرنامج : هنا يقوم اللاعبين بالتسجيل و الدخول .. و هنا يقوم اللاعبين بإختيار الألعاب التي يريدون لعبها و تحميلها .. القائمة اليسرى هي قائمة الألعاب و القائمة اليمنى هي قائمة المستخدمين الذين كتبوا أكواداً لهذه الألعاب .. و فوق الأزرار التي في الاسفل تجد شريط مكتوب فيه أعلى النتائج .. و هنا يقوم إحدى اللاعببين بكتابة كود لإحدى الألعاب .. و بعد أن يقوم بعمل Save يتم إرسال الكود إلى الخادم يقوم بمباراة جميع اللاعبين المسجلين في هذه اللعبة و تعديل النتائج .. ربما يقوم هذا الفيديو بتوضيح أكثر : للتحميل : حتى هذه اللحظة يتوفر إصدار نظام لينكس .. و قريباً إن شاء الله سيتوفر إصدار لنظام ويندوز https://sourceforge.net/projects/cap-scg/ و أخيراً و ليس أخراً .. مازال هناك الكثير لإضافته و تعديله .. و ربما تكون هناك بعض المشاكل و الأخطاء المخفية هنا و هناك و لم أكتشفها و تظهر عند بعض المستخدمين ! .. و لهذا أرحب بجميع إقتراحاتكم و إضافاتكم و مشاكلكم في التعليقات .. المصدر : http://omarmokhtar.net/2011/08/02/code-and-play-version-0-1-beta/