كيفية العثور على الحد الأدنى من القيمة الفرعية
https://stackoverflow.com/questions/1268826
-
13-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
تخيل أن لديك قماش وفي هذا القماش هناك بالفعل بعض الكائنات. كيف يمكنك العثور على الحد الأدنى من الطريقة لتغطية المنطقة "المكشوفة" مع المربعات، وليس تراكب بعضها البعض، ملء تماما قماش.
في حالتي "قماش" عبارة عن حاوية HTML-Div والكائنات متداخلة حاويات DIV. يمكن أن تبدو مثل هذا: http://www.Encodechain.com/demo/200908_optimize.png.على اليسار، هناك "البداية" وعلى اليمين هناك "خطوة" أولا ممكنة
أعلم أن هناك خوارزمية لهذا الغرض، ولكن حاليا لا أستطيع تذكر الاسم.
المحلول
أفضل ما يمكن أن أجده هو هذه الورقة: تبليط مستطيل بأقل مربعاتوبعد الورقة هي قراءة مثيرة للاهتمام، على الرغم من أنها تقع في بعض الأحيان في عمق إقليم النظرية مع الحديث عن "الثوابت العالمية". أنا لست متأكدا مما إذا كانت مسألة "يمكن لمستطيل حجم M By N by N Bilears with K Squarares" هو NP-Complete. كما لوحظ في استجابة أخرى، فإن سؤالك يشبه مشاكل التعبئة التي تكتمل NP. وبالطبع، فإن مشكلتك هي تعميم واحد موجه في هذه الورقة، لأنك تتعامل مع المناطق غير المستطيلة. يمكنك البدء عن طريق كسر منصولك إلى الحد الأدنى لعدد المستطيلات، مشكلة أخرى مثيرة للاهتمام في حد ذاتها. وأخيرا، حتى لو كان بإمكانك القيام بذلك بكفاءة، لست متأكدا مما إذا كانت تبليط تلك المستطيلات على النحو الأمثل ستؤدي إلى تبليط مثالي.
كما يلاحظ المؤلف، فإن الخوارزمية الجشعة هي مكان جيد للبدء: فقط اخماد أكبر مربع يمكنك حتى تكون المنطقة ممتلئة.
نصائح أخرى
