בעיית תרמיל הגב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
←אלגוריתמי קירוב: ההוכחה שכתב משתמש:זה ינחמנו הייתה נכונה (למעט אי-דיוק קטן ולא משמעותי). ניסחתי בצורה יותר מפורטת, אולי מפורטת מדי... |
|||
שורה 62:
=== אלגוריתמי קירוב ===
[[אלגוריתם חמדן|האלגוריתם החמדן]] הבא מוצא תרמיל שמחירו לכל הפחות מחצית המחיר של הפתרון המיטבי (2-קירוב){{הערה|Alexander Souza, [https://pdfs.semanticscholar.org/1788/27014a29983305b13f49b6a516fb791a9acf.pdf Combinatorial Algorithms - Lecture Notes , Winter Term 10/11], 2011}}:
נמיין את העצמים (שמשקלם אינו גדול מהחסם; עצם שמשקלו גדול מהחסם <math>W</math> אינו רלוונטי לבעיה) לפי יחס המחיר-משקל שלהם <math>p_i/w_i</math>. נוסיף לתרמיל, כל עוד זה אפשרי, את העצם הבא ברשימה הממוינת לפי יחס מחיר-משקל (מתחילים עם העצם בעל היחס הגבוה ביותר). נסמן ב-<math>j</math> את מספר העצמים שהצלחנו להכניס בצורה זו, ולכן ניתן לתאר את המחיר של העצמים שהכנסנו על ידי: <math>\sum_{i=1}^j p_i</math>. כעת נתבונן על המחיר של העצם ה-<math>j+1</math>: {{כ}}<math>p_{j+1}</math>. אם <math>\sum_{i=1}^j p_i > p_{j+1}</math>, נשאיר את <math>j</math> העצמים בתיק, ואם <math>\sum_{i=1}^j p_i < p_{j+1}</math>, נוציא את <math>j</math> העצמים מהתיק, ונכניס במקומם את העצם ה-<math>j+1</math>.
'''הוכחה שאלגוריתם זה נותן פתרון 2-קירוב:''' נסמן ב-<math>m</math> את הערך של הפתרון האופטימלי. נתבונן בבעיה דומה בה מותר לנו להכניס חלקי עצמים (נניח חצי עצם), ולא רק עצמים שלמים, ונסמן ב-<math>M</math> את הערך של הפתרון האופטימלי עבור בעיה זו. הפתרון האופטימלי עבור בעיה בה מותר להכניס חלקי עצמים, הוא גדול-שווה לפתרון האופטימלי של הבעיה המקורית בה ניתן להכניס רק עצמים שלמים (שכן כל פתרון עבור הבעיה המקורית, הוא גם פתרון אפשרי של הבעיה עם חלקי עצמים).
אם יכולנו להכניס לתרמיל חלקי עצמים, אזי ברור שהפתרון האופטימלי היה להכניס את j העצמים הראשונים, ולהכניס חלק מהעצם ה-j+1 שבדיוק ממלא את המשקל שניתן עוד להכניס לתרמיל (המשקל שניתן עוד להכניס לתרמיל לאחר הכנסת j העצמים הראשונים הוא <math>W - \sum_{i=1}^j w_i</math>, ולכן החלק של העצם ה-j+1 שיוכנס לתרמיל הוא <math>x_{j+1} = \frac{W - \sum_{i=1}^j w_i}{w_{j+1}} < 1</math>). לכן:
:<math>\sum_{i=1}^{j+1} p_i = \sum_{i=1}^{j} p_i + p_{j+1} \geq \sum_{i=1}^{j} p_i + x_{j+1} p_{j+1} = M \geq m </math>, {{רווח קשיח|3}} ולענייננו מה שחשוב זה ש: {{רווח קשיח|1}} <math>\sum_{i=1}^{j+1} p_i \geq m </math>
ובמילים: המחיר של העצמים 1 עד j+1 גדול מהמחיר של עצמים 1 עד j + המחיר של חלק מעצם j+1, ששווה ל-M (הפתרון של הבעיה עם חלקי עצמים), שגדול-שווה ל-m (הפתרון של הבעיה שלנו).
לכן, אם נחלק את הסכום <math>\sum_{i=1}^{j+1} p_i</math> ל-<math>\sum_{i=1}^{j} p_i</math> ול-<math>p_{j+1}</math>, בהכרח לפחות אחד משני הביטויים הללו חייב להיות בעל מחיר של לפחות <math>\frac{m}{2}</math>, כיוון שסכום המשקלים של שניהם חייב להיות גדול-שווה ל-<math>m</math>.
== קישורים חיצוניים ==
| |||