שיחה:בעיית תרמיל הגב

ערך זה נכתב או הורחב משמעותית בקורס "ויקיפדיה בפקולטה למדעי המחשב" במסגרת מיזם עבודות ויקידמיות בטכניון - הפקולטה למדעי המחשב

הערות על הערך

הערך נחמד וחשוב. שתי הערות קטנות:

• "כיוון שהבעיה היא NP-שלמה, לא קיימים אלגוריתמים פולינומיים אשר מוצאים פתרון מיטבי." - צ"ל לא ידועים, ייתכן שיום אחד יימצא אלג' פולינומיאלי לבעיה.
• wi אינו מוגדר. האם הוא אינו צריך להיות מוחלף ב-vi לאורך הערך?
• חסר לי הסבר קצר של נכונות האלג' החמדן בסוף הערך.
• אגב, למה לא להביא את פתרון בעיית תרמיל הגב הרגילה, ולא את תרמיל הגב הבינארית? ההבדל אינו גדול, והפתרון כך כללי יותר.

חג שמח, ‏אופקאלף • שיחה • הצטרפו למיזם המקורי!‏ 11:18, 17 באפריל 2014 (IDT)

קודם כל תודה על ההערות.

• לגבי העניין שלא קיימים אלגוריתמים - תיקנתי את זה, אפילו לא שמתי לב שכתבתי את זה.
• לגבי vi, אני התבלבלתי קצת והשתמשתי בשני סימונים. אני מעדיף את הסימון wi עבור משקל ולכן שיניתי את כל מופעי vi למופעי wi.
• נכונות האלגוריתם החמדן - יש הוכחה לא מורכבת מדי ליחס הקירוב שלו אבל אני תוהה אם זה לא קצת כבד לתת אותה בערך הזה. כרגע אני חושב שהערך פונה לקהל יעד בלי מעורב מבחינת ידע מתמטי ואני חושב שלהוסיף הוכחת יחס קירוב קצת תפגע בנגישות עבור אנשים שפחות מבינים. אם אתה בכל זאת חושב שיש לזה מקום, אני יכול להוסיף את זה.
• כיוון שהיה חשוב לי לצרף גם קוד לפתרון הבעיה, הלכתי על בעיית תרמיל הגב הבינארית גם בגלל הפשטות וגם בגלל שהיה לי מקור לקוד. אם פתרון לבעיית תרמיל הגב הרגילה הוא טוב יותר, אני יכול להחליף.

האם יש הערות טכניות לגבי הערך ? כלומר מעבר להערות על התוכן - עריכה, כללי ויקיפדיה וכו'

שוב תודה!

--Eidanch - שיחה 17:26, 23 באפריל 2014 (IDT)

לא מצאתי בעיות טכניות. השתמשת יפה בנוסחאות המתמטיות ובקישורים פנימיים.

אני לא מכיר את ההוכחה לאלג' הזה (ראיתי שבדף שקישרת אליו היא לא ארוכה, אבל לא עקבתי אחריה). אם מדובר בהוכחה ארוכה ומסורבלת, אז יש לשקול האם להוסיף את ההוכחה לערך. אחרת, לעניות דעתי, יש להוסיף אותה לערך (תוך ניסיון שתהא ברורה גם עבור אלו שאינם בקיאים). אני לא חושב שיש צורך שכל קטע וקטע בוויקיפדיה יהיה נהיר עבור כל קורא, גם אם כדאי להשתדל שכן.

לגבי הבעיה הבינארית, זה לא נראה לי ממש עקרוני, פשוט עלתה לי התהיה מדוע הפתרון הוא דווקא לבעיה הבינארית, ועכשיו הבנתי מדוע.

