مشاكل حركة الحصى

تُعرف مسائل حركة الحصى ، أو حركة الحصى على الرسوم البيانية ، بأنها مجموعة من المسائل المترابطة في نظرية الرسوم البيانية، والتي تتناول حركة عدة أجسام ("حصى") من رأس إلى آخر في رسم بياني، مع وجود قيد على عدد الحصى التي يمكن أن تشغل رأسًا في أي وقت. تظهر مسائل حركة الحصى في مجالات مثل تخطيط حركة الروبوتات المتعددة (حيث تمثل الحصى الروبوتات) وتوجيه الشبكات (حيث تمثل الحصى حزم البيانات). أشهر مثال على مسألة حركة الحصى هو لغز الـ 15 الشهير، حيث يجب إعادة ترتيب مجموعة غير مرتبة من 15 بلاطة داخل شبكة 4×4 عن طريق تحريك بلاطة واحدة في كل مرة.

الصياغة النظرية

الصيغة العامة لمسألة حركة الحصى هي حركة الحصى على الرسوم البيانية ^{[ 1 ]} المصاغة على النحو التالي:

يترك $G=(V,E)$ ليكن رسمًا بيانيًا مع $n$ الرؤوس. ليكن $P=\{1,\ldots ,k\}$ كن مجموعة من الحصى مع $k<n$ . ترتيب الحصى هو رسم تخطيطي $S:P\rightarrow V$ بحيث $S(i)\neq S(j)$ ل $i\neq j$ خطوة $m=(p,u,v)$ يتضمن نقل الحصى $p$ من الرأس $u$ إلى الرأس المجاور غير المشغول $v$ تتمثل مشكلة حركة الحصى على الرسوم البيانية في اتخاذ قرار، بالنظر إلى ترتيبين. $S_{0}$ و $S_{+}$ ، ما إذا كان هناك تسلسل من الحركات التي تُحدث تحولاً $S_{0}$ داخل $S_{+}$ .

الاختلافات

تُقيّد الاختلافات الشائعة في هذه المسألة بنية الرسم البياني لتكون كالتالي:

شجرة ^[²^]
شبكة مربعة ، ^{[ 3 ]}
رسم بياني ثنائي الاتصال . ^{[ 4 ]}

هناك مجموعة أخرى من الاختلافات تأخذ في الاعتبار الحالة التي تكون فيها بعض ^{[ 5 ]} أو كل ^{[ 3 ]} الحصى غير مصنفة وقابلة للتبديل.

لا تسعى نسخ أخرى من المشكلة إلى إثبات إمكانية الوصول فحسب، بل تسعى أيضًا إلى إيجاد تسلسل (مثالي محتمل) من التحركات (أي خطة) التي تقوم بالتحويل.

تعقيد

من المعروف أن إيجاد أقصر سلسلة حلول في مسألة حركة الحصى على الرسوم البيانية (مع حصى مُصنّفة) يُعدّ مسألة صعبة من فئة NP ^{[ 6 ]} وصعبة من فئة APX ^{[ 3 ]} . يمكن حلّ المسألة غير المُصنّفة في وقت متعدد الحدود عند استخدام مقياس التكلفة المذكور أعلاه (تقليل إجمالي عدد التحركات إلى الرؤوس المجاورة)، ولكنها تُعدّ مسألة صعبة من فئة NP بالنسبة لمقاييس التكلفة الطبيعية الأخرى ^{[ 3 ] .}

مراجع

