11-11-2011, 01:50 AM
|
 |
|
|
تاريخ التسجيل: Jan 2010
التخصص: الحمدلله ... =)
نوع الدراسة: إنتظام
المستوى: الثالث
الجنس: أنثى
المشاركات: 1,840
|
|
[ 1000000$ لحـل خوارزمية الـMinesweeper..! ]^_^
اذا كنتـ/ي من لاعبي هذه اللعبة الشهيرة فستعرف عما أتحدث...
لقد توصل الباحث Richard Kaye في عام 2000 إلى نتيجة مفادها أن تعقيد حل مسألة كانسة الألغام هوNP-complete
لمن لا يعرف اللعبة فهي تعتمد على اكتشاف أماكن الألغام بين مجموعة من المربعات و ذلك بالاستفادة من المعلومات التي تقدمها الأرقام خلف كل مربع,و هي من الألعاب التي تأتي مع نظام تشغيل ويندوز.
الحالة الموضحة في الشكل تعطي فكرة عن الصعوبة الكامنة في حل هذه اللعبة , فلكي نكتشف أماكن الألغام علينا أن نسبر كل المربعات و نجمع كل المعلومات المتوفرة و نتخذ أقل عدد ممكن من المجازفات , و في هذه الحالة المبينة في الشكل ليس علينا أن نقوم بأي مجازفة بل يكفي أن نمعن التفكير و نفكر في كل الاحتمالات حتى نتوصل للحل الوحيد, طبعاً هناك حالات خاصة يكون لزاماً علينا أن نقوم بالتخمين و لكن في مثل هذه الحالات يجب أن نتدرس كافة الاحتمالات و نحاول أن نجعل المجازفة أقل ما يمكن.
عندما تلعب في كانسة الألغام عليك أن تأخذ بعين الاعتبار كل منطقة اللعب بحيث يكون لكل خطوة تأثير كبير على باقي المربعات و يصبح لزاماً علينا سبرها من جديد بعد كل خطوة, و هذا ما يجعل اللعبة صعبة الحل و يجعلنا نعتقد بأنها NP-complete
لقد تمكن Richard Kaye من برهان أن مسألة كانسة الألغام مكافئة في التعقيد لمسائل NP-complete و هي مسائل تأخذ شكل مسائل عامة تتطلب أجوبة من النمط نعم\لا
إن هذه المسائل مهمة للغاية و اكتشاف خوارزمية فعالة لحلها مفيد جداً و أعني هنا بكلمة فعالة أنها تستغرق زمن كثير حدود لتنفيذها, و لكن للأسف فحتى يومنا هذا لم يتمكن أحداً من ايجاد مثل هذه الخوارزمية, و هناك كثير من الناس يعتقدون أنه لا وجود لمثل هذه الخوارزمية و لكن حتى برهان استحالة ايجاد خوارزمية فعالة قد يكون مستحيلاً...
و هكذا من خلال مسألة كانسة الألغام نجد نفسنا نعود للمسألة الشهيرة هل NP=P ؟
و التي تعتبر من أهم و أكبر المسائل المفتوحة في الرياضيات إلى يومنا هذا , لمزيد من المعلومات عن هذه المسألة
|