اخبار

دليل بمساعدة الكمبيوتر يحل مشكلة “تلوين التعبئة”


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

قال: “بمجرد أن اكتشفنا أنه كان هناك 20 عامًا من العمل على المشكلة ، أدى ذلك إلى تغيير الصورة تمامًا”.

تجنب المبتذلة

على مر السنين ، اكتسب Heule مهنة من إيجاد طرق فعالة للبحث بين مجموعات واسعة ممكنة. يُطلق على نهجه اسم حل SAT – اختصارًا لـ “الرضا”. يتضمن إنشاء صيغة طويلة ، تسمى الصيغة المنطقية ، والتي يمكن أن يكون لها نتيجتان محتملتان: 0 أو 1. إذا كانت النتيجة 1 ، فإن الصيغة صحيحة ، وتم استيفاء المشكلة.

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

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

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

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

اعتبر هيول وسوبركاسو توسيع نطاق نهج حساب القوة الغاشمة مبتذلاً بطريقة ما. قال سوبركاسو: “كان لدينا العديد من الأفكار الواعدة ، لذلك اتخذنا عقلية” دعونا نحاول تحسين نهجنا حتى نتمكن من حل هذه المشكلة في أقل من 48 ساعة من الحساب على الكتلة “.

للقيام بذلك ، كان عليهم أن يبتكروا طرقًا للحد من عدد التركيبات التي يتعين على مجموعة الحوسبة تجربتها.

“[They] قال ألكسندر سويفر من جامعة كولورادو ، كولورادو سبرينغز ، “لا نريد فقط حلها ، ولكن لحلها بطريقة مثيرة للإعجاب”.

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

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

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

زر الذهاب إلى الأعلى