לדעתי במצב אידאלי, תסופק בערך גם ההוכחה לכך שהבעיה הינה NP שלמה (אני, אגב, לא מכיר גם את ההוכחה הזו). עם זאת, אני מניח שההוכחה היא רדוקציה מבעיה אחרת, ולא מצאתי הוכחה ל-NP-שלמות של הבעיות הבסיסיות, כך שהוכחה כזו תיצור "חור", ועדיף כבר לא להביאה. ‏אופקאלף • שיחה • הצטרפו למיזם המקורי!‏ 18:32, 23 באפריל 2014 (IDT)

אני מנסה לראות עד כמה אפשר להכניס תכנים יותר תאורטיים כמו הוכחת הקושי (ואולי גם הוכחת הקירוב). ניסיתי לחפש ומצאתי מקור שמציין רדוקציה לבעיית החלוקה, ניסיתי לתמצת כאן גרסה של ההוכחה. זה מרגיש קצת חסר ואני לא שלם עם זה במאה אחוז אבל אני גם לא רוצה לתת לחלק הזה של המאמר יותר משקל ממה שהוא צריך לקבל מה אתה חושב ? אם זה סביר אני מתאר לעצמי שאפשר להראות גם את הוכחת הקירוב של האלגוריתם החמדן, אם כי כדי באמת לתת את ההוכחה הזו צריך לדבר על חסמים תחתונים לאופטימום, ובהוכחה הקנונית גם עוברים דרך בעיית תרמיל הגב השברית שלא הזכרנו בערך (אפשר לעקוף את זה, אבל, שוב, מדובר בעוד פרטי הוכחה). מה דעתך ?

--Eidanch - שיחה 20:09, 23 באפריל 2014 (IDT)

מצטער שלא הגבתי. אגיב יותר מאוחר היום. ‏אופקאלף • שיחה • הצטרפו למיזם המקורי!‏ 14:06, 29 באפריל 2014 (IDT)

אז ככה:

1. הרדוקציה היא מבעיית החלוקה ולא אליה.
2. לא ברור מי זה P ברדוקציה.
3. אולי כדאי לכתוב בסוגריים שבבעיית החלוקה קובעים האם ניתן לחלק מולטי קבוצה של מספרים לשתי תת קבוצות שסכומן זהה?
4. אם כך הייתי מוותר על הוכחת הקירוב, בינתיים מספיק הקישור להוכחה בהערת השוליים.
5. אגב, ראה ויקיפדיה:ביבליוגרפיה#כללי כתיבת מקורות ביבליוגרפיים בוויקיפדיה, צריך לסדר אותן בערך. ‏אופקאלף • שיחה • הצטרפו למיזם המקורי!‏ 19:25, 29 באפריל 2014 (IDT)

ראשית טיפלתי בארגון של הקישורים, עכשיו זה נראה הרבה יותר טוב מאשר רשימת PDF-ים. לגבי בעיית החלוקה הוספתי הערת שוליים שמתארת את הבעייה. אני ממש לא בטוח מה התכוונת לגבי P - זה מוגדר ברדוקציה ואני לא בטוח מה לא ברור פה. באופן כללי אני לא שלם עם הוכחת הקושי והאופן שבה היא מוצגת, אולי זה בכל זאת לא צריך להיכנס כאן (אבל אם זה נראה לך בסדר, אני איתך). האם יש לך הערות נוספות על הערך ? האם אתה חושב שהוא מוכן לעלות למרחב הציבורי ? האם תוכל להגיד לי מה אני מריך לעשות כדי להעלות אותו למרחב הציבורי ?

תודה!

--Eidanch - שיחה 11:43, 2 במאי 2014 (IDT)

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

חוץ מזה לדעתי הערך מוכן למרחב הערכים. בראש הדף יש לך לשונית כזו, אתה מצביע עליה ולוחץ על "העברה", במקום "משתמש" אתה מעביר את זה למרחב הראשי, ומוריד את השם שלך. בהצלחה. ‏אופקאלף • שיחה • הצטרפו למיזם המקורי!‏ 11:51, 2 במאי 2014 (IDT)

מה זה פיזיבלי? ‏אופקאלף • שיחה • הצטרפו למיזם המקורי!‏ 14:30, 2 במאי 2014 (IDT)

