הסוכן הנוסע

הסוכן הנוסע

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

../images/Emo12.gif מה פרוש להוכיח?

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

...כן....

ומאחר ואיני מתמטיקאי, ומאחר ולדעתי הפיתרון שלי הוא "טוב", איך אני מוכיח את ה"איכות" שלו, את היעילות שלו... וכו'.

צריך להבין מעט בסיבוכיות

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

תיקון קטן

הפורום המתאים יהיה פורום מדעי המחשב.

תודה

תשובה

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

שאלה

מה זה בעיית הנוסע.. מה אומר p=np ? מה זה npc .. אגב אני מדמחניק, אבל Noob (סמסטר 3) אז לא נתקלתי במושגים האלה, שאגב נשמעים מאוד מעניינים אני יודע שnp זה בעיות שפתירות רק במעבר על כל האפשרויות ,נניח לקבל קבוצת מספרים ולבדוק אם אפשר לחלק אותה ל2 קבוצות ככה שסכום האיברים באחת שווה לסכום בשניה.. אשמח אם תבהיר את המושגים האלה..

אוקי את הסוכן מצאתי

http://he.wikipedia.org/wiki/%D7%91%D7%A2%D7%99%D7%99%D7%AA_%D7%94%D7%A1%D7%95%D7%9B%D7%9F_%D7%94%D7%A0%D7%95%D7%A1%D7%A2 לא הבנתי מה רע למצוא גרף פורש מינמום כמו שעושים במבנה נתונים ?

מה יעזור לך עץ פורש?

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

אין בעיה למצוא עץ פורש מינימום

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

לא הבנתי

נניח יש לי גרף ויש לי על כל קשת "משקל" שמייצג כמה מרחק צריך לעבור בשביל לעבור בקשת אני יכול לפרוש את כל הגרף לעץ שבו אם אני אלך המסלול יהיה הכי קצר... לא ?

לא.

איך אתה יודע שהמסלול הקצר ביותר הוא עץ?

שאלה טובה

הסבר

