في فرز الفطائر تختلف الأحجام، وتقتصر الحركة على قلب جزء يبدأ من أعلى الرصة. رياضيًا هي عملية عكس بادئة من ترتيب العناصر. [2]
سنستعمل ست بطاقات مرقمة بدل طعام، ونقرأها من أعلى إلى أسفل: 3,6,1,5,2,4. الهدف هو 1,2,3,4,5,6. سنصل إليه بخطة بسيطة من ثماني حركات، ثم نجد طريقًا أقصر يتكون من ست حركات ونثبت بالحصر أن خمسًا لا تكفي لهذا المدخل.
الخلاصة السريعة
- قلب أول
kعناصر يعكس ترتيبها فقط، ويترك ما بعدها في موضعه. - خطة مثالنا البسيطة تستخدم الأطوال
2,6,3,5,3,4,2,3، فتصل إلى الترتيب المطلوب. - الطريق الأقصر الذي وجده بحثنا يستخدم
5,4,6,3,4,5؛ صلاحية الخطة الأولى لا تثبت أنها الأقصر. - فحصنا الترتيبات الستة العناصر جميعها، وعددها 720؛ وافقت الخطة البسيطة العدد الأدنى في 297 منها.
- رفض فحص مستقل كل سلاسل القلب الأقصر من ست لمثالنا، وعددها 3906؛ النتائج تخص أحجامًا متميزة بلا اتجاه للوجه.
حدّد بالضبط ما الذي تقلبه الحركة
اختر طولًا من اثنين إلى ستة. قلب المقدمة بطول ثلاثة يحول بداية المثال 3,6,1 إلى 1,6,3، مع بقاء الذيل 5,2,4 كما كان. أما نقل الرقم ستة إلى آخر القائمة مباشرة فليس حركة مسموحة؛ يجب إنجازه عبر قلب مقدمات كاملة.
القلب بطول واحد لا يغير شيئًا، لذلك استبعدناه من الحركات التي نعدها. والقلب بطول أكبر من عدد العناصر خطأ في المدخلات. الأرقام رتب من واحد إلى ستة تظهر مرة واحدة؛ الرصة التي تكرر رقمًا أو تحذف رتبة ليست مدخلًا لهذا النموذج.
ثبّت الأكبر ثم قلّص الجزء الجاري
تعرض محاضرة كارنيغي ميلون طريقة رفع أكبر عنصر لم يُرتب إلى الأعلى، ثم قلب الجزء الجاري لوضعه في أسفله. يتكرر ذلك على الجزء الأقصر. [1]
في البداية يقع ستة في الموضع الثاني، فنقلب أول عنصرين ليصبح في الأعلى. نقلب الستة بعدها فيستقر عند القاعدة. الحالة الآن 4,2,5,1,3,6. نعامل الستة كجزء منتهٍ؛ لن تشملها قلباتنا اللاحقة.
نبحث عن خمسة داخل العناصر الخمسة الأولى. يقع في الموضع الثالث، فنقلب ثلاثة ثم خمسة. نصل إلى 3,1,4,2,5,6. تكرر الخطة الفكرة للأربعة، ثم الثلاثة، وتجد أن الاثنين أصبحا مرتبين دون حركة إضافية. يبين السجل كل حالة فعلية، لا مجرد عدد إجمالي.
| الخطوة | طول المقدمة المقلوبة | الحالة من الأعلى إلى الأسفل |
|---|---|---|
| 0 | — | 3,6,1,5,2,4 |
| 1 | 2 | 6,3,1,5,2,4 |
| 2 | 6 | 4,2,5,1,3,6 |
| 3 | 3 | 5,2,4,1,3,6 |
| 4 | 5 | 3,1,4,2,5,6 |
| 5 | 3 | 4,1,3,2,5,6 |
| 6 | 4 | 2,3,1,4,5,6 |
| 7 | 2 | 3,2,1,4,5,6 |
| 8 | 3 | 1,2,3,4,5,6 |
إذا استقر الأكبر المطلوب في آخر الجزء، نتجاوز حجمه. وإن كان في أوله، تكفي قلبة واحدة لوضعه أسفله. هذا يوفر حركات، ولا يضمن الطريق الأدنى.
لعدد n≥2، تحتاج هذه الطريقة إلى 2n−3 قلبات على الأكثر: حتى قلبتين لكل حجم من n إلى ثلاثة، وقلبة واحدة للعنصرين الأخيرين. [1]
عند ستة عناصر يعطي الحد تسعًا. سجلنا استعمل ثمانيًا؛ الحد الأعلى ليس وعدًا بأن كل مدخل سيستهلكه. المدخل المرتب مسبقًا يحتاج صفرًا في تنفيذنا، والمدخل ذو العنصرين 2,1 يحتاج قلبة واحدة فقط.
ابحث في الحالات بدل تكرار القرار نفسه
اعتبر كل ترتيب من الستة حالة مستقلة. تصل حركة واحدة بين حالتين إذا أمكن تحويل إحداهما إلى الأخرى بقلب مقدمة طولها اثنان أو ثلاثة أو أربعة أو خمسة أو ستة. لكل حالة خمسة جيران مختلفين، والقلب يعكس نفسه: تطبيق الطول نفسه مرتين يعيد الرصة الأصلية.
بدأ برنامجنا من الهدف المرتب وحفظ له مسافة صفر. أضاف الجيران بمسافة واحدة إلى طابور، ثم جيرانهم الجدد بمسافة اثنتين، وهكذا. لا يعيد إدخال حالة رآها من قبل. بما أن كل حافة تمثل حركة واحدة، تُكتشف الحالات على طبقات متزايدة؛ لا يمكن أن يظهر لاحقًا طريق أقصر من طبقة الاكتشاف الأولى.
حفظنا مع كل حالة الطول الذي يعيدها إلى الحالة السابقة الأقرب للهدف. تسمح قابلية القلب للعكس باستعادة المسار من مدخلنا نحو الهدف رغم أن البحث بدأ من الهدف. أعطى ذلك السجل التالي.
| الخطوة | طول المقدمة المقلوبة | الحالة من الأعلى إلى الأسفل |
|---|---|---|
| 0 | — | 3,6,1,5,2,4 |
| 1 | 5 | 2,5,1,6,3,4 |
| 2 | 4 | 6,1,5,2,3,4 |
| 3 | 6 | 4,3,2,5,1,6 |
| 4 | 3 | 2,3,4,5,1,6 |
| 5 | 4 | 5,4,3,2,1,6 |
| 6 | 5 | 1,2,3,4,5,6 |
اختبار مستقل يستبعد خمس حركات أو أقل
وجود طريق من ست يعطي حدًا أعلى بست فقط. للتحقق من الحد الأدنى لمثالنا، ولدنا كل كلمة من أطوال الحركات الخمسة بطول صفر إلى خمسة. عددها 1+5+25+125+625+3125=3906. طبق برنامج آخر كل كلمة على البداية، ولم يصل أي منها إلى الهدف.
استخدم هذا الفحص تبديل موضعي طرفي الجزء تدريجيًا، بدل عكس شريحة القائمة كما يفعل مولد الجيران. ولم يحذف الكلمات التي تكرر الحركة نفسها أو تعود إلى حالة سابقة؛ أبقاها كلها حتى يغطي كل تسلسل أقصر ضمن القواعد. مع الطريق ذي الست نستنتج العدد الأدنى لهذا المدخل: ستة.
نتائج جميع الرصات الصغيرة وحدودها
عدد ترتيبات ست رتب مختلفة هو 6×5×4×3×2×1=720. وصل البحث إلى العدد كله. توزعت المسافات من الهدف بحسب أطوالها من صفر إلى سبعة على الأعداد 1,5,20,79,199,281,133,2. مجموعها 720؛ توجد حالتان فقط تحتاجان سبع حركات في هذا الحصر.
نفذنا الخطة البسيطة لكل ترتيب، ثم تحققنا من قانونية كل قلبة، واستعادة الحالة السابقة بقلبها ثانية، وانتهاء السجل إلى الهدف. لم ينزل عددها عن مسافة البحث ولم يتجاوز تسعًا. وافق المسافة في 297 حالة؛ لذلك لا نصفها بأنها أمثل دائمًا، ولا نستنتج من هذا الكسر احتمالًا لبيانات عملية لم ندرس توزيعها.
رفض التنفيذ سبعة مدخلات غير صالحة موزعة بين رتب معيبة وأطوال قلب غير مقبولة، وفحص القائمتين الفارغة والمفردة. تكلفة البحث الشامل تتغير بشدة مع عدد العناصر؛ حصر 720 حالة لا يثبت أن الطريقة مناسبة لقائمة طويلة.
تختلف النسخة ذات الوجه المعلَّم، إذ تدخل اتجاهات الأقراص ضمن الهدف. نموذجنا يتتبع ترتيب الأحجام فقط. [2]
لإعادة التجربة، احتفظ بالبداية والهدف وقائمة أطوال القلب. يمكنك فحص صحة أي حل بإعادة تشغيله خطوة خطوة، لكن وصفه بأنه الأقصر يحتاج حجة أو بحثًا يستبعد الحلول الأقصر. هذا التفريق هو ما تكشفه الرصة الصغيرة هنا، دون ادعاء تجربة مطبخ أو قياس زمن.
المصادر
- Carnegie Mellon — Pancakes With A Problem
- Bulteau, Fertin, Rusu — Pancake Flipping is Hard، تعريف المسألة في الملخص.
المدخل والرسوم وسجلات التنفيذ والحصر أُعدت لهذا المقال. أُعد النص بمساعدة الذكاء الاصطناعي، ولا يُنسب إلى مراجعة بشرية مستقلة.