שיחה:בעיית תרמיל הגב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ←אלגוריתמי קירוב: תקלדה |
←אלגוריתמי קירוב: תגובה |
||
שורה 81:
::::מעבר לכך: אין סיבה לנסות לקבל את "סוג הקירוב הכי טוב שאפשר להשיג" - בערך כזה די להראות שקיים אלגוריתם פשוט להסבר וזול מבחינה חישובית, שמבטיח פתרון שהוא "טוב לפחות כמו <שבר כלשהו> של הפתרון המיטבי". אגב, שים נא לב שהקישור וההוכחה שבו, למעשה מתייחסים לבעיה מוגבלת יותר, בה הערכים והמשקלים הם מספרים שלמים. אמנם לא הבנתי איפה בהוכחה נעשה שימוש בתנאי הזה - עד כמה שהצלחתי להבין, אותה הוכחה תופסת גם בלי המגבלה, אבל ההוכחה המקושרת מתייחסת לבעיה בניסוח מוגבל לשלמים. לגבי "למה הורדתי": בגלל שחשבתי שההוכחה יותר פגומה ממה שבעצם הייתה, החזרתי את הניסוח של כותב הערך המקורי (בתוספת הבהרה שהאלגוריתם מתייחס לבעיה הלא חסומה - חסרון ההבהרה הזו גרם ל[[משתמש:Orielno]] לרשום בתקציר העריכה בה החליף את האלגוריתם "האלגוריתם לא תואר בצורה מלאה. האלגוריתם שתואר עד כה לא השיג חצי, במצבים מסוימים הוא יכל להשיג אפילו רק מיליונית" - דבר שאינו נכון, כמובן, כשמבינים שמדובר בבעיה הלא חסומה).
::::לגבי הורדת האמירה שקיים אלגוריתם של סכימת קירוב מלאה - זה סתם collateral damage: כיוון שהחלפתי הוכחה פגומה באלגוריתם נכון (בלי הוכחה, אבל נכונותו כמעט טריביאלית), החזרתי את הסעיף למצב בו השאיר אותו הכותב המקורי. לו התעמקתי יותר, כנראה התוספת הייתה ניצלת. על כך מגיעה לך התנצלות - אקווה שלא תזקוף זאת נגדי ביום הכיפורים הבא... :) [[שיחת משתמש:קיפודנחש|קיפודנחש]] 23:17, 12 באוקטובר 2018 (IDT)
:::::אתה מתייחס לבעיית התרמיל כאל כמה סוגי בעיות נפרדות שאינן מכילות אחת את השנייה, ואין זה כך. שלושת סוגי הבעיות הן כאלו שאחת מכילה את האחרת, כלומר: קבוצת בעיות תרמיל הגב הבינארי מכילה את קבוצת בעיות תרמיל הגב החסומה, וזו מכילה-ממש את קבוצת בעיות תרמיל הגב הלא חסומה. לכן, פתרון לבעיות תרמיל הגב הבינארי הוא פתרון לכל בעיית תרמיל גב, ועדיף להראות פתרון כללי שנכון לכל סוג של בעיה, מאשר פתרון שנכון רק עבור גרסה פרטית מסוימת של הבעיה. אוריאל, [[משתמש:Orielno|Orielno]] - [[שיחת משתמש:Orielno|שיחה]] 08:51, 13 באוקטובר 2018 (IDT)
| |||