ثعبان في الصندوق

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

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

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

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

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

يُعرف الحد الأقصى لطول الثعبان في الصندوق للأبعاد من واحد إلى ثمانية؛ وهو

1، 2، 4، 7، 13، 26، 50، 98 (التسلسل A099155 في OEIS ) .

بعد هذا الطول، لا يُعرف الطول الدقيق لأطول ثعبان؛ وأفضل الأطوال التي تم العثور عليها حتى الآن للأبعاد من تسعة إلى ثلاثة عشر هي

191، 379، 746، 1476، 2932. ^{[ 1 ]}

بالنسبة للدورات (مسألة الملف داخل الصندوق)، لا يمكن أن توجد دورة في مكعب فائق ذي بُعد أقل من اثنين. أقصى أطوال لأطول الدورات الممكنة هي

0، 4، 6، 8، 14، 26، 48، 96 (التسلسل A000937 في OEIS ) .

بعد هذا الطول، لا يُعرف الطول الدقيق لأطول دورة؛ وأفضل الأطوال التي تم التوصل إليها حتى الآن للأبعاد من تسعة إلى ثلاثة عشر هي

192، 374، 738، 1468، 2840. ^{[ 1 ]}

تُعدّ اللفائف المزدوجة حالة خاصة: وهي عبارة عن دورات يتكرر فيها النصف الثاني من بنية النصف الأول، وتُعرف أيضًا باللفائف المتناظرة . بالنسبة للأبعاد من اثنين إلى سبعة، تكون أطوال أطول اللفائف المزدوجة الممكنة هي

4، 6، 8، 14، 26، 46.

إضافة إلى ذلك، فإن أفضل الأطوال التي تم التوصل إليها حتى الآن للأبعاد من ثمانية إلى ثلاثة عشر هي

94، 186، 370، 726، 1430، 2810. ^{[ 1 ]}

في كلتا مسألتي الثعبان والملف داخل الصندوق، من المعروف أن أقصى طول يتناسب طرديًا مع 2^ ⁿ لصندوق ذي n بُعد، وذلك تقاربًا مع ازدياد n ، ويكون محدودًا من الأعلى بـ 2 ^{^n - 1.} ثابت التناسب غير معروف، وأفضل حد أدنى معروف هو 77/256 ≈ 0.30 (انظر أبوت وكاتشالسكي (1991) ). ^{[ 2 ]}

