הסוכן הנוסע

[חייםאבג]

הסוכן הנוסע

יש לי הצעה לפיתרון הבעיה - איך אני יכול להוכיח שזהו פיתרון מנצח?

 

[neko]

תניח שיש לך פתרון אחר

שהוא אופטימלי, ותראה שלא יכול להיות שהפתרון האופטימלי הזה יותר טוב משלך.

 

[טיורינג]

לא הבנתי

יש לך הצעה שפותרת את הבעיה בזמן פולינומיאלי או מה?

 

[חייםאבג]

אז ככה, אני לא מתמטיקאי ולא איש מחש

מחשבים... אז... בדחילו... מה זה בעברית "פולינומיאלי"?

 

[טיורינג]

אה...

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

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

 

[חייםאבג]

איך אתה מקשר בין "הסוכן" למספרים

ראשוניים ו-(מה זה)-בעית התרמיל? איך אני יכול לבחון את הפתרון שלי לעומת הפתרונות של "מיטב המוחות" ו... אתה אמרת... איך עושים מזה כסף?

 

[טיורינג]

רגע, פרה פרה...

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

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

 

[sagima]

אולי כדאי להדגיש

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

 

[טיורינג]

נכון, אתה כמובן צודק

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

 

[חייםאבג]

מה זה "היוריסטי"?

 

[ahab]

"כלל אצבע"

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

 

[טיורינג]

חיים? עדיין איתנו?

או שהתייאשת מפרץ הביטויים ששפכנו פה...

 

[ron369]

סאב-אקספוננציאלי זה לא בהכרח פול'

(ולהיפך, על פולינומיאלי זה לא בהכרח אקספוננציאלי)(נדחף

)

 

[mE and Me]

מה יש ביניהם (בין פולי' לאקספ')?

 

[ron369]

אינסוף פונקציות, ככל הנראה ../images/Emo3.gif

למשל n^lgn אמורה להיות שייכת ל"מחלקה" הזו, אם אני לא טועה.

 

[ron369]

הוכחה

סאב אקספוננציאלית: n^lgn = e^lgnlgn = e^lg^2n = o(e^n) = o(e^lg(2)n) = 2^n) מש"ל.

 

[ron369]

אה, ועל פולינומיאלית זה טריוויאלי

(ו, זה היה אמור לעבור צד בחלון

)

 

[mE and Me]

הבנתי, תודה על ההסבר

 

[neko]

אבל 2 בחזקת n לא קצת אקספ'?

 

[mE and Me]

זה אמנם (O(2^n אבל אפשר לתחום את זה

גם ב-(O(2^lg²n, ואז בגלל ש-lg²n<<n אזי גם: zzz 2^lg²n<<2^n (ככה לפחות יצא לי).