בעיית הסוכן הנוסע.

[SweeT_EviL]

אני מניח שכולם יודעים על מה אני מדבר. במידה ולא

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

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

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

שפה? אם זה משנה שיהיה C.

תודה.

[שניצל]

שני תיקונים קטנים טפשיים:

א. קוראים לבעיה "בעיית הסוכן הנוסע", לא הנוסע המתמיד.

ב. הסיבוכיות היא !n.

חוץ מזה, כדאי להתחיל מכאן:

http://en.wikipedia.org/wiki/Travelling_salesman_problem

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

[SweeT_EviL]

D=

שונה. יקרא ויחזור לשאלות..

עריכה:

אני לא מחפש פתרון פשוט =]

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

[exercise]

תהיה בטוח שלא כולם יודעים על מה אתה מדבר

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

פתרון מיטבי תמצא בטח בקוד של TSPLIB.

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

[Buffer]

אם אתה מגביל ל-5 יעדים ה-tradeoff הוא הפתרון שהציע שניצל.

אתה תגיע לסיבוכיות של 5!=120 שזה O(1)

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

אם אתה בכל זאת רוצה, זה מצריך הרבה ידע מוקדם בגרפים. אתה יכול להסתכל על שני האלגוריתמים האלה: http://en.wikipedia.org/wiki/Dijkstra's_algorithm

http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

[exercise]

אם אתה מגביל מראש למספר קבוע של יעדים, אז הסיבוכיות תמיד תהיה O(1).

[SerpentMage]

דווקא הפתרון האידיאלי הכללי לא צורך הרבה ידע בתורת בגרפים (למרות שאתה ממפה את הבעיה למודל של גרף), אלא יותר בטכניקה של תכנות דינאמי: http://en.wikipedia.org/wiki/Dynamic_programming

היא מאפשרת פתרון בסיבוכיות של N² * 2^N

האלגוריתם עצמו (קרדיט לטכניון):

ואכן, עבור 5 יעדים הפתרון של שניצל הוא האידיאלי.

[Zelig]

ישנם "פתרונות" היוריסטים עם שגיאה חסומה ל-TSP.

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

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

[SerpentMage]

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

את מה שהזכרת אני דווקא לא זוכר, אבל שווה מאוד לבדוק.

[SweeT_EviL]

דווקא הפתרון האידיאלי הכללי לא צורך הרבה ידע בתורת בגרפים (למרות שאתה ממפה את הבעיה למודל של גרף), אלא יותר בטכניקה של תכנות דינאמי: http://en.wikipedia.org/wiki/Dynamic_programming

היא מאפשרת פתרון בסיבוכיות של N² * 2^N

האלגוריתם עצמו (קרדיט לטכניון):

ואכן, עבור 5 יעדים הפתרון של שניצל הוא האידיאלי.

לא הכי הבנתי את האלגוריתם הזה - שורות 3,4.

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

עוד מעט אני יקרא עוד פעם את ויקיפדיה.