• أبوت، إتش إل؛ كاتشالسكي، إم. (1988)، "حول مسألة الثعبان في الصندوق"، مجلة نظرية التوافيق، السلسلة ب ، 45 : 13-24 ، doi : 10.1016/0095-8956(88)90051-2
• أبوت، إتش إل؛ كاتشالسكي، إم . (1991)، "حول بناء رموز الثعبان في الصندوق"، Utilitas Mathematica ، 40 : 97-116
• أليسون، ديفيد؛ باولوسما، دانيال (2016)، حدود جديدة لمسألة الثعبان في الصندوق ، arXiv : 1603.05119 ، Bibcode : 2016arXiv160305119A
• بيترمان، د.س. (2004)، حدود دنيا جديدة لمسألة الثعبان في الصندوق: خوارزمية جينية بلغة برولوج ومنهج بحث استدلالي (ملف PDF) (رسالة ماجستير)، قسم علوم الحاسوب، جامعة جورجيا
• بلاوم، ماريو؛ إتزيون، توفي (2002)، استخدام رموز الثعبان في الصندوق لتحديد المسارات بشكل موثوق في حقول المؤازرة لمحرك الأقراص ، براءة اختراع أمريكية رقم 6,496,312
• كاسيلا، د.أ.؛ بوتر، و.د. (2005)، "استخدام التقنيات التطورية للبحث عن الثعابين واللفائف"، مؤتمر IEEE لعام 2005 حول الحوسبة التطورية (CEC2005) ، المجلد  3، الصفحات 2499-2504 
• كاسيلا، د. أ. (2005)، حدود دنيا جديدة لمسألتي الثعبان في الصندوق والملف اللولبي في الصندوق (ملف PDF) (رسالة ماجستير)، قسم علوم الحاسوب، جامعة جورجيا
• دانغ، تشو؛ بازغان، كريستينا؛ كازيناف، تريستان؛ شوبان، مورغان؛ ويليمين، بيير هنري (2023). "تكييف سياسة النشر المتداخل مع بدء التشغيل الدافئ والتوقف الأمثل" . وقائع مؤتمر AAAI حول الذكاء الاصطناعي . 37 (10): 12381-12389 . doi : 10.1609/aaai.v37i10.26459 .
• دانزر، ل.؛ كلي، ف. (1967)، "طول الثعابين في الصناديق"، مجلة نظرية التوافيق ، 2 (3): 258-265 ، doi : 10.1016/S0021-9800(67)80026-7
• ديفيز، د. و. (1965)، "أطول المسارات والحلقات 'المنفصلة' في مكعب N "، معاملات IEEE للحواسيب الإلكترونية ، EC-14 (2): 261، doi : 10.1109/PGEC.1965.264259
• ديمر، كنوت (1985)، "حد أعلى جديد لطول الثعابين"، كومبيناتوريكا ، 5 (2): 109-120 ، doi : 10.1007/BF02579373 ، S2CID 30303683 
• دياز-غوميز، ب.أ.؛ هوجن، د.ف. (2006)، "مشكلة الثعبان في الصندوق: تخمين رياضي ومنهج الخوارزمية الجينية"، وقائع المؤتمر الثامن حول الحوسبة الجينية والتطورية ، سياتل، واشنطن، الولايات المتحدة الأمريكية، ص 1409-1410 ، doi : 10.1145/1143997.1144219 ، S2CID 19239490  {{citation}}: CS1 maint: موقع الناشر مفقود ( رابط )
• دوغلاس، روبرت ج. (1969)، "حدود عليا لطول الدوائر ذات الانتشار المتساوي في المكعب ذي البعد d "، مجلة نظرية التوافيق ، 7 (3): 206-214 ، doi : 10.1016/S0021-9800(69)80013-X
• Evdokimov، AA ( 1969)، “الطول الأقصى لسلسلة في وحدة مكعبة ذات أبعاد n ”، Matematicheskie Zametki ، 6 : 309–319
• كاوتز، ويليام هـ. (يونيو 1958)، "رموز التحقق من الأخطاء بمسافة الوحدة"، معاملات معهد مهندسي الراديو في الحواسيب الإلكترونية ، EC-7 (2): 179-180 ، doi : 10.1109/TEC.1958.5222529 ، S2CID 26649532 
• كيم، س.؛ نيوهوف، د. ل. (2000)، "رموز الثعبان في الصندوق كتعيينات فهرس كمية قوية"، وقائع ندوة IEEE الدولية حول نظرية المعلومات ، ص  402، doi : 10.1109/ISIT.2000.866700 ، ISBN 0-7803-5857-0، S2CID 122798425 
• كيني، د. ( 2012)، "نهج جديد لمشكلة الثعبان في الصندوق"، وقائع المؤتمر الأوروبي العشرين حول الذكاء الاصطناعي، ECAI-2012 ، ص 462-467 
• كيني، د. ( 2012)، "بحث مونت كارلو عن الثعابين واللفائف"، وقائع ورشة العمل الدولية السادسة حول الاتجاهات متعددة التخصصات في الذكاء الاصطناعي، MIWAI-2012 ، ص 271-283 
• كلي، ف. (1970)، "ما هو أقصى طول لثعبان ذي أبعاد د ؟"، المجلة الرياضية الأمريكية الشهرية ، 77 (1): 63-65 ، doi : 10.2307/2316860 ، JSTOR 2316860 
• كوتشوت، كيه جيه ( 1996)، "رموز الثعبان في الصندوق للأبعاد 7"، مجلة الرياضيات التوافقية والحوسبة التوافقية ، 20 : 175-185
• لوكيتو ، أ.؛ فان زانتن، أ.ج. (2001)، "حد أعلى جديد غير تقاربي لرموز الثعبان في الصندوق"، مجلة الرياضيات التوافقية والحوسبة التوافقية ، 39 : 147-156
• باترسون، كينيث ج.؛ تولياني، جوناثان (1998)، "بعض رموز الدوائر الجديدة"، معاملات IEEE في نظرية المعلومات ، 44 (3): 1305-1309 ، doi : 10.1109/18.669420
• بوتر، دبليو دي؛ روبنسون، آر دبليو؛ ميلر، جيه إيه؛ كوتشوت، كيه جيه؛ ريديس، دي زد (1994)، "استخدام الخوارزمية الجينية لإيجاد رموز الثعبان في الصندوق"، وقائع المؤتمر الدولي السابع حول التطبيقات الصناعية والهندسية للذكاء الاصطناعي وأنظمة الخبراء ، أوستن، تكساس، الولايات المتحدة الأمريكية، الصفحات 421-426 {{citation}}: CS1 maint: موقع الناشر مفقود ( رابط )
• سنيفيلي، إتش إس (1994)، "مسألة الثعبان في الصندوق: حد أعلى جديد"، الرياضيات المتقطعة ، 133 ( 1-3 ): 307-314 ، doi : 10.1016/0012-365X(94)90039-6
• سولوفييفا، ف. إ. (1987)، "حد أعلى لطول الدورة في مكعب وحدة ذي أبعاد ن "، Metody Diskretnogo Analiza (باللغة الروسية)، 45 : 71-76 ، 96-97
• توهي، دي آر؛ بوتر، دبليو دي؛ كاسيلا، دي إيه (2007)، "البحث عن رموز الثعبان في الصندوق باستخدام نماذج التقليم المتطورة"، وقائع المؤتمر الدولي لعام 2007 حول الأساليب الجينية والتطورية (GEM'2007) ، لاس فيغاس، نيفادا، الولايات المتحدة الأمريكية، الصفحات 3-9 {{citation}}: CS1 maint: موقع الناشر مفقود ( رابط )
• Wojciechowski, J. (1989), "حد أدنى جديد لرموز الثعبان في الصندوق"، Combinatorica ، 9 (1): 91–99 ، doi : 10.1007/BF02122688 ، S2CID 9450370 
• يانغ، يوان شنغ؛ صن، فانغ؛ هان، سونغ (2000)، "خوارزمية بحث عكسي لمسألة الثعبان في الصندوق"، مجلة جامعة داليان للتكنولوجيا ، 40 ( 5): 509-511
• زيمور، جيل (1997)، "حد أقصى لحجم الثعبان في الصندوق"، كومبيناتوريكا ، 17 (2): 287-298 ، doi : 10.1007/BF01200911 ، S2CID 1287549 
• زينوفيك، آي.؛ كرونينغ، د.؛ شيبيرياك، ي. (2008)، "حساب رموز غراي التوافقية الثنائية عبر البحث الشامل باستخدام خوارزميات حل SAT"، معاملات IEEE في نظرية المعلومات ، 54 (4): 1819-1823 ، doi : 10.1109/TIT.2008.917695 ، hdl : 20.500.11850/11304 ، S2CID 2854180 

• كيني، ديفيد (2012)، صفحة أبحاث الثعبان في الصندوق (جامعة كيوتو)
• وايسشتاين، إريك دبليو ، "الأفعى" ، عالم الرياضيات
• xkcd : "مشكلة الثعبان في الصندوق"