🤖 machine learning

CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs

تقدم هذه الورقة مشروع CayleyPy، الذي يجمع بين التعلم المعزز وطرق مسافة الانتشار لحل مسألة إيجاد المسار بكفاءة على رسوم كايلي البيانية الضخمة، متجاوزاً بنجاح الأدوات الكلاسيكية مثل GAP، ومقدماً دليلاً قوياً على حدسية OEIS-A186783 المتعلقة بقطر الزمرة المتناظرة، ومؤسساً حدوداً نظرية جديدة مع دعوة المجتمع للمشاركة من خلال تحديات Kaggle.

المؤلفون الأصليون: A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii

نُشر 2026-05-19

📖 5 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii, V. Zamkovoy, L. Cheldieva, I. Koltsov, A. Sychev, A. Eliseev, S. Nikolenko, N. Narynbaev, R. Turtayev, N. Rokotyan, S. Kovalev, A. Rozanov, V. Nelin, S. Ermilov, L. Shishina, D. Mamayeva, A. Korolkova, K. Khoruzhii, A. Romanov

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

الصورة الكبيرة: البحث عن أقصر طريق للعودة إلى المنزل في متاهة المرايا

تخيل أنك في متاهة عملاقة ولانهائية. لكن هذه ليست متاهة عادية بجدران؛ إنها متاهة مصنوعة من القواعد. في كل مرة تخطو فيها خطوة، تتبع قاعدة محددة تغير موقعك. في الرياضيات، يسمى هذا مخطط كلي (Cayley graph).

الهدف من هذه الورقة البحثية هو حل نوع معين من المتاهات: متاهة LRX. هذه المتاهة مبنية باستخدام قواعد خلط مجموعة أوراق اللعب (أو تبديل الأرقام).

القاعدة L: إزاحة كل شيء خطوة واحدة إلى اليسار.
القاعدة R: إزاحة كل شيء خطوة واحدة إلى اليمين.
القاعدة X: تبديل أول عنصرين.

التحدي هو: إذا بدأت بمجموعة أوراق لعب بترتيب فوضوي، فما هو أطول تسلسل من حركات اليسار (Left)، واليمين (Right)، والتبديل (Swap) لإعادتها إلى الترتيب المثالي؟

المشكلة: المتاهة أكبر من أن يستوعبها البشر (والحواسيب القديمة)

بالنسبة لمجموعة صغيرة من أوراق اللعب، يمكن لإنسان أو برنامج كمبيوتر قياسي (مثل برنامج الرياضيات الشهير GAP) معرفة الحل. ولكن مع زيادة عدد الأوراق ( $n$ )، ينفجر عدد الترتيبات الممكنة.

بالنسبة لـ $n=20$ ، تكون المتاهة ضخمة.
بالنسبة لـ $n=100$ ، تكون المتاهة كبيرة جداً لدرجة أن مساراتها تفوق عدد الذرات في الكون.

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

الحل: تعليم الذكاء الاصطناعي كيفية "تخمين" الطريق

قام المؤلفون ببناء نظام يسمى CayleyPy RL. فكر في الأمر كتدريب روبوت للتنقل في المتاحة. لقد استخدموا طريقة تسمى التعلم التعزيزي (Reinforcement Learning - RL).

إليك كيف دربوا الروبوت، باستخدام تشبيه بسيط:

1. "الإحماء" (مسافة الانتشار - Diffusion Distance)
تخيل أنك أسقطت قطرة حبر في كأس من الماء. ينتشر الحبر بشكل عشوائي. إذا كنت تريد معرفة مدى بعد نقطة معينة عن المركز، يمكنك رؤية الوقت الذي يستغرقه الحبر للوصিং إليها.

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

2. "التدريب الذكي" (التعلم التعزيزي)
بعد ذلك، علموا الذكاء الاصطناعي أن يكون أكثر ذكاءً. بدلاً من مجرد التخمين بناءً على المسارات العشوائية، استخدموا تقنية تسمى التعلم العميق لـ Q (Deep Q-Learning).

تخيل أن الذكاء الاصطناعي يلعب لعبة يحصل فيها على "عقوبة" مقابل كل خطوة يتخذها. هو يريد الوصول إلى خط النهاية بأقل عدد من العقوبات.
جرب الذكاء الاصطناعي حركات مختلفة، ورأى أي منها يقربه من الهدف، وقام بتعديل "دماغه" (الشبكة العصبية) لتقديم تخمينات أفضل.
الابتكار: قاموا بدمج حدس "انتشار الحبر" مع منطق "لعب الألعاب". ساعد هذا الذكاء الاصطناعي على تجنب الوقوع في "النهايات المسدودة المحلية" (local minima) التي عادة ما تحبط الخوارزميات الأبسط.

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