Feasible. אפשרי (תחת המגבלות הנתונות). נויקלן 16:51, 2 במאי 2014 (IDT)

אז למה לא בעברית? :-) ‏אופקאלף • שיחה • הצטרפו למיזם המקורי!‏ 17:42, 2 במאי 2014 (IDT)

נדמה לי שזה מונח מקובל במדעים מדויקים לתיאור פתרון שעומד במגבלות שהוצבו, אבל אני אשאיר את המענה הסופי לעידן/אנשים מהדיסציפלינה. ראה גם w:Feasible region. נויקלן 17:49, 2 במאי 2014 (IDT)

לא נתקלתי בו בהקשר של מדעי המחשב (באוניברסיטה). נראה מה עידן יגיד, תודה. ‏אופקאלף • שיחה • הצטרפו למיזם המקורי!‏ 17:51, 2 במאי 2014 (IDT)

המונח פיזיבילי הוא מונח מתחום האופטימיזציה שבא לתאר כל פתרון של הבעייה שעומר באילוצים (קח לדוגמה תכנון לינארי - פתרון פיזיבילי הוא פתרון שוקטור שמקיים את כל האילוצים הלינאריים). באנגלית זה מונח מקובל ולצערי אין לי מינוח עברי מקובל (ובדקתי באפליקציה של האקדמיה...). אם מישהו במקרה מוצא מילה עברית או דרך טובה יותר להביע את העניין אני אשמח לשמוע. הפתרון שאני יכול להציע הוא פשוט להחליף "פיזיבילי" ב-"פתרון העומד באילוצים". דעתכם ? --Eidanch - שיחה 17:54, 3 במאי 2014 (IDT)

גוגל תרגום מציע שלל הצעות לתרגום "Feasible": מעשי, סביר, בר ביצוע, ממיש. אני יכול להוסיף את "ישׂים" (ניתן ליישום), אך מכל ההצעות מעדיף את "פיזיבילי". דוד שי - שיחה 19:22, 3 במאי 2014 (IDT)

למה לא "חוקי"? ‏אופקאלף • שיחה • הצטרפו למיזם המקורי!‏ 20:11, 3 במאי 2014 (IDT)

במשמעות הזו אני בעד "תקין" או "חוקי". בדרך כלל feasible הוא "מעשי" יותר מאשר "תקין". עוזי ו. - שיחה 23:47, 11 במאי 2014 (IDT)

מקובל עלי. שיניתי ל-"חוקי" במקום "פיזיבילי". הוספתי הערה שמבהירה ש-"חוקי" משמעותו עומד באילוצים. --Eidanch - שיחה 16:08, 13 במאי 2014 (IDT)

שתי הערות לשוניות

• החלפתי את המונח "תת-קבוצה" במונח "אוסף", משום שהמונח "תת-קבוצה" מתאים רק לבעיית תרמיל הגב הבינארי.
• הערך השתמש לסירוגין במונחים "מחיר" ו"ערך". למען האחידות שיניתי את כל המופעים ל"מחיר" (יש שיגידו ש"מחיר" ו"ערך" אינן מילים נרדפות). דוד שי - שיחה 19:22, 3 במאי 2014 (IDT)

קוד בפייתון

הקוד בפייתון מחורבש (חוץ מהזחה אחת של תוכן הפונקציה, כל ההזחות האחרות התאיידו). אנא החזר את ההזחות, ועל הדרך, החלף את הרווחים בטאבים. קיפודנחש 19:32, 16 ביוני 2014 (IDT)

לא הייתי משתמש במינוח שהשתמשת בו, אבל אתה צודק, הקוד לא היה תקין. תיקנתי. לגבי רווחים וטאבים, אני דווקא מעדיף את שיטת הרווחים ולא את הטאבים ולכן השארתי את ההזחה בפורמט של ארבעה רווחים. --Eidanch - שיחה 22:40, 16 ביוני 2014 (IDT)

