مشكلة التراص مربع

Question

لقد وجدت مشكلة موانئ دبي الشهيرة في العديد من الأماكن ، لكن لا يمكنني معرفة كيفية حلها.

يتم إعطاؤك مجموعة من أنواع n من الصناديق ثلاثية الأبعاد المستطيلة ، حيث يحتوي المربع I^th على ارتفاع H (i) ، العرض W (i) وعمق D (i) (جميع الأرقام الحقيقية). تريد إنشاء كومة من الصناديق التي يبلغ طولها قدر الإمكان ، ولكن يمكنك فقط تكديس مربع أعلى مربع آخر إذا كانت أبعاد قاعدة 2-D من الصندوق السفلي أكبر من تلك الموجودة في 2- 2- د قاعدة من الصندوق الأعلى. بالطبع ، يمكنك تدوير مربع بحيث يعمل أي جانبي كقاعدته. يُسمح أيضًا باستخدام مثيلات متعددة من نفس النوع من الصندوق.

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

Answer 1

أعتقد أنه يمكنك حل هذا باستخدام البرمجة الديناميكية أطول زيادة بعد الخوارزمية: http://www.algorithmist.com/index.php/longest_incring_subequence

إن حساب الدورات أمر سهل بما فيه الكفاية: لكل برج كل ما عليك التحقق منه هو ما يحدث إذا كنت تستخدم ارتفاعه كطول القاعدة وعرضه كحل وماذا يحدث إذا كنت تستخدمه بالطريقة الطبيعية. علي سبيل المثال:

=============
=           =
=           =
=           = L
=     H     =
=           =
=           =
=============   
      W

يصبح شيئًا مثل (نعم ، أعلم أنه لا يبدو شيئًا كما ينبغي ، فقط اتبع الترميزات):

==================
=                =
=                =  
=       W        = L
=                =
=                =
==================
        H

لذلك لكل كتلة لديك بالفعل 3 كتل تمثل دوراتها المحتملة. اضبط مجموعة الكتل الخاصة بك وفقًا لهذا ، ثم فرز عن طريق تقليل مساحة القاعدة وتطبيق خوارزمية DP LIS فقط على الحصول على الحد الأقصى للارتفاع.

تكرار التكيف هو: D [i] = أقصى ارتفاع يمكننا الحصول عليه إذا كان البرج الأخير يجب أن يكون i.

D[1] = h(1);
D[i] = h(i) + max(D[j] | j < i, we can put block i on top of block j)

Answer is the max element of D.

شاهد مقطع فيديو يشرح هذا هنا: http://people.csail.mit.edu/bdean/6.046/dp/

Answer 2

يمكن اعتبار المكدس سلسلة من التوائم X و Y و z (x ، y كونها المستوى ثنائي الأبعاد ، و z الارتفاع) ، حيث x (i)> x (i+1) و y (i)> y ( أنا+1). الهدف من ذلك هو زيادة مجموع Z لالتقاط التوائم من مجموعة الثلاثيات المتاحة - كل ثلاثة أضعاف نوع واحد من الصندوق في اتجاه معين. من السهل جدًا أن نرى أن تطبيق القيد x> y لا يقلل من مساحة الحل. لذلك يولد كل مربع 3 توائم ، مع كل من W ، H ، D كإحداثي Z.

إذا كنت تعتبر التوائم كرسوم بيانية حميدة موجهة حيث توجد حواف ذات طول z بين ثلاثة توائم عندما تكون القيود X ، Y راضية بينهما ، فإن المشكلة هي العثور على أطول مسار من خلال هذا الرسم البياني.

Answer 3

لنحاول أولاً حل هذه المشكلة في 2-D:

لنفترض أن لديك مستطيلات مع X's و Y's ، والسؤال متشابه (أعلى برج ، ولكن هذه المرة يجب أن تقلق فقط بشأن بُعد أساسي واحد).
أولاً ، تتجاوز المجموعة بأكملها ، وتكرار كل مستطيل عن طريق تدويرها 90 درجة (تبديل x و y) ، باستثناء المربعات (حيث x (1) = x (2) && y (1) = y (2)) . هذا يمثل جميع الاختلافات الممكنة.
ثم تقوم بفرزها بجانب X ، من الأكبر إلى الأصغر. في حالة التكرار x ، يمكنك إزالة القيمة ذات القيمة y المنخفضة.

نفس المبدأ المطبق في السيناريو ثلاثي الأبعاد ، الآن فقط لا تضاعف حجم المجموعة بمقدار 6 (كل متغيرات محتملة من W ، H ، D) ولكن بدلاً من ذلك. يمكنك القيام بذلك عن طريق رفض جميع الاختلافات حيث يكون العرض أقل من العمق (لذلك لكل i ، w (i)> = d (i)) ، ثم رفض الاختلاف حيث لا يكون الارتفاع هو الأعلى ولا أدنى الأبعاد الثلاثة (لأن الاختلافين الآخرين يمكن أن يذهبا أعلى الآخر وهذا واحد لا يمكن الانضمام). مرة أخرى ، يمكنك أيضًا رفض التكرار (حيث W (1) = W (2) && h (1) = H (2) && d (1) = d (2)).
بعد ذلك ، يجب أن تكون فرزًا حسب العرض ، فقط هذه المرة التي لا تتخلص فيها من الاختلافات بنفس العرض (لأن أحدهم قد يتناسب مع برج قد لا يكون له) ثم يمكنك استخدام خوارزمية LIS كما هو موضح أعلاه بواسطة ivlad:

D[1] = h(1);
D[i] = h(i) + max(D[j] | j <= i and we can put tower i on tower j) or simply h(i) if no such D[j] exists.

كانت الحيلة هي ، كما تعلمون أن العرض هو الأطول بين الاثنين ، حتى تعرف أن العنصر الأول لن يتناسب مع أي عنصر لاحق.

Answer 4

أقترح عليك إنشاء شجرة (أو نوع من بنية الأشجار) وتحليلها بالبحث في العمق ، وحساب الارتفاع القصوى من قيم "الارتفاع" الرأسي الفردي (Depening on Detation).

هذا (أعتقد أن هذا هو النهج الأساسي).

التفاصيل على التفاصيل:

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

عندما يتم بناء الشجرة ، اذهب من خلال أرضية إلى ورقة من الشجرة.

Answer 5

يتكون حل للمشكلة من ثلاث خطوات.

1. فرز الأبعاد لكل مربع بحيث تقل مقارنة أي مربعين بمقارنة أبعادها المقابلة.
2. فرز تسلسل الصناديق معجوغرافيا بحيث يكون لكل مربع لكل صندوق ، الصناديق إلى اليسار هي الصناديق التي قد تتناسب.
3. يتقدم ال O(n^2) خوارزمية لأطول مشكلة بعد زيادة.

الخطوة الثالثة هي أغلى وتصطيف بتعقيد الحل O(n^2). إذا كنت ترغب في قراءة شرح كامل للنهج ، فكيف تساهم كل خطوة في العثور على إجابة ، ورمز كامل ، إلقاء نظرة على منشور المدونة الذي كتبته عن المشكلة.