بدلاً من ذلك، أرسل المؤلفون فريقاً من المستكشفين (شعاع - beam).
عند كل تقاطع، ينقسم الفريق. هم يحتفظون بأفضل 10,000 مسار واعد ويرمون المسارات السيئة.
من خلال الحفاظ على فريق ضخم (ملايين المسارات في بعض الحالات)، يضمن الذكاء الاصطناعي أنه حتى لو تاه معظم المستكشفين، فإن واحداً منهم على الأقل سيجد المسار الأقصر المثالي.

"الخدعة السحرية" (خدعة X)**

اكتشف المؤلفون اختصاراً صغيراً مضحكاً. في الكود الخاص بهم، أضافوا سطراً واحداً من المنطق:

إذا كان أول ورقتين في الترتيب الصحيح بالفعل، فلا تقم بتبديلهما.

يبدو هذا الأمر بديهياً للإنسان، لكنه بالنسبة للكمبيوتر كان تغييراً جذرياً. هذه القاعدة الصغيرة، التي أطلقوا عليها اسم "خدعة X" (X-trick)، سمحت لذكائهم الاصطناعي بحل متاهات مكونة من 100 ورقة ( $n=100$ ).

بدون الخدعة: استطاع الذكاء الاصطناعي التعامل مع حوالي 40 ورقة فقط.
مع الخدعة: تعامل مع أكثر من 100 ورقة، متفوقاً على برنامج الكمبيوتر القديم (GAP) الذي تعطل عند حوالي 20 ورقة.

ماذا أثبتوا؟ (الجزء الرياضي)**

بعيداً عن مجرد بناء برنامج حل سريع، استخدموا ذكاءهم الاصطناعي للقيام باكتشافات حول رياضيات هذه المتاهات:

