A path-finding algorithm for computing minimal-weight-matching centrosymmetry parameter

ملخص تقني: خوارزمية بحث عن مسار لحساب معامل التماثل المركزي ذي الوزن الأدنى

بيان المشكلة
معامل التماثل المركزي (CSP) هو مقياس يُستخدم في الديناميكا الجزيئية لتحديد النظام الهيكلي المحلي، لا سيما في تحديد العيوب في الشبكات البلورية. يُعرف الـ CSP بأنه مجموع مربعات معايير أزواج المتجهات للجيران المتقابلين: $CSP = \sum_{i=1}^{N/2} ||R_i + R_{i+N/2}||^2$، حيث $N$ هو عدد أقرب الجيران.

يتمثل التحدي الحرج في حساب الـ CSP في اختيار أزواج محددة من الجيران المتقابلين. قبل عام 2020، اعتمدت البرمجيات الموجودة على "الاختيار الجشع للحواف" (greedy edge selection) أو "المطابقة الجشعة للرؤوس" (greedy vertex matching)، وكلاهما حدده لارسنون كنهج معيب نظراً لعدم قدرتهما على ضمان الحد الأدنى العالمي. أعاد لارسن صياغة المشكلة كبحث عن "مطابقة قصوى ذات وزن أدنى" (Minimal-Weight Maximum Matching - MWM) على رسم بياني كامل الاتصال من الذرات المجاورة، حيث تكون أوزان الحواف هي $||R_i + R_j||^2$. الحل القياسي لـ MWM هو خوارزمية بلوسوم (Blossom algorithm) لإدموندز، والتي تبلغ تعقيدها الزمني $O(N^4)$. ومع ذلك، في حسابات الـ CSP، يكون عدد الجيران ($N$) صغيراً عادةً (على سبيل المثال، 8 لغلاف BCC الأول، 12 لغلاف FCC الأول، 14 لغلاف BCC الثاني). تبحث الورقة فيما إذا كان النهج البديل، وتحديداً خوارزمية البحث عن المسار باستخدام A*، يمكن أن يقدم أداءً فائقاً لهذه الأحجام المحددة والصغيرة من الرسوم البيانية رغم احتمال كون التعقيد التقاربي النظري له أسوأ.

المنهجية
يقترح المؤلفون إعادة صياغة مشكلة MWM كبحث عن أقصر مسار في رسم بياني لفضاء الحالة.

• تمثيل الحالة: تمثل عقد الرسم البياني للبحث "المطابقات الجزئية" (مجموعات من أزواج الذرات المنفصلة). وتتميز الحالة بقناع بت (bitmask) للذرات المتطابقة، ومعرّف آخر زوج مضاف ($ID_{max}$)، والوزن المتراكم ($g$)، وتقدير استدلالي للتكلفة المتبقية ($h$).
• بناء الرسم البياني: تربط الحواف بين مطابقة مكونة من $k$ زوج ومطابقة مكونة من $(k+1)$ زوج من خلال إضافة زوج ذري جديد غير متداخل. وزن الانتقال هو وزن الزوج المضاف.
• الخوارزمية: يتم استخدام خوارزمية A* لإيجاد أقصر مسار من مطابقة فارغة (0 أزواج) إلى مطابقة كاملة ($N/2$ زوج).
  • الاستدلال ($h$): عرّف المؤلفون استدلالاً مقبولاً ورتيباً يعتمد على مجموع أقصر $r$ حافة متاحة (حيث $r$ هو عدد الأزواج المتبقية للمطابقة) ذات المعرفات الأكبر من $ID_{max}$. يتم حساب هذه المصفوفة مسبقاً لضمان الكفاءة.
  • التحسينات: تم تنفيذ عدة استراتيجيات لتقليل مساحة البحث وعمليات طابور الأولويات:
    1. الحد العلوي الأولي: يوفر "المطابقة الجشعة للرؤوس" حداً علوياً أولياً ($w_U$) للوزن الأمثل.
    2. التقليم الديناميكي: يتم تحديث الحد العلوي كلما تم العثور على مطابقة كاملة.
    3. تقليم الفروع: نظراً لرتابة الاستدلال، تنتهي حلقة البحث مبكراً إذا تجاوزت التكلفة المقدرة ($g + w + h$) الحد العلوي الحالي.
    4. تكثيف الطابور: يتم تغيير حجم طابور الأولويات لإزالة المدخلات التي تتجاوز الحد العلوي الأفضل الحالي.

