خوارزمية فقس المستطيل الأمثل

Question

أنا أبحث عن خوارزمية لتظليل مستطيل بأقصر طول إجمالي للخط، بحيث يمكن تمرير كائن بمساحة معينة من خلال التظليل.

على سبيل المثال، في حالة وجود مستطيل مقاس 5 × 3 سم، وقمت بفتحه باستخدام خطوط متوازية بعرض 1 سم، فإن أكبر جسم يمكنني تمريره عبر الفتحة هو مربع طول ضلعه 1 سم.لقد استخدمت إجمالي 22 سم (أي 4x3+2x5) من خطوط الفتحة.لذلك، لتمرير مساحة 1 سم مربع، استخدمت 22 سم من خطوط التظليل.

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

يحرر: باتباع خطى nlucaroni وجدت تخمين قرص العسل والتي تنص على أن أي تقسيم للمستوى إلى مناطق متساوية المساحة له محيط على الأقل محيط الشبكة السداسية العادية، وهو ما يجيب على سؤالي جزئيًا.

Answer 1

أنت بحاجة إلى الأشكال التي تشكل أ التغطية بالفسيفساء.ربما يكون السداسي هو أفضل رهان لك.ومع ذلك، ماذا لو كان الشكل الذي تمر به لا يتناسب تمامًا مع نمط التغطية بالفسيفساء؟

انظر إلى الفسيفساء واكتشف ما إذا كان النمط/الشاشة/الفتحة الخاصة بك يجب أن تكون منتظمة أم لا، ويجب أن تناسب الكائن الذي يتم اختباره، وما إلى ذلك.

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

سؤالك غامض/غير مكتمل جدًا، هذا كل ما لدي لك.

Answer 2

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

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

يحرر:عندما جربت الخوارزمية المقترحة بالفعل، حصلت على نتائج أسوأ من النسخة الساذجة.أنت بالتأكيد بحاجة إلى مراعاة الحد الأدنى للحجم عند وضع الأسلاك.

Answer 3

ماذا يعني تفقيس المستطيل؟

هل يمكنك إعادة صياغة سؤالك؟

أيضًا، أثناء إعادة الصياغة، اذكر ما يجب أن تتلقاه الخوارزمية كمدخل وما يجب أن تنتجه كمخرجات.