הצגת המקור של הדף "בעיית אריזה בדליים"

ב[[מדעי המחשב]], '''בעיית אריזה בדליים''' (bin packing) היא בעיית [[אופטימיזציה (מתמטיקה)|אופטימיזציה]] חשובה, בה יש לארוז חפצים במספר מינימלי של דליים. הבעיה היא [[NP-קשיות|NP-קשה]].

==הגדרה==
נתונים <math>n</math> חפצים, לכל אחד מהם נפח: <math>a_1,...,a_n</math>. בנוסף נתונים מספר לא מוגבל של דליים, שכל אחד מהם בנפח <math>C</math> ומתקיים <math>C \ge a_i</math> לכל i (אחרת אי אפשר לארוז אותם בשום דרך). יש לארוז את החפצים במספר מינימלי של דליים, כך שבכל דלי הנפח הכולל של החפצים לא יעלה על נפח הדלי. באופן פורמלי, יש לחלק את המספרים <math>a_1,...,a_n</math> למספר מינימלי של קבוצות זרות, שסכום כל קבוצה לא יעלה על <math>C</math>.

== סיבוכיות ==
הבעיה היא NP-קשה, והצגתה כ[[בעיית הכרעה]]: "האם ניתן לארוז בפחות מ-k דליים?" היא NP-שלמה. הבעיה היא גם NP קשה חזקה, כלומר גם קבלת הקלט בכתיב אונארי היא NP קשה (בניגוד ל[[בעיית תרמיל הגב]] למשל).

יתרה מכך, בהנחה ש-P שונה מ-NP, אין גם [[אלגוריתם קירוב]] ביחס יותר טוב מ 1.5. ניתן לראות זאת על ידי רדוקציה מ[[בעיית החלוקה]]: בהינתן וקטור <math>a_1,...,a_n</math>, נקח <math>C=\frac{\sum a_i}{2}</math> ואז בעיית האריזה בדליים תתן פתרון עם שני דליים [[אם ורק אם]] בעיית החלוקה פתירה, אחרת 3 דליים ומעלה.{{הערה|https://cs.ubishops.ca/home/cs567/more-np-complete/rangasamy-bin-packing.pdf}}

==אלגוריתמים==
===תכנון ליניארי בשלמים===
ניתן לפתור את הבעיה באמצעות [[תכנון ליניארי]] בשלמים.{{הערה|http://www.or.deis.unibo.it/kp/Chapter8.pdf}} המשתנים הם <math>x_{ij}</math> שמציין "הפריט ה-i נכנס לדלי ה-j" וכן <math>y_j</math> שמציין "הדלי ה-j נמצא בשימוש" (צריך רק n משתנים כאלה, כי תמיד אפשר לפתור ב-n דליים - להכניס כל פריט לדלי אחר).

כעת המשוואות הן:
:<math>\sum x_{ij}a_i \le y_j C</math>
לכל j, וכן
:<math>\sum_j x_{ij} = 1</math>
לכל i (הפריט נכנס לבדיוק דלי 1) ובנוסף אילוצים שכופים על כל המשתנים להיות בינאריים.
פונקציית המטרה היא למזער את <math>\sum_j y_j</math>.

===אלגוריתם חמדן===
[[אלגוריתם חמדן]] לבעיה יהיה: לעבור על הפריטים אחד אחד, ובכל פעם לנסות להכניס אותו לאחד הדליים הקיימים. אם לא מצליחים, לפתוח דלי חדש ולשים רק אותו. מימוש האלגוריתם מושפע מהסדר בו עוברים על הפריטים, ומהסדר בו עוברים על הדליים כשמנסים למצוא דלי פנוי.

== הערות שוליים ==
{{הערות שוליים}}

[[קטגוריה:בעיות NP-קשות]]
[[קטגוריה:בעיות NP-שלמות]]