فرضية "رقم الإله" (God's Number): هناك تخمين شهير في الرياضيات يقول إن أصعب عملية خلط لـ $n$ من الأوراق تتطلب بالضبط $n(n-1)/2$ من الحركات. اختبر الذكاء الاصطناعي هذا لعدد كبير من الأوراق ولم يجد أبداً خلطة كانت أصعب من هذا الرقم. وهذا يدعم بقوة فكرة أن هذه الصيغة هي الحد المطلق.
الخلطة "الأطول": حددوا أكثر خلطة فوضوية ممكنة ("العنصر الأطول") وأثبتوا بالضبط كيفية تفكيكها إلى حركات.
الحدود الجديدة: أثبتوا رياضياً أن المتاهة لا يمكن أن تكون أصغر من حجم معين ولا يمكن أن تكون أكبر من حجم آخر، مما قلص الإجابة بشكل كبير.
شكل المتاهة: وجدوا أنه إذا قمت بعدّ عمليات الخلط الموجودة عند كل مسافة من البداية، فإن الأرقام لا تتبع منحنى جرسياً مثالياً (مثل التوزيع الطبيعي). بدلاً من ذلك، تتبع شكلاً غريباً وغير متماثل يسمى توزيع غومبل (Gumbel distribution).

النتائج: الذكاء الاصطنا ضد "الحرس القديم"**

تقارن الورقة طريقتهم الجديدة في الذكاء الاصطناعي بنظام جبر الكمبيوتر القياسي GAP:

GAP: يمكنه حل ما يصل إلى ~20 ورقة. يستغرق ساعات أو أياماً. المسارات التي يجدها غالباً ما تكون طويلة وغير فعالة.
CayleyPy RL (الذكاء الاصطناعي): يمكنه حل ما يصل إلى ~100 ورقة. هو أسرع بكثير. ويجد مسارات قريبة جداً من أقصر مسار نظري ممكن.

الملخص

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

لقد وضعوا أيضاً الكود الخاص بهم وتحدياتهم على منصة تسمى Kaggle، داعين الآخرين لمحاولة كسر أرقامهم القياسية والمساعدة في حل نسخ أصعب من هذه الألغاز.

ملخص تقني: CayleyPy RL: البحث عن المسارات والتعلم التعزيزي على رسوم كايلي (Cayley Graphs)

بيان المشكلة
تتناول الورقة مشكلة البحث عن المسارات في رسوم كايلي المتناهية الضخمة، مع التركيز بشكل خاص على الزمرة المتناظرة $S_n$ الناتجة عن الإزاحات الدورية اليسارية ( $L$ )، والإزاحات الدورية اليمنية ( $R$ )، وتبديل أول عنصرين ( $X$ ). هذا التكوين، المعروف باسم رسم LRX كايلي، يتوافق مع تسلسل OEIS رقم A186783. التحدي الرياضي الجوهري هو تفكيك عنصر زمرة إلى أقصر حاصل ضرب ممكن من المولدات (إيجاد أقصر مسار في الرسم)، وهذه المشكلة هي من نوع NP-hard للرسوم العامة لـ Cayley المتناهية. تعتمد أنظمة الجبر الحاسوبية الكلاسيكية، مثل GAP، على خوارزمية Schreier-Sims، والتي غالبًا ما تنتج مسارات طويلة بشكل أسي وتفشل في التعامل مع الزمر التي تتجاوز أحجامها $10^{30}$ (أي $n \approx 20$ لـ $S_n$ ). يهدف المؤلفون إلى تطوير مناهج تعتمد على الذكاء الاصطناعي قادرة على التعامل مع رسوم تصل أحجامها إلى $10^{70}$ (على سبيل المثال $n \approx 40$ إلى $100$) مع إنتاج مسارات قريبة من المثالية أو مثالية.

المنهجية
يقترح المؤلفون منهجية هجينة تجمع بين التعلم التعزيزي (RL)، وتحديدًا التعلم العميق لـ Q (DQN)، مع استراتيجية تدريب مسبق تعتمد على مسافات الانتشار (diffusion distances).

إطار عمل التعلم التعزيزي: يتم صياغة مشكلة البحث عن المسار كإيجاد أقصر مسار من الحالة $s$ إلى عنصر الوحدة $e$ . يتم نمذجة ذلك باستخدام معادلة بلمان (Bellman equation)، حيث تحقق دالة المسافة $d(s)$ العلاقة $d(s) = 1 + \min_{t \in N(s)} d(t)$ . يتم تكييف خوارزمية DQN القياسية لتقريب دالة القيمة هذه باستخدام الشبكات العصبية.
التدريب المسبق بمسافة الانتشار: لمعالجة مشكلة "المكافأة الشحيحة" والضجيج المتأصل في التهيئة القياسية لـ DQN، يقدم المؤلفون مرحلة "إحماء". يقومون بتوليد بيانات تدريب عبر مسارات عشوائية (انتشار) تبدأ من الهدف. يتم تدريب شبكة عصبية أولاً للتنبؤ بعدد الخطوات في هذه المسارات العشوائية (مسافة الانتشار).
DQN المعدلة: بعد ذلك، يتم ضبط الشبكة المدربة مسبقًا باستخدام خوارزمية DQN معدلة. ومن الأهمية بمكان أن أهداف تحديث بلمان يتم قصها (clipped) بناءً على الخطوة الزمنية $k$ التي تمت فيها زيارة الحالة لأول مرة خلال عملية توليد المسار العشوائي. هذا يمنع الشبكة من المبالغة في تقدير المسافات ويؤدي إلى استقرار التدريب.
البحث الشعاعي الموجه (Guided Beam Search): بمجرد تدريب الشبكة العصبية على تقدير المسافات، فإنها تعمل كدالة استدلالية لخوارزمية البحث الشعاعي. يحافظ البحث الشعاعي على عدد ثابت ( $W$ ) من الحالات الأكثر واعدة في كل خطوة، حيث يتم توسيع جيرانها واختيار أفضل $W$ بناءً على تنبؤات الشبكة. هذا يتجنب الوقوع في النهايات الصغرى المحلية، وهو نمط فشل شائع في البحث الجشع (greedy search).
"خدعة X" (The X-trick): تم تقديم تعديل استدلالي محدد لمولدات LRX. إذا كان أول عنصرين في التبديل مرتبين بالفعل، يتم استبعاد المولد $X$ (الذي يبدل بينهما) من مجموعة الجيران. هذا التعديل البسيط في سطر واحد يقلل مساحة البحث بشكل كبير ويحسن أوقات الاختلاط (mixing times).
عدم الرجوع للخلف (Non-backtracking): يدمج المؤلفون قيود عدم الرجوع للخلف في كل من توليد المسار العشوائي والبحث الشعاعي لتقليل التباين في تقديرات المسافة ومنع الركود في النهايات الصغرى المحلية.

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

التقدم الخوارزمي: تقدم الورقة مزيجًا مبتكرًا من التدريب المسبق بمسافة الانتشار وDQN المعدلة. يتغلب هذا النهج على قيود DQN القياسية (المكافآت الشحيحة، الأهداف الضوضائية) ويتفوق على الطرق الكلاسيكية.
معايير الأداء: نجحت الطرق المقترحة في إيجاد مسارات لرسوم LRX كايلي حتى $n \approx 44$ بدون معرفة مسبقة، وحتى $n \approx 100$ عند استخدام "خدعة X". هذا يتجاوز بشكل كبير قدرات GAP، المحدودة بـ $n \approx 20$ . وتنتج أساليب الذكاء الاصطناست مسارات أقصر وتعمل بشكل أسرع من GAP لـ $n$ المماثلة.
النتائج الرياضية والتخمينات:
- تخمين القطر: يدعم المؤلفون بقوة تخمين OEIS-A186783 بأن قطر رسم LRX كايلي هو $n(n-1)/2$ . وقد تحققوا من ذلك عبر بحث BFS شامل لـ $n \le 15$ وعبر التفكيك بالذكاء الاصطناعي لـ $n$ تصل إلى 200 (عبر تحديات Kaggle)، حيث لم يجدوا أي تفكيك أقصر من الطول المخمن.
- العنصر الأطول: حددوا عنصرًا فريدًا "أطول عنصر" $\ell_n = (1, 0, n-1, n-2, \dots, 3, 2)$ وقدموا تفكيكًا صريحًا بطول $n(n-1)/2$ .
- الحدود: تثبت الورقة حداً أدنى لقطر الرسم وهو $n(n-1)/2 - n/2 - 1$ وحداً أعلى قدره $n(n-1)/2 + 3n$ عبر خوارزمية بنائية. وتقترح خوارزمية تجريبية حداً أكثر دقة وهو $n(n-1)/2 + n/2$ .
- توزيع النمو: تشير التجارب العددية إلى أن دالة النمو لرسم LRX تتبع توزيع Gumbel منحرف لليسار للقيم الكبيرة من $n$ ، على عكس التوزيع الغاوسي الملاحظ في رسوم تبديل الجيران.
- وقت الاختلاط: بينما تتراوح أوقات الاختلاط للمسارات العشوائية القياسية بين $O(n^3)$ و $O(n^3 \log n)$ ، يخمن المؤلفون أن المسارات العشوائية المعدلة بـ "خدعة X" تختلط بشكل أسرع، بزمن تعقيد قدره $O(n^2)$ .
- الطيف: يبدو أن طيف رسم LRX يتبع توزيعًا منتظمًا.
المصادر المفتوحة والعمل الجماعي: أطلق المؤلفون مشروع "CayleyPy" وأنشأوا تحديات Kaggle لتجميع الحلول لتفكيك أطول عنصر وإيجاد خوارزميات مثالية، مما يعزز التعاون بين مجتمعات الذكاء الاصطناعي والرياضيات.

النتائج

الكفاءة: بالنسبة لـ $n=20$ ، يتطلب GAP أكثر من 41 دقيقة لإيجاد مسار بطول 217,944، بينما تجد طريقة مسافة الانتشار المسار الأمثل بطول 190 في أقل من 4 دقائق.
القابلية للتوسع: باستخدام "خدعة X"، حل النظام حالات لـ $n=100$ (حجم الرسم $\approx 10^{157}$ ) في حوالي 8.5 ساعة على وحدة معالجة رسومية واحدة، حيث وجد مسارًا بطول 16,632 (مقارنة بالقطر المخمن البالغ 4,950).
أداء النموذج: غالبًا ما تفوقت النماذج البسيطة مثل MLP و Gradient Boosting (CatBoost/XGBoost) على البنى المعقدة مثل Transformers و CNNs لهذه المهمة المحددة.
البحث الشعاعي: يعتمد معدل نجاح إيجاد المسار بشكل كبير على عرض الشعاع، حيث يظهر تحسن فائق الخطية مع زيادة حجم الشعاع، بشكل يشبه "تبادل الأفكار" في المجتمع البحثي.

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