איך אפשר לעשות טאב? לחיצה רגילה על טאב מעבירה אותך לתיבת ה"תקציר". ‏אופקאלף • שיחה‏ • 22:43, 16 ביוני 2014 (IDT)

@Eidanch: לא הייתה כל כוונה לפגוע במישהו - כתוצאה מתקלה כזו או אחרת הקוד התחרבש. להבא, אשמח להשתמש במינוח אחר אם תאמר לי מה המינוח המועדף עליך. @Ofekalef: הדרך הקצרה היא בעזרת "העתק/הדבק": מעתיקים תו טאב מדף בו התו כבר קיים או מיישום אחר, ומדביקים בעורך ויקי. הדרך ה"נכונה" היא בעזרת עורך הקוד, אבל למרבה הצער העורך מופעל רק בדפים ששמם מסתיים ב-js או css, ובדפים במרחב "יחידה". באופן כללי, כשמוסיפים קטע קוד לדף, עדיף לערוך את הקוד בכלים הטבעיים, ואחרי שהקוד מתהדר ורץ נכון, מדביקים בדף (ואז הטאבים מגיעים בשלמותם). בהרבה מקרים אי אפשר לעשות הכל, משום שמדובר ב-snippet, אבל תמיד אפשר לערוך בעורך קוד "אמתי" ולהדביק לדף. במקרה הזה, אפשר לבדוק את הקוד ממש, משום שמדובר בפונקציה שלמה' ומשום שפייתון לא דורש הרבה ביורוקרטיה. קיפודנחש 23:50, 16 ביוני 2014 (IDT)

הקוד היה מוצג מימין לשמאל, מה שמאוד הקשה על הקריאה שלו, הסתתי אותו להיות מוצג משמאל לימין. מקווה שאין התנגדות לעניין. שיחת משתמש:אבי גורפינקל 11:06, 11 ביולי 2015 (IDT)

הקוד הוצג בין תגי source, כך שהוא נראה נכון, ואפילו צבוע בצורה נאה. יתכן שלמשך תקופה קצרה אחד השרתים מגמגם, וכמה קבצי CSS לא הגיעו לדפדפן שלך, וזה גרם לבעיה שראית. ביטלתי את העריכה שלך, לפי ההיגיון שמקרים קשים יוצרים דין רע. הקוד צריך להיראות נכון עכשיו. קיפודנחש 11:19, 11 ביולי 2015 (IDT)

למה "בעיית תרמיל הגב" ולא פשוט "בעיית התרמיל"?

נכון שגוגל-טרנסלייט מתרגם "knapsack" ל"תרמיל גב", אבל ה"גב" לא מוסיף הרבה להבנה... --Erel Segal - שיחה 12:37, 29 במרץ 2018 (IDT)

זו לא שאלה של תוספות הבנתיות, אלא של השם המקובל. אפשר לראות שהשם "בעיית תרמיל הגב" מקובל (למשל, [1]). אם אתה יכול להראות שהשם "בעיית התרמיל" מקובל באותה מידה או יותר, אפשר לדון בהעברת הערך. קיפודנחש 19:40, 29 במרץ 2018 (IDT)

אלגוריתמי קירוב

כמה בעיות עם האלגוריתם המתואר ועם ההוכחה:

• לא מפורט לאיזו גרסה של הבעיה האלגוריתם מתייחס (בינרית, חסומה, לא חסומה)
• האלגוריתם דורש, בתנאים מסוימים, "להכניס את החפץ ה-j+1 לתרמיל", אך למעשה אין ערובה שזה אפשרי - משקלו של העצם יכול להיות גדול מהחסם
• הטענה "ויחס המחיר-משקל שלה גם כן נמוך יותר או שווה, שהרי המיון הוא לפי יחס זה" לא מוכחת, וגם לא נכונה - הנתון לא גורר את המסקנה.

