ما هي الخوارزمية لتقليل الانحراف المعياري لمجموعات m المجمعة من مجموعات n؟[مع محاولة]

Question

لدي صناديق م (مبالغ) ومجموع ن.كل أمر يذهب إلى سلة المهملات.من أجل تقليل الانحراف المعياري، لدي خوارزمية جشعة يبدو أنها تحقق ذلك.لست متأكدا من الاسم، ولكن أود أن أعرف المزيد.يجب أن يكون مجموع جميع الصناديق m أكبر من الصفر في نهاية الخوارزمية.

يبدو الأمر بسيطًا:

فرز الجمع من الأعلى إلى الأدنى.

لكل جمع في الجمع:ابحث عن أول سلة متاحة مع الحد الأدنى من المبلغ وضعها في السلة

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

تحرير --- هذه هي محاولتي للتحليل:

تسعى الخوارزمية إلى تقليل الانحراف المعياري لمجموعات m التي تم جمعها من مجموعات n.

المتوسط ​​هو دائما مجموع n مقسوما على m، وهذا معطى.

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

لنفترض أن هناك bin m1، وليس الحد الأدنى لمجموع bin، فهذا خيار أفضل من الحد الأدنى لمجموع bin m.ستؤدي الإضافة إلى هذا الصندوق إلى تقليل الانحراف المعياري من حولك.

بمعنى آخر، وضع القيمة التالية n في m سيؤدي إلى تقليل التباين إلى الحد الأقصى، مما يعني أننا قمنا بتقليل مجموع (m_i - u)^2 إلى الحد الأقصى.ملحوظة:m1' = m1 + x، m' = m + x، حيث x هو الجمع التالي.

لذا:Result_sum_var + (m1' - u)^2 + (m - u)^2 < Result_sum_var + (m' - u)^2 + (m1 - u^2) حيث m1 أكبر من m.

التبسيط والتحليل:

(م1' - ش)^2 + (م - ش)^2 < (م' - ش)^2 + (م1 - ش^2)

m1'^2 - 2um1' + 2u^2 + m^2 - 2um < m'^2 - 2um' + 2u^2 + m1^2 - 2um1

m1'^2 - 2um1' + m^2 - 2um < m'^2 - 2um' + m1^2 - 2um1

تجاهل المصطلحات الخطية التي سيكون اختلافها ثابتًا (الخطية).

م1'^2 + م^2 < م'^2 + م1^2

إذا أضفنا مجموع x إلى m1 فإن هذا يتسع إلى:

(م1 + س)^2 + م^2 < (م + س)^2 + م1^2

m1^2 + 2m1x + x^2 + m^2 < m^2 + 2mx + x^2 + m1^2

2 م 1 × < 2 م ×

m1 < m، هذا تناقض.لذلك لا يمكن أن يكون هناك خيار أفضل من الحد الأدنى لمجموع بن م.

Answer 1

لا، لا تنتج الخوارزمية دائمًا الحل الأمثل.متى $م=2$, ، هذا (على الأقل بنفس صعوبة) الأمر مشكلة التقسيم, ، وهو NP-صعب.تناقش ويكيبيديا الخوارزمية الجشعة ويسرد مثالًا مضادًا يوضح أن الخوارزمية الخاصة بك لا تعمل.

Answer 2

لقد اكتشفت أن الخوارزمية هي خوارزمية LPT.يتم تناوله هنا جنبًا إلى جنب مع خوارزميات أخرى لمهمة نموذجية:الجدولة على الأجهزة المتوازية ذات الوظائف الثابتة.المشكلة هي NP الثابت وNP كاملة.خوارزميات الوقت متعددة الحدود هي تقريبية.

https://depositonce.tu-berlin.de/bitstream/11303/11089/3/grigoriu_liliana_2019.pdf