برنامج "قصير النظر" يشق المشاكل المعقدة

خوارزمية الكمبيوتر الجديدة تخلق مشاكل حساب لا توصف

طريقتان من 1152 طريقة مختلفة لتلوين العقد لنفس الشبكة بأربعة ألوان. قد لا يكون للعُقد المتصلة بخط معين نفس اللون. © MPIDS
قراءة بصوت عال

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

في الطريقة الجديدة ، ينظر العلماء فقط إلى أقسام فردية من المشكلة ويعملون عليها الواحدة تلو الأخرى. حتى الآن ، كانوا في كل خطوة حول الخريطة بأكملها أو كامل سودوكو في الرأي. يمكن الإجابة على العديد من الأسئلة من الفيزياء والرياضيات وعلوم الكمبيوتر لأول مرة. الطريقة الجديدة ظهرت الآن في مجلة New Journal of Physics.

كم من "الألوان" هناك؟

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

يتعين على الباحثين بعد ذلك الإجابة عن سؤال واحد فقط: ما عدد الطرق التي يمكن بها تلوين العقد إذا تم إعطاء عدد معين من الألوان؟ الشرط الوحيد: قد لا يكون للعقد المتصلة بخط معين نفس اللون. اعتمادًا على التطبيق ، يفترض "لون" العقدة معنى مختلف تمامًا. في حالة الخريطة ، يعني "اللون" في الواقع اللون ، في سودوكو ، "الألوان" عبارة عن أرقام مختلفة.

خريطة ألمانيا مع التمثيل المقابل كشبكة. أعلى اليمين: سودوكو مبسط من ثلاث مرات ثلاثة صناديق ("المربع السحري"). أسفل اليمين: التمثيل المقابل كشبكة. "1" يتوافق مع "أحمر" ، "2" يتوافق مع "أزرق" و "3" يتوافق مع "أصفر". IDS MPIDS

مليارات السنين من وقت الحوسبة

يوضح فرانك فان بوسل من معهد ماكس بلانك للديناميكيات والتنظيم الذاتي (MPIDS) أن "الخوارزمية السابقة تنسخ الشبكة بالكامل في كل خطوة حسابية ، وتغيير جانب واحد فقط في كل مرة". كلما زاد عدد العقد ، يزداد وقت الحوسبة بشكل كبير. على سبيل المثال ، بالنسبة لشبكة مربعة بحجم رقعة الشطرنج ، يقدر أن تكون مليارات عديدة من السنين. عرض

تعمل "الرؤية القصيرة" على تبسيط العمليات الحسابية

الخوارزمية الجديدة التي طورها علماء G Wissenschaftlerttingen أسرع بكثير. يقول ديني فليغنر من MPIDS "حسابنا لشبكة الشطرنج لا يستغرق سوى سبع ثوانٍ". الخدعة: مع الطريقة الجديدة ، ينتقل الباحثون من عقدة إلى عقدة عبر الشبكة. كما لو كان برنامج الكمبيوتر قصير النظر ، فإنه يأخذ فقط في الاعتبار العقدة التالية. الشبكة بالكامل ليس لديها في الرأي. على سبيل المثال ، في العقدة الأولى ، لا يمكن أخيرًا اختيار اللون. لأنه سيحتاج إلى معرفة كيفية اتصال جميع العقد الأخرى.

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

التطبيق في الحالات المعقدة

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

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

(معهد ماكس بلانك للديناميات والتنظيم الذاتي ، 09.02.2009 - NPO)