לגבי העניין שלא קיימים אלגוריתמים - תיקנתי את זה, אפילו לא שמתי לב שכתבתי את זה.
לגבי vi, אני התבלבלתי קצת והשתמשתי בשני סימונים. אני מעדיף את הסימון wi עבור משקל ולכן שיניתי את כל מופעי vi למופעי wi.
נכונות האלגוריתם החמדן - יש הוכחה לא מורכבת מדי ליחס הקירוב שלו אבל אני תוהה אם זה לא קצת כבד לתת אותה בערך הזה. כרגע אני חושב שהערך פונה לקהל יעד בלי מעורב מבחינת ידע מתמטי ואני חושב שלהוסיף הוכחת יחס קירוב קצת תפגע בנגישות עבור אנשים שפחות מבינים. אם אתה בכל זאת חושב שיש לזה מקום, אני יכול להוסיף את זה.
כיוון שהיה חשוב לי לצרף גם קוד לפתרון הבעיה, הלכתי על בעיית תרמיל הגב הבינארית גם בגלל הפשטות וגם בגלל שהיה לי מקור לקוד. אם פתרון לבעיית תרמיל הגב הרגילה הוא טוב יותר, אני יכול להחליף.
האם יש הערות טכניות לגבי הערך ? כלומר מעבר להערות על התוכן - עריכה, כללי ויקיפדיה וכו'
לא מצאתי בעיות טכניות. השתמשת יפה בנוסחאות המתמטיות ובקישורים פנימיים.
אני לא מכיר את ההוכחה לאלג' הזה (ראיתי שבדף שקישרת אליו היא לא ארוכה, אבל לא עקבתי אחריה). אם מדובר בהוכחה ארוכה ומסורבלת, אז יש לשקול האם להוסיף את ההוכחה לערך. אחרת, לעניות דעתי, יש להוסיף אותה לערך (תוך ניסיון שתהא ברורה גם עבור אלו שאינם בקיאים). אני לא חושב שיש צורך שכל קטע וקטע בוויקיפדיה יהיה נהיר עבור כל קורא, גם אם כדאי להשתדל שכן.
לגבי הבעיה הבינארית, זה לא נראה לי ממש עקרוני, פשוט עלתה לי התהיה מדוע הפתרון הוא דווקא לבעיה הבינארית, ועכשיו הבנתי מדוע.
לדעתי במצב אידאלי, תסופק בערך גם ההוכחה לכך שהבעיה הינה NP שלמה (אני, אגב, לא מכיר גם את ההוכחה הזו). עם זאת, אני מניח שההוכחה היא רדוקציה מבעיה אחרת, ולא מצאתי הוכחה ל-NP-שלמות של הבעיות הבסיסיות, כך שהוכחה כזו תיצור "חור", ועדיף כבר לא להביאה. אופקאלף • שיחה • הצטרפו למיזם המקורי! 18:32, 23 באפריל 2014 (IDT)תגובה
אני מנסה לראות עד כמה אפשר להכניס תכנים יותר תאורטיים כמו הוכחת הקושי (ואולי גם הוכחת הקירוב). ניסיתי לחפש ומצאתי מקור שמציין רדוקציה לבעיית החלוקה, ניסיתי לתמצת כאן גרסה של ההוכחה. זה מרגיש קצת חסר ואני לא שלם עם זה במאה אחוז אבל אני גם לא רוצה לתת לחלק הזה של המאמר יותר משקל ממה שהוא צריך לקבל מה אתה חושב ? אם זה סביר אני מתאר לעצמי שאפשר להראות גם את הוכחת הקירוב של האלגוריתם החמדן, אם כי כדי באמת לתת את ההוכחה הזו צריך לדבר על חסמים תחתונים לאופטימום, ובהוכחה הקנונית גם עוברים דרך בעיית תרמיל הגב השברית שלא הזכרנו בערך (אפשר לעקוף את זה, אבל, שוב, מדובר בעוד פרטי הוכחה). מה דעתך ?
ראשית טיפלתי בארגון של הקישורים, עכשיו זה נראה הרבה יותר טוב מאשר רשימת PDF-ים. לגבי בעיית החלוקה הוספתי הערת שוליים שמתארת את הבעייה. אני ממש לא בטוח מה התכוונת לגבי P - זה מוגדר ברדוקציה ואני לא בטוח מה לא ברור פה. באופן כללי אני לא שלם עם הוכחת הקושי והאופן שבה היא מוצגת, אולי זה בכל זאת לא צריך להיכנס כאן (אבל אם זה נראה לך בסדר, אני איתך). האם יש לך הערות נוספות על הערך ? האם אתה חושב שהוא מוכן לעלות למרחב הציבורי ? האם תוכל להגיד לי מה אני מריך לעשות כדי להעלות אותו למרחב הציבורי ?
התבלבלתי, זה בסדר. אולי תוכל להסביר במשפט את ה"אם ורק אם" שברדוקציה? (כלומר: בהינתן חלוקה - התרמיל החוקי יהיה... ובהינתן תרמיל, החלוקה תהיה...) לא התעמקתי אבל זה לא נראה לי טריוויאלי.
המונח פיזיבילי הוא מונח מתחום האופטימיזציה שבא לתאר כל פתרון של הבעייה שעומר באילוצים (קח לדוגמה תכנון לינארי - פתרון פיזיבילי הוא פתרון שוקטור שמקיים את כל האילוצים הלינאריים). באנגלית זה מונח מקובל ולצערי אין לי מינוח עברי מקובל (ובדקתי באפליקציה של האקדמיה...). אם מישהו במקרה מוצא מילה עברית או דרך טובה יותר להביע את העניין אני אשמח לשמוע. הפתרון שאני יכול להציע הוא פשוט להחליף "פיזיבילי" ב-"פתרון העומד באילוצים". דעתכם ? --Eidanch - שיחה17:54, 3 במאי 2014 (IDT)תגובה
החלפתי את המונח "תת-קבוצה" במונח "אוסף", משום שהמונח "תת-קבוצה" מתאים רק לבעיית תרמיל הגב הבינארי.
הערך השתמש לסירוגין במונחים "מחיר" ו"ערך". למען האחידות שיניתי את כל המופעים ל"מחיר" (יש שיגידו ש"מחיר" ו"ערך" אינן מילים נרדפות). דוד שי - שיחה19:22, 3 במאי 2014 (IDT)תגובה
הקוד בפייתון מחורבש (חוץ מהזחה אחת של תוכן הפונקציה, כל ההזחות האחרות התאיידו). אנא החזר את ההזחות, ועל הדרך, החלף את הרווחים בטאבים. קיפודנחש19:32, 16 ביוני 2014 (IDT)תגובה
לא הייתי משתמש במינוח שהשתמשת בו, אבל אתה צודק, הקוד לא היה תקין. תיקנתי. לגבי רווחים וטאבים, אני דווקא מעדיף את שיטת הרווחים ולא את הטאבים ולכן השארתי את ההזחה בפורמט של ארבעה רווחים. --Eidanch - שיחה22:40, 16 ביוני 2014 (IDT)תגובה
@Eidanch: לא הייתה כל כוונה לפגוע במישהו - כתוצאה מתקלה כזו או אחרת הקוד התחרבש. להבא, אשמח להשתמש במינוח אחר אם תאמר לי מה המינוח המועדף עליך. @Ofekalef: הדרך הקצרה היא בעזרת "העתק/הדבק": מעתיקים תו טאב מדף בו התו כבר קיים או מיישום אחר, ומדביקים בעורך ויקי. הדרך ה"נכונה" היא בעזרת עורך הקוד, אבל למרבה הצער העורך מופעל רק בדפים ששמם מסתיים ב-js או css, ובדפים במרחב "יחידה". באופן כללי, כשמוסיפים קטע קוד לדף, עדיף לערוך את הקוד בכלים הטבעיים, ואחרי שהקוד מתהדר ורץ נכון, מדביקים בדף (ואז הטאבים מגיעים בשלמותם). בהרבה מקרים אי אפשר לעשות הכל, משום שמדובר ב-snippet, אבל תמיד אפשר לערוך בעורך קוד "אמתי" ולהדביק לדף. במקרה הזה, אפשר לבדוק את הקוד ממש, משום שמדובר בפונקציה שלמה' ומשום שפייתון לא דורש הרבה ביורוקרטיה. קיפודנחש23:50, 16 ביוני 2014 (IDT)תגובה
הקוד הוצג בין תגי source, כך שהוא נראה נכון, ואפילו צבוע בצורה נאה. יתכן שלמשך תקופה קצרה אחד השרתים מגמגם, וכמה קבצי CSS לא הגיעו לדפדפן שלך, וזה גרם לבעיה שראית. ביטלתי את העריכה שלך, לפי ההיגיון שמקרים קשים יוצרים דין רע. הקוד צריך להיראות נכון עכשיו. קיפודנחש11:19, 11 ביולי 2015 (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)תגובה
אכן שגיתי, אבל שגיאה שונה מזו שאתה מתאר: ההבדל הוא לא בין "הבעיה השברית" לבעיה עצמה, אלא בין הבעיה הבינרית לבעיה הלא חסומה. התיאור המקורי (שאגב, אינו "האלגוריתם שלי", אלא של כותב הערך המקורי) עדיף, לדעתי, מכמה טעמים: (1) הניסוח שלו קל ופשוט בהרבה (2) קל לראות שהוא אכן מספק פתרון שערכו אכן לפחות מחצית מהפתרון המיטבי, לעומת הפתרון הנוכחי בו קשה לראות זאת (3) הוא באמת "אלגוריתם חמדן" לעומת האלגוריתם שמופיע כעת בערך, שאינו כזה, למרות שהוא מכריז על עצמו ככזה.
כאמור, האלגוריתם המקורי והנוכחי פותרים למעשה שתי בעיות שונות (הניסוח הבינרי לעומת הניסוח הלא חסום), אבל לא ברור למה עדיף להראות פתרון מורכב ומסובך (יחסית) לבעיה הבינרית, במקום פתרון פשוט וברור יותר לבעיה הלא חסומה.
מעבר לכך: אין סיבה לנסות לקבל את "סוג הקירוב הכי טוב שאפשר להשיג" - בערך כזה די להראות שקיים אלגוריתם פשוט להסבר וזול מבחינה חישובית, שמבטיח פתרון שהוא "טוב לפחות כמו <שבר כלשהו> של הפתרון המיטבי". אגב, שים נא לב שהקישור וההוכחה שבו, למעשה מתייחסים לבעיה מוגבלת יותר, בה הערכים והמשקלים הם מספרים שלמים. אמנם לא הבנתי איפה בהוכחה נעשה שימוש בתנאי הזה - עד כמה שהצלחתי להבין, אותה הוכחה תופסת גם בלי המגבלה, אבל ההוכחה המקושרת מתייחסת לבעיה בניסוח מוגבל לשלמים. לגבי "למה הורדתי": בגלל שחשבתי שההוכחה יותר פגומה ממה שבעצם הייתה, החזרתי את הניסוח של כותב הערך המקורי (בתוספת הבהרה שהאלגוריתם מתייחס לבעיה הלא חסומה - חסרון ההבהרה הזו גרם למשתמש:Orielno לרשום בתקציר העריכה בה החליף את האלגוריתם "האלגוריתם לא תואר בצורה מלאה. האלגוריתם שתואר עד כה לא השיג חצי, במצבים מסוימים הוא יכל להשיג אפילו רק מיליונית" - דבר שאינו נכון, כמובן, כשמבינים שמדובר בבעיה הלא חסומה).
לגבי הורדת האמירה שקיים אלגוריתם של סכימת קירוב מלאה - זה סתם collateral damage: כיוון שהחלפתי הוכחה פגומה באלגוריתם נכון (בלי הוכחה, אבל נכונותו כמעט טריביאלית), החזרתי את הסעיף למצב בו השאיר אותו הכותב המקורי. לו התעמקתי יותר, כנראה התוספת הייתה ניצלת. על כך מגיעה לך התנצלות - אקווה שלא תזקוף זאת נגדי ביום הכיפורים הבא... :) קיפודנחש23:17, 12 באוקטובר 2018 (IDT)תגובה
אתה מתייחס לבעיית התרמיל כאל כמה סוגי בעיות נפרדות שאינן מכילות אחת את השנייה, ואין זה כך. שלושת סוגי הבעיות הן כאלו שאחת מכילה את האחרת, כלומר: קבוצת בעיות תרמיל הגב הבינארי מכילה את קבוצת בעיות תרמיל הגב החסומה, וזו מכילה-ממש את קבוצת בעיות תרמיל הגב הלא חסומה. לכן, פתרון לבעיות תרמיל הגב הבינארי הוא פתרון לכל בעיית תרמיל גב, ועדיף להראות פתרון כללי שנכון לכל סוג של בעיה, מאשר פתרון שנכון רק עבור גרסה פרטית מסוימת של הבעיה. אוריאל, Orielno - שיחה08:51, 13 באוקטובר 2018 (IDT)תגובה
מצד אחד, אתה צודק: אפשר להסתכל על הבעיה הלא חסומה, עבור תרמיל עם מגבלה נתונה, כאילו היא הבעיה הבינרית, משום שלכל משקל נתון יש לכל היותר x פריטים שאפשר להכניס, ולכן היא כמו הבעיה החסומה, שמצידה היא בעצם סוגשל הבעיה הבינרית, בה חלק מהפריטים זהים.
_אבל_, (א) הערך עצמו עושה את ההבחנה הזו, והעיקר, (ב) נכון שהבעיה בניסוח הלא חסום היא תת קבוצה של הניסוח הבינרי, אבל נכון גם שעבור תת הקבוצה הזו יש "אלגוריתם החמדן" אמתי (כפי שציינתי, הניסוח הנוכחי אינו כזה), פשוט להסבר וקל להבנה, שמבטיח ערך שהוא לפחות מחצית הערך המיטבי.
הניסוח הנוכחי מסורבל, והוכחתו תופסת חלק לא פרופורציוני מהערך, בלי לתרום לקורא תרומה רלוונטית למידע על הבעיה, ומקומה במדעי המחשב. מסיבה זו, עריכתך ששיחזרתי הייתה לדעתי שיפור לרעה. קיפודנחש16:59, 13 באוקטובר 2018 (IDT)תגובה