זה שה"הוכחה" פגומה לא אומר שהטענה (=האלגוריתם מספק תוצאה שטיבה לכל הפחות מחצית מהמיטבית) לא נכונה, אבל עדיף לא להביא הוכחה בכלל, מאשר "הוכחה" כזו.

על הדרך אציין גם שלפי התיאור בערך, "חסומה" הוא מקרה פרטי של הבעיה הבינרית, ואעז לנחש שהתיאור שגוי. אפשר לתאר גרסה "חסומה" של הבעיה ששונה ממש מהגרסה הבינרית, במקרה בו יש עצמים עם מספר עותקים מוגבל, ועצמים אחרים עם מספר עותקים לא מוגבל. קיפודנחש 19:14, 11 באוקטובר 2018 (IDT)

חפירה קצת יותר מעמיקה מלמדת שהאלגוריתם, ובעקבותיו ה״הוכחה״ בטעות יסודו. האלגוריתם הנכון תואר בערך (בלי ״הוכחה״), ו״תוקן״ על ידי עורך שלא הבין אותו עד תומו. בכוונתי לשחזר כעת שיחזרתי לגרסה הנכונה. קיפודנחש 00:41, 12 באוקטובר 2018 (IDT)

משעשע אותי שהורדת גם את התיקון שלי לקישור השבור של המקור לאלגוריתם, כך שמי שבודק לא יכול לראות כעת את טענתך, לפחות את התיקון לקישור אחזיר. לדעתי אתה מתבלבל בין בעיית תרמיל הגב השברית שאותה האלגוריתם שלך פותר, אך כפי שהוזכר למעלה בפסקה הראשונה היא לא הוזכרה בערך. לבין בעיית התרמיל בשלמים אותה האלגוריתם שלך לא פותר. ניקח למשל תרמיל בגודל 3 וחפץ אחד במשקל אחד בשווי 1.1 וחפץ שני במשקל 3 בשווי 3, האלגוריתם שלך יבחר את החפץ הראשון ולא יהיה לו מקום לשני, מה שנותן פחות מחצי מהאופטימלי.

חוץ מזה לא הבנתי למה הורדת את האמירה שקיים אלגוריתם של סכימת קירוב מלאה, זה ממש חשוב לדעתי, גם אם כרגע אין בוויקיפדיה העברית הסבר למושג הזה, ככל הידוע לי זה סוג הקירוב הכי טוב שאפשר להשיג לבעיה NP קשה. --זה ינחמנו - שיחה 09:39, 12 באוקטובר 2018 (IDT)

רק להבהרה, המושג בעיית תרמיל הגב השברית הכוונה שאפשר לקחת שברים של חפץ ולא שהמשקל הוא בשברים --זה ינחמנו - שיחה 09:43, 12 באוקטובר 2018 (IDT)

אכן שגיתי, אבל שגיאה שונה מזו שאתה מתאר: ההבדל הוא לא בין "הבעיה השברית" לבעיה עצמה, אלא בין הבעיה הבינרית לבעיה הלא חסומה. התיאור המקורי (שאגב, אינו "האלגוריתם שלי", אלא של כותב הערך המקורי) עדיף, לדעתי, מכמה טעמים: (1) הניסוח שלו קל ופשוט בהרבה (2) קל לראות שהוא אכן מספק פתרון שערכו אכן לפחות מחצית מהפתרון המיטבי, לעומת הפתרון הנוכחי בו קשה לראות זאת (3) הוא באמת "אלגוריתם חמדן" לעומת האלגוריתם שמופיע כעת בערך, שאינו כזה, למרות שהוא מכריז על עצמו ככזה.

כאמור, האלגוריתם המקורי והנוכחי פותרים למעשה שתי בעיות שונות (הניסוח הבינרי לעומת הניסוח הלא חסום), אבל לא ברור למה עדיף להראות פתרון מורכב ומסובך (יחסית) לבעיה הבינרית, במקום פתרון פשוט וברור יותר לבעיה הלא חסומה.

