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

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

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

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

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

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

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

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

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

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

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

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

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