یک بازی SAT Based :

   
نام نویسنده:
|
دسته بندی:
|
یک بازی SAT Based :


نسخه انتخابی مساله با توجه به اینکه فرمول داده شده قابل قبول است یا خیر می تواند به راحتی حدث زده شود . برای k=3 و بزرگتر از مساله SAT به NP-Complete بودن شهرت دارد . و مساله NP چیزی است که شما هم می توانید آن را در یک پیشنهاد حل برای زمان های چند جمله ای چک بکنید اما ، اینطور نیست که حتما در همان زمان های چند جمله ای راه حل ۀن را پیدا کنید . مساله SAT کاملا در NP قرار می گیرد زیرا اگر من تعدادی کمیت به متغییر بدهم به راحتی خواهید فهمید که فرمول درست است . و اینکه معادله در کدام حالت درست است .
بخش "Complete" نوشته هم اینجا وارد کار می شود زیرا اگر شما بتوانید مساله SAT را در زمان های چند جمله ای حل بکنید بدین ترتیب تمامی مسائل NP می توانند در زمان های چند جمله ای حل بشوند . و اینچنین است که SAT نمایانگر تمامی مسائل موجود در NP می باشد .
خب می توان به اینگونه مسائل به چشم یک مشکل بسیار بزرگ و مساله ای غیر قابل حل شدن نگاه کرد اما ، چطور می شود که درک بهتری از آن به دست آورد ؟
Olivier Bailleux از دانشگاه Universite de Bourgogne Franche-Comte بازی جالبی را اختراع کرده است که برابر با همان مساله SAT می باشد .
خب حالا در این قسمت نحوه کار کردن آن را هم توضیح می دهیم . پیکربندی شروع با مجموعه ای از بسته های با ظاهری گرد و چهار گوش در رنگ هایی خاص آغاز می شود . تمامی کاری که بازیکن باید انجام بدهد این است که تمامی شکل های گرد یا چهار گوش یک رنگ خاص را از میان بردارد . همین . و در پایان پیکر بندی به گونه ای خواهد بود که در هر رنگ یک شکل ( گرد یا چهار گوش ) وجود خواهد داشت و در هر جعبه نیز حداقل یک شکل قرار خواهد گرفت .
ترتیبی که شکل ها در آن برکنار شده اند و تفاوتی حاصل نشده است تنها شروع کار را نشان می دهند و این مرحله پایانی است که دارای اهمیت می باشد .

satgame
همه پیکربندی ها آغازین می توانند تبدیل به مرحله نهایی مورد انتظار بشوند و آنهایی که به این مهم دست یابند کنش پذیر خوانده می شوند .
بازی کردن این بازی خیلی هم راحت نیست اما هر چه باشد بازی سرگرم کننده ای است . معمولا نظریه پردازان پیچیده به انجام این بازی مبادرت دارند و برخی هم با NP سرگرم می شوند اما در این مورد خاص خود بازی از SAT مشتق شده است و بنابراین NP کاملی می باشد .
از چه نظر مشابه مساله SAT می باشد ؟
هر یک از بسته ها عبارتی منطقی است . هر رنگ هم یک همخوان متغیر چهارگوش برای معادلات صحیح و برای معادلات غلط به صورت گرد است .
پیکربندی ورودی می تواند به عنوان یک عبارت منطقی خواهد شود – یک چهارگوش ، متغیر مثبت و یک دایره متغیر منفی است . بنابراین پیکربندی ورودی در شکلی که ارائه شده است به صورت زیر خواهد بود .
(r or  b or  not p)
  و ( not r or  b or not p)
   و  (r or  not b or  not p)
و  (not r or not b or not p)
و (p or y)
      و (r or not y)
و (b or not y)
مساله SAT برای پیدا کردن یک معادله درست نادرست r ، b و  p است و در حالتی که هر بند صحیح باشد بایستی همه آنها برای صحیح بودن AND درست بوده باشند .
با برگشت به مساله بازی می بینیم که این امر برابر با قرار دادن هر رنگ برای یکی از شکل ها می باشد . در صورتی که شما بتوانید این کار را بکنید و در هر جعبه حداقل یک شکل ( گرد یا چهار گوش ) داشته باشید در این صورت این جعبه صحیح ارزیابی می شود . از آنجایی که آن OR هر یک از متغیر ها می باشد ، شما برای صحیح بودن کل جعبه ها تنها به یکی از این موارد نیاز دارید .
اگر کمی بیشتر در مورد آن فکر بکنید مطمعنا به علت آن پی خواهید برد .
اگر شما این بازی را انجام بدهید باز هم خواهید گفت که سختی های مساله SAT شیرین تر از حل کردن معادلات این بازی بوده است .

satgameicon
یک پیام هشدار : هیچگاه تعداد رنگ های موجود در بازی را فقط به خاطر مشاهده نحوه عمل اشیاء به دو رنگ کاهش ندهید زیرا مساله SAT در دو متغیر ، P است نه NP .
الان چیزی که باقی می ماند این است که شما به کسی نیاز دارید تا این کار را به عنوان یک بازی وب یا موبایل اجرا بکند و همه افراد می توانند از این بازی لذت ببرند .

اخبار مرتبط

دیگر اخبار نویسنده

ارسال نظر


شخصی سازی Close
شما در این صفحه قادر به شخصی سازی نمیباشید