تقسيم المقصلة

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 10 صور
الموسوعة الحرة
القطع بالمقصلة: عبارة عن ورقة مُحسَّنة من مستطيلات أصغر يمكن تقسيمها بشكل سليم من خلال سلسلة صحيحة من القطع من طرف إلى طرف.
القطع غير المقصلة: لا يمكن فصل هذه المستطيلات عن طريق إجراء قطع منصف واحد عبر المستوى.

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

يُعدّ تقسيم المقصلة شائعًا بشكل خاص في تصميم المخططات الأرضية في الإلكترونيات الدقيقة . ويُطلق عليه أيضًا في هذا السياق مصطلح تقسيم التقطيع أو مخطط التقطيع . [ 1 ] كما تُشكّل تقسيمات المقصلة البنية الأساسية لتقسيمات الفضاء الثنائي . وتوجد مسائل تحسينية متنوعة مرتبطة بتقسيم المقصلة، مثل: تقليل عدد المستطيلات أو الطول الإجمالي للقطع. وهذه مسائل مُختلفة من مسائل تقسيم المضلعات ، حيث تكون القطع مُقيدة لتكون قطعًا بالمقصلة.

تُعدّ عملية القطع بالمقصلة مشكلةً مشابهةً ولكنها مختلفة . في هذه المشكلة، تكون الورقة الأصلية مستطيلاً بسيطاً بدون ثقوب. يكمن التحدي في أن أبعاد المستطيلات الصغيرة مُحددة مسبقاً. عادةً ما تكون أهداف التحسين هي زيادة مساحة المستطيلات المُنتجة أو قيمتها، أو تقليل الفاقد أو عدد الأوراق المطلوبة.

حساب تقسيم المقصلة بأقصر طول حافة

في مسألة تقسيم المستطيلات ذات أقصر طول ضلع ، يتمثل الهدف في تقسيم المضلع المستقيم الأصلي إلى مستطيلات، بحيث يكون إجمالي طول الضلع في حده الأدنى. [ 2 ] : 166-167

يمكن حل هذه المشكلة في الوقت المناسبيا(ن5){\displaystyle O(n^{5})}حتى لو كان المضلع الخام يحتوي على ثقوب. تستخدم الخوارزمية البرمجة الديناميكية بناءً على الملاحظة التالية: يوجد تقسيم مستطيل قصير المدى حيث يحتوي كل جزء مستقيم أقصى على رأس من حدوده . لذلك، في كل تكرار، يوجديا(ن){\displaystyle O(n)}الخيارات الممكنة لعملية القطع التالية بالمقصلة، وهناك إجمالاًيا(ن4){\displaystyle O(n^{4})}المشاكل الفرعية.

في الحالة الخاصة التي تكون فيها جميع الثقوب متدهورة (نقاط مفردة)، يكون التقسيم المستطيل باستخدام المقصلة ذو الطول الأدنى ضعف التقسيم المستطيل ذي الطول الأدنى على الأكثر. [ 2 ] : 167-170. من خلال تحليل أكثر دقة، يمكن إثبات أن عامل التقريب في الواقع لا يتجاوز 1.75. ليس من المعروف ما إذا كان 1.75 دقيقًا، ولكن هناك حالة يكون فيها عامل التقريب 1.5. [ 3 ] لذلك، يوفر التقسيم باستخدام المقصلة تقريبًا بعامل ثابت للمسألة العامة، وهي مسألة صعبة من نوع NP.

يمكن تعميم هذه النتائج على صندوق ذي أبعاد d : يمكن إيجاد تقسيم مقصلة بأقل طول حافة في وقتيا(دن2د+1){\displaystyle O(dn^{2d+1})}ويكون الحجم الكلي ( d -1) في التقسيم الأمثل للمقصلة على الأكثر2د-4+4/د{\displaystyle 2d-4+4/d}[ 4 ] أضعاف ما هو عليه في تقسيم صندوق d الأمثل .

استخدم أرورا [ 5 ] وميتشل [ 6 ] تقنية التقسيم بالمقصلة لتطوير مخططات تقريبية متعددة الحدود لمشاكل التحسين الهندسي المختلفة.