المساهمات الرئيسية

1. إعادة صياغة خوارزمية: تقدم الورقة صياغة جديدة لمسار البحث عن طريق إعادة صياغة MWM كبحث عن مسار A* في رسم بياني لفضاء الحالة من المطابقات الجزئية.
2. الاستدلالات المتخصصة: تطوير استدلال متخصص، مقبول ورتيب، مصمم خصيصاً لقيود الـ CSP (صغر $N$، وأوزان الحواف المرتبة) مما يسمح بالحساب المسبق الثابت.
3. التنفيذ والاختبار: تم تنفيذ الخوارزمية بكل من C++ وJulia (ضمن حزمة MDProcessing.jl). وقد تمت مقارنتها بخوارزمية بلوسوم المرجعية (من إعداد P. Larsen وD. Pereira) المتاحة في حزمة OVITO.

النتائج
أُجريت الاختبارات المرجعية على نظامين: طور سائل لـ 1000 جسيم لينارد-جونز (حيث غالباً ما يفشل الاختيار الجشع، مما يستلحزم MWM كاملاً) ونظام بلوري من 8000 ذرة نحاس (حيث ينجح الاختيار الجشع للحواف غالباً).

• الطور السائل (LJ): بالنسبة لأعداد الجيران الصغيرة ($N=8, 12, 14$)، تفوقت خوارزمية A* المحسنة على خوارزمية بلوسوم. على سبيل المثال، في نظام مكتبي مع $N=8$، استغرق تنفيذ A* بلغة C++ حوالي 2.16 مللي ثانية مقارنة بـ 4.7 مللي ثانية لخوارزمية بلوسوم. تم تحديد نقطة التعادل حيث تصبح بلوسوم أسرع بين 14 و16 ذرة.
• الطور البلوري (Cu): في الأنظمة ذات التماثل العالي حيث غالباً ما يعطي "الاختيار الجشع للحواف" (GES) الحل الأمثل مباشرة، كان أداء خوارزمية بلوسوم مع GES كخطوة أولية هو الأفضل لـ $N=12$. ومع ذلك، بالنسبة لـ $N=8, 14,$ و$16$، كان نهج A* أسرع بشكل ملحوظ (على سبيل المثال، لـ$N=14$، استغرق A* حوالي 39.9 مللي ثانية مقابل 80.1 مللي ثانية لبلوسوم على النظام المكتبي).
• أداء اللغة: يعد تنفيذ Julia منافساً لنسخة C++، حيث أظهر تباطؤاً بنسبة ضئيلة فقط، ويُعزى ذلك إلى أعباء التشغيل (runtime overheads).

الأهمية والادعاءات
تدعي الورقة أنه بالنسبة للمجال المحدد لحساب معامل التماثل المركزي (CSP)، حيث يكون عدد الجيران عادةً صغيراً (8–14)، فإن نهج البحث عن مسار A* مع استراتيجيات التقليم المصممة خصيصاً يعد بديلاً قابلاً للتطبيق وغالباً ما يكون متفوقاً على خوارزمية بلوسوم لإدموندز.

• يشير المؤلفون إلى أنه بينما قد يكون التعقيد الزمني في أسوأ الحالات لـ A* ($O(b^{N/2})$) أعلى نظرياً من خوارزمية بلوسوم ($O(N^4)$)، فإن الثوابت الأصغر والتقليم الفعال في سياق الـ CSP المحدد يؤديان إلى تنفيذ أسرع لأعداد الجيران النموذجية.
• تقترح الورقة أن خوارزمية A* "تستحق النظر إليها كالتنفيذ الافتراضي لـ MWM" لحسابات الـ CSP، لا سيما عندما يكون $N < 16$.
• يقترح المؤلفون بتواضع نهجاً هجيناً—باستخدام الاختيار الجشع للحواف أولاً (كما في عمل لارسن الأصلي) ثم العودة إلى خوارزمية A* المقترحة فقط عند الضرورة—مما قد يحسن الأداء بشكل أكبر، خاصة في الأنظمة البلورية عالية التماثل.