↑ كورنهاوزر، دانيال؛ ميلر، غاري ؛ سبيراكيس، بول (1984)، "تنسيق حركة الحصى على الرسوم البيانية، وقطر مجموعات التبديل، والتطبيقات"، وقائع الندوة السنوية الخامسة والعشرين حول أسس علوم الحاسوب (FOCS 1984) ، مطبعة جمعية مهندسي الكهرباء والإلكترونيات، الصفحات 241-250 ، CiteSeerX 10.1.1.17.3556 ، doi : 10.1109/sfcs.1984.715921 ، ISBN 978-0-8186-0591-8، S2CID 40949575
↑ أوليتا، ف.؛ مونتي، أ.؛ بارينتي، م.؛ بيرسيانو، ب. (1999)، "خوارزمية خطية الزمن لجدوى حركة الحصى على الأشجار"، Algorithmica ، 23 (3): 223-245 ، doi : 10.1007/PL00009259 ، MR 1664708 ، S2CID 672515
1 2 3 4 كالينيسكو، جرويا؛ دوميتريسكو، أدريان؛ باش، يانوس (2008)، “إعادة التشكيل في الرسوم البيانية والشبكات”، مجلة SIAM للرياضيات المنفصلة ، 22 (1): 124–138 ، CiteSeerX 10.1.1.75.1525 ، دوى : 10.1137 / 060652063 ، MR 2383232
↑ سورينك، بافيل (2009)، "نهج جديد لتخطيط المسار لعدة روبوتات في الرسوم البيانية ثنائية الاتصال"، وقائع المؤتمر الدولي لهندسة الروبوتات والأتمتة (ICRA 2009) ، IEEE، الصفحات 3613-3619 ، doi : 10.1109/robot.2009.5152326 ، ISBN 978-1-4244-2788-8، S2CID 6621773
↑ باباديميتريو، كريستوس هـ .؛ راغافان، برابهاكار ؛ سودان، مادهو ؛ تاماكي، هيساو (1994)، "تخطيط الحركة على الرسم البياني"، وقائع الندوة السنوية الخامسة والثلاثين حول أسس علوم الحاسوب (FOCS 1994) ، مطبعة جمعية مهندسي الكهرباء والإلكترونيات، الصفحات 511-520 ، doi : 10.1109/sfcs.1994.365740 ، ISBN 978-0-8186-6580-6، S2CID 1998334
↑ راتنر، دانيال؛ وارموث، مانفريد (1990)، "الـ $(n^{2}-1)$ "مسائل الألغاز ومسائل إعادة التوطين ذات الصلة"، مجلة الحوسبة الرمزية ، 10 (2): 111-137 ، doi : 10.1016/S0747-7171(08)80001-6 ، MR 1080669

[Kornhauser-1] كورنهاوزر، دانيال؛ ميلر، غاري ؛ سبيراكيس، بول (1984)، "تنسيق حركة الحصى على الرسوم البيانية، وقطر مجموعات التبديل، والتطبيقات"، وقائع الندوة السنوية الخامسة والعشرين حول أسس علوم الحاسوب (FOCS 1984) ، مطبعة جمعية مهندسي الكهرباء والإلكترونيات، الصفحات 241-250 ، CiteSeerX 10.1.1.17.3556 ، doi : 10.1109/sfcs.1984.715921 ، ISBN 978-0-8186-0591-8، S2CID 40949575

[Auletta-2] أوليتا، ف.؛ مونتي، أ.؛ بارينتي، م.؛ بيرسيانو، ب. (1999)، "خوارزمية خطية الزمن لجدوى حركة الحصى على الأشجار"، Algorithmica ، 23 (3): 223-245 ، doi : 10.1007/PL00009259 ، MR 1664708 ، S2CID 672515

[Calinescu-3] 1 2 3 4 كالينيسكو، جرويا؛ دوميتريسكو، أدريان؛ باش، يانوس (2008)، “إعادة التشكيل في الرسوم البيانية والشبكات”، مجلة SIAM للرياضيات المنفصلة ، 22 (1): 124–138 ، CiteSeerX 10.1.1.75.1525 ، دوى : 10.1137 / 060652063 ، MR 2383232

[Surynek-4] سورينك، بافيل (2009)، "نهج جديد لتخطيط المسار لعدة روبوتات في الرسوم البيانية ثنائية الاتصال"، وقائع المؤتمر الدولي لهندسة الروبوتات والأتمتة (ICRA 2009) ، IEEE، الصفحات 3613-3619 ، doi : 10.1109/robot.2009.5152326 ، ISBN 978-1-4244-2788-8، S2CID 6621773

[Papadimitriou-5] باباديميتريو، كريستوس هـ .؛ راغافان، برابهاكار ؛ سودان، مادهو ؛ تاماكي، هيساو (1994)، "تخطيط الحركة على الرسم البياني"، وقائع الندوة السنوية الخامسة والثلاثين حول أسس علوم الحاسوب (FOCS 1994) ، مطبعة جمعية مهندسي الكهرباء والإلكترونيات، الصفحات 511-520 ، doi : 10.1109/sfcs.1994.365740 ، ISBN 978-0-8186-6580-6، S2CID 1998334

[Ratner-6] راتنر، دانيال؛ وارموث، مانفريد (1990)، "الـ $(n^{2}-1)$ "مسائل الألغاز ومسائل إعادة التوطين ذات الصلة"، مجلة الحوسبة الرمزية ، 10 (2): 111-137 ، doi : 10.1016/S0747-7171(08)80001-6 ، MR 1080669

[ 1 ]

[

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

اللغة	العربية (RTL)
روابط موسوعية	28 رابطاً
المصدر الأصلي	ويكيبيديا ↗