מעבר לכך: אין סיבה לנסות לקבל את "סוג הקירוב הכי טוב שאפשר להשיג" - בערך כזה די להראות שקיים אלגוריתם פשוט להסבר וזול מבחינה חישובית, שמבטיח פתרון שהוא "טוב לפחות כמו <שבר כלשהו> של הפתרון המיטבי". אגב, שים נא לב שהקישור וההוכחה שבו, למעשה מתייחסים לבעיה מוגבלת יותר, בה הערכים והמשקלים הם מספרים שלמים. אמנם לא הבנתי איפה בהוכחה נעשה שימוש בתנאי הזה - עד כמה שהצלחתי להבין, אותה הוכחה תופסת גם בלי המגבלה, אבל ההוכחה המקושרת מתייחסת לבעיה בניסוח מוגבל לשלמים. לגבי "למה הורדתי": בגלל שחשבתי שההוכחה יותר פגומה ממה שבעצם הייתה, החזרתי את הניסוח של כותב הערך המקורי (בתוספת הבהרה שהאלגוריתם מתייחס לבעיה הלא חסומה - חסרון ההבהרה הזו גרם למשתמש:Orielno לרשום בתקציר העריכה בה החליף את האלגוריתם "האלגוריתם לא תואר בצורה מלאה. האלגוריתם שתואר עד כה לא השיג חצי, במצבים מסוימים הוא יכל להשיג אפילו רק מיליונית" - דבר שאינו נכון, כמובן, כשמבינים שמדובר בבעיה הלא חסומה).

לגבי הורדת האמירה שקיים אלגוריתם של סכימת קירוב מלאה - זה סתם collateral damage: כיוון שהחלפתי הוכחה פגומה באלגוריתם נכון (בלי הוכחה, אבל נכונותו כמעט טריביאלית), החזרתי את הסעיף למצב בו השאיר אותו הכותב המקורי. לו התעמקתי יותר, כנראה התוספת הייתה ניצלת. על כך מגיעה לך התנצלות - אקווה שלא תזקוף זאת נגדי ביום הכיפורים הבא... :) קיפודנחש 23:17, 12 באוקטובר 2018 (IDT)

אתה מתייחס לבעיית התרמיל כאל כמה סוגי בעיות נפרדות שאינן מכילות אחת את השנייה, ואין זה כך. שלושת סוגי הבעיות הן כאלו שאחת מכילה את האחרת, כלומר: קבוצת בעיות תרמיל הגב הבינארי מכילה את קבוצת בעיות תרמיל הגב החסומה, וזו מכילה-ממש את קבוצת בעיות תרמיל הגב הלא חסומה. לכן, פתרון לבעיות תרמיל הגב הבינארי הוא פתרון לכל בעיית תרמיל גב, ועדיף להראות פתרון כללי שנכון לכל סוג של בעיה, מאשר פתרון שנכון רק עבור גרסה פרטית מסוימת של הבעיה. אוריאל, Orielno - שיחה 08:51, 13 באוקטובר 2018 (IDT)

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

_אבל_, (א) הערך עצמו עושה את ההבחנה הזו, והעיקר, (ב) נכון שהבעיה בניסוח הלא חסום היא תת קבוצה של הניסוח הבינרי, אבל נכון גם שעבור תת הקבוצה הזו יש "אלגוריתם החמדן" אמתי (כפי שציינתי, הניסוח הנוכחי אינו כזה), פשוט להסבר וקל להבנה, שמבטיח ערך שהוא לפחות מחצית הערך המיטבי.

הניסוח הנוכחי מסורבל, והוכחתו תופסת חלק לא פרופורציוני מהערך, בלי לתרום לקורא תרומה רלוונטית למידע על הבעיה, ומקומה במדעי המחשב. מסיבה זו, עריכתך ששיחזרתי הייתה לדעתי שיפור לרעה. קיפודנחש 16:59, 13 באוקטובר 2018 (IDT)