אתה מנסה למצוא לבעיה פתרון מבלי לדעת את הגדרת הבעיה? בעית הסוכן הנוסע היא זו: בהינתן אינסטנציה של גרף שלם, לא מכוון וממושקל עם משקלות אי-שליליים לקשתות, מצא בגרף מעגל המילטון במשקל מינימלי. אינני יודע אם אני מכיר את כל המושגים בהם השתמשתי בניסוח המתמטי המדויק הנ"ל של הבעיה. אז הנה הסבר קצר על כל מונח: גרף זה יחס דו מקומי E(u,v על קבוצת קדקדים. אם הזוג u,v נמצא ביחס, אז יש קשת מכוונת בין u ל v. גרף לא מכוון זה גרף בו היחס E הוא יחס סימטרי, היינו לכל u,v אי של יו וי גורר אי של וי יו. אם אתה מצייר את זה, אז לשם נוחות לא צריך לצייר גרף לא מכוון ע"י קשת אחת בכל כיוון, אלא פשוט ע"י קו במום קו עם חץ בקצה. גרף שלם הוא גרף שבו היחס E הוא יחס מלא, היינו בין כל זוג קדקדים יש קשת. גרף ממושקל הוא גרף שבו יש פונקציה דו-מקומית שמתאימה לכל קשת (זוג איברים הנמצאים ביחס E) מספר (ממשי). מעגל המילטון: "טיול" בגרף המתחיל מקודקוד x, עובר בכל קדקד בגרף פעם אחת בלבד, ומסתיים בקדקד x. הבעיה הזו, TSP, היא בעיה קשה מבחינה חישובית. אנו מבחינים במחלקות חישוביות שונות עבורות בעיות כריעות. ידוע, למשל, אלגוריתם שבזמן ריצה בסדר-גודל אקספוננציאלי פותר את TSP. אבל סיבוכיות כזו איננה טובה כי, למשל, אם יש 100 קדקדים, מספר הצעדים של האלגוריתם במקרה הכללי הוא 2 בחזקת 100 (כפול איזה קבוע ממשי). נניח שיש מחשב שמחשב את זה תוך שניה אחת. עכשיו נגדיל את הקלט להיות באורך 200. למחשב לא תקחנה 2 שניות, אלא פי 2 בחזקת 100 זמן מהזמן הקודם. אם קודם לקח שניה, עכשיו זה 2 בחזקת 100 שניות. תחשוב לבד כמה הרבה זה. הקלט רק הוכפל באורכו, אבל זמן הריצה גדל בצורה מעריכית. יש מחלקות זמן ריצה גרועות יותר, דאבל אקספוננטיאל, שזה שתיים בחזקת שתיים בחזקת n. ויש גם עוד יותר גרוע, שתיים בחזקת שתיים בחזקת שתיים... n פעמים! (ויש בעיות שזה החסם שלהן!) עכשיו, מחלקת הסיבוכיות P היא מחלקת כל הבעיות שלכל אחת מהן קיים אלגוריתם שבזמן ריצה שהוא פונקציה פולינומיאלית של אורך הקלט מסיים ריצתו. NP זו מחלקת הסיבוכיות של כל הבעיות שלכל אחת מהן, אם יודעים מהי התשובה עבור אינסטנציה (קלט) כלשהו, אפשר לבדוק בזמן פולינומיאלי אם התשובה הזו נכונה או לא. התשובה לא נקראת כך, אלא נקראת "עד". אז כדי להוכיח שבעיה היא בNP, תנחש תשובה, ותראה שניתן בזמן פולינומיאלי להכריע האם התשובה נכונה או לא. תכונת קשיות NP היא שמכל בעיה בNP אפשר לעשות רדוקציה לבעיה שהיא NP קשה. זה אומר שבעיה NP קשה היא קשה לחישוב לפחות כמו כל בעיה בNP. לקבוצת הבעיות בNP שהן גם NP קשות קוראים NPC. לאף אחת מהן לא ידוע אלגוריתם בזמן ריצה פולינומיאלי. מוכיחים על בעיה מסוימת, 3 SAT שהיא NP קשה ע"י תרגום כל בעיה בNP המנוסחת עבור מכונת טיורינג (מודל חישובי שקול למחשב) לנוסחה בצורת 3SAT. זה נקרא משפט קוק. מעתה והלאה, כדי להראות שבעיה היא NP קשה, צריך להראות שאפשר לעשות רדוקציה ממנה ל3SAT. ואם היא גם בNP אז היא NPC. P מוכלת בNP, כי אם יש אלגוריתם פולינומיאלי למצוא התשובה, אפשר לייצר את התשובה בזמן פולינומיאלי, ואז אם יש לנו "עד" אפשר להריץ על הקלט ולהשוות לעד, וההשוואה זה O של n, ולכן זה בNP. את השאלה ההפוכה לא יודעים. אבל אם תראה על אחת מבעיות NPC, כמו TSP או SAT, שיש להן אלג' פולינומיאלי, אז מאחר שכולן "קשות באותה מידה" (זו המשמעות לכך שהן באותה המחלקה), יהיה אלגוריתם לכולן. בהצפנה למשל, מסתמכים על כך שNP שונה מP, ולכן לא ריאלי שמישהו יחפש את כל האפשרויות כי זה יקח לו זמן מעריכי.

עובר בכל קודקוד *לפחות* פעם אחת

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

לא לפחות, בדיוק

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

אתה צודק. סליחה על ההערה המיותרת.

טוב

P זה אוסף הבעיות שיש להן פתרון בזמן פולינומיאלי. NP זה אוסף כל הבעיות שאם אתה אומר לי מהו הפתרון, אז אני יכול לבדוק אם הוא באמת הפתרון בזמן פולינומיאלי. למשל בעיית subset-sum: קלט: n מספרים טבעיים ומספר t. שאלה: האם יש תת קבוצה של המספרים האלו שסכומם הוא t? מדוע היא בNP? כי אם תגיד לי איזה מספרים יש בתת הקבוצה שאתה חושב שהיא מתאימה, אז אני אוכל לבדוק אם היא אכן מתאימה והבדיקה תהיה בזמן פולינומיאלי. כלומר: אני צריך לבדוק אם אכן כל אחד מהמספרים בתת הקבוצה הוא אכן בקבוצה של n המספרים המקוריים, ואני צריך לבדוק אם סכומם הוא אכן t. ברור שכל זה יקח לי זמן פולינומיאלי. P מוכלת בNP (לא ניכנס בדיוק למה זה נכון. מה גם שאני לא ממש בטוח). השאלה (שאם תפתור אותה תקבל מליון דולר, באמת) היא האם P=NP? כלומר, האם לכל בעיה שניתן לבדוק את הפתרון שלה בזמן פולינומיאלי היא גם פתירה בזמן פולינומיאלי. NPC זה אוסף של בעיות שאם תוכיח שאחת מהן פתירה בזמן פולינומיאלי, אז מזה נובע שP=NP. אכן נושא מאוד מעניין. אם אתה רוצה אני יכול לשלוח לך לינק לסיכומי הרצאות בנושא. אגב, בתור מדמ"חניק (אתה מדמ"חניק???) אתה תלמד את הדברים בכל מקרהץ