عدد أقسام المقصلة

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

  • في بعدين، يوجد حد أعلى فييا(ن!25ن-3ن3/2){\displaystyle O\left({\frac {n!2^{5n-3}}{n^{3/2}}}\right)}يُنسب هذا الرقم إلى كنوت . وهو رقم شرودر . [ 7 ]
  • في فضاء ذي أبعاد d ، قدم أكرمان، وباريكيت، وبينتر، وروميك [ 8 ] صيغة جمع دقيقة، وأثبتوا أنها فيΘ((2د-1+2د(د-1))نن3/2){\displaystyle \Theta \left({\frac {(2d-1+2{\sqrt {d(d-1)}})^{n}}{n^{3/2}}}\right)}عندما تكون قيمة d تساوي 2، يصبح هذا الحدΘ((3+22)نن3/2){\displaystyle \Theta \left({\frac {(3+2{\sqrt {2}})^{n}}{n^{3/2}}}\right)}.
  • كما قام كل من أسينوفسكي وباريكيت ومنصور وبينتر [ 9 ] بدراسة عدد فئات التكافؤ القطعي لتقسيمات المقصلة.

تلوين فواصل المقصلة

التلوين متعدد الألوان للرسم البياني المستوي هو تلوين رؤوسه بحيث يظهر كل لون مرة واحدة على الأقل في كل وجه من أوجه الرسم البياني. وقد سعى العديد من الباحثين إلى إيجاد أكبر قيمة لـ k بحيث يوجد دائمًا تلوين متعدد الألوان من الدرجة k . ومن الحالات الخاصة المهمة عندما يمثل الرسم البياني تقسيمًا لمستطيل إلى مستطيلات.

  • أثبت دينيتز وكاتز وكراكوفسكي [ 10 ] أنه يوجد دائمًا تلوين متعدد الألوان بثلاثة ألوان.
  • أثبت Aigner-Horev و Katz و Krakovski و Loffler [ 11 ] أنه في الحالة الفرعية الخاصة التي يمثل فيها الرسم البياني تقسيم المقصلة ، يوجد دائمًا تلوين قوي متعدد الألوان بأربعة ألوان.
  • قام كيزيغ [ 12 ] بتوسيع هذه النتيجة لتشمل أقسام المقصلة ذات الأبعاد d ، وقدم خوارزمية تلوين فعالة.
  • أثبت ديميتروف، أيجنر-هوريف وكراكوفسكي [ 13 ] أخيرًا أنه يوجد دائمًا تلوين قوي متعدد الألوان بأربعة ألوان.

انظر أيضاً

مراجع

  1. ^ Lengauer، Thomas (1990)، “Circuit Partitioning” ، الخوارزميات التوافقية لتخطيط الدوائر المتكاملة ، فيسبادن: Vieweg+Teubner Verlag، الصفحات من 251 إلى 301، دوى : 10.1007 / 978-3-322-92106-2_6 ، ISBN  978-3-322-92108-6تم الاطلاع عليه بتاريخ 16 يناير 2021
  2. 1 2 دو، دينغ-تشو؛ كو، كير-آي؛ هو، شياودونغ (2012). تصميم وتحليل خوارزميات التقريب . سبرينغر: التحسين وتطبيقاته. نيويورك: سبرينغر-فيرلاغ. الصفحات 165-209 ، الفصل 5 "القطع بالمقصلة". ISBN  978-1-4614-1700-2.
  3. ↑ غونزاليس، تيوفيلو؛ تشنغ، سي-تشينغ (1989-06-01). "حدود محسّنة للتقسيمات المستطيلة والمقصلة" . مجلة الحساب الرمزي . 7 (6): 591-610 . doi : 10.1016/S0747-7171(89)80042-2 . ISSN 0747-7171 . 
  4. ↑ غونزاليس، تيوفيلو ف.؛ رزازي، محمد رضا؛ شينغ، مان تاك؛ تشنغ، سي تشينغ (1994-05-01). "حول التقسيمات المثلى للمقصلة التي تقارب التقسيمات المثلى لصندوق d" . الهندسة الحسابية . 4 (1): 1-11 . doi : 10.1016/0925-7721(94)90013-2 . ISSN 0925-7721 . 
  5. ↑ أرورا، س. (أكتوبر 1996). "مخططات تقريبية متعددة الحدود لمسألة البائع المتجول الإقليدية وغيرها من المسائل الهندسية". وقائع المؤتمر السابع والثلاثين حول أسس علوم الحاسوب . ص 2-11 . doi : 10.1109/SFCS.1996.548458 . ISBN  0-8186-7594-2. S2CID 1499391 . 
  6. ↑ ميتشل، جوزيف إس بي (1999-01-01). "تقسيمات المقصلة تقارب التقسيمات المضلعية: مخطط تقريبي بسيط ذو زمن متعدد الحدود لمسائل البائع المتجول الهندسية، ومسألة الشجرة الممتدة الدنيا k، والمسائل ذات الصلة" . مجلة SIAM للحوسبة . 28 (4): 1298-1309 . doi : 10.1137/S0097539796309764 . ISSN 0097-5397 . 
  7. ↑ ياو، بو؛ تشين، هونغيو؛ تشنغ، تشونغ كوان؛ غراهام، رونالد (1 يناير 2003). "تمثيلات المخططات الأرضية: التعقيد والروابط" . معاملات ACM في أتمتة تصميم الأنظمة الإلكترونية . 8 (1): 55-80 . doi : 10.1145/606603.606607 . ISSN 1084-4309 . S2CID 1645358 .  
  8. ↑ أكرمان، إيال؛ باريكيت، جيل؛ بينتر، رون ي.؛ روميك، دان (31 مايو 2006). "عدد أقسام المقصلة في الأبعاد d" . رسائل معالجة المعلومات . 98 (4): 162-167 . doi : 10.1016/j.ipl.2006.01.011 . ISSN 0020-0190 . 
  9. ↑ أسينوفسكي، أندريه؛ باريكيت، جيل؛ منصور، توفيق؛ بينتر، رون ي. (28-09-2014). "تكافؤ القطع لتقسيمات المقصلة ذات الأبعاد d" . الرياضيات المتقطعة . 331 : 165-174 . doi : 10.1016/j.disc.2014.05.014 . ISSN 0012-365X . 
  10. ↑ دينيتز، يفيم؛ كاتز، ماثيو جيه؛ كراكوفسكي، روي (1 ديسمبر 2009). "حماية التقسيمات المستطيلة" . المجلة الدولية للهندسة الحسابية وتطبيقاتها . 19 (6): 579-594 . doi : 10.1142/S0218195909003131 . ISSN 0218-1959 . 
  11. ↑ هوريف، إيلاد؛ كاتز، ماثيو جيه؛ كراكوفسكي، روي؛ لوفلر، مارتن (15 يونيو 2009). "تلوين متعدد الألوان لتقسيمات المقصلة بأربعة ألوان" . رسائل معالجة المعلومات . 109 (13): 690-694 . doi : 10.1016/j.ipl.2009.03.006 . ISSN 0020-0190 . 
  12. ↑ كيسيز، بالاز (2008). "تلوين متعدد الألوان لأقسام المقصلة ذات الأبعاد n" . في: هو، شياودونغ؛ وانغ، جي (محرران). الحوسبة والتوافقية . سلسلة محاضرات في علوم الحاسوب. المجلد 5092. برلين، هايدلبرغ: سبرينغر. الصفحات 110-118 . doi : 10.1007/978-3-540-69733-6_12 . ISBN   978-3-540-69733-6.
  13. ↑ ديميتروف، داركو؛ هوريف، إيلاد؛ كراكوفسكي، روي (2009-05-06). "تلوين متعدد الألوان للتقسيمات المستطيلة" . الرياضيات المتقطعة . 309 (9): 2957-2960 . doi : 10.1016/j.disc.2008.07.035 . ISSN 0012-365X .