איך אלגוריתם יכול לתכנן מסלולים?
דמיינו סוכן נוסע שהבוס נותן לו רשימה של ערים ודורש ממנו לתכנן את המסלול הכי קצר ביניהן, כך שיעבור פעם אחת בדיוק בכל עיר ואז ישוב לנקודה שממנה התחיל את המסלול.
המשימה הלכאורה פשוטה הזו היא אחת הבעיות המסובכות בעולם המדעי. היא זכתה לשם "בעיית הסוכן הנוסע" (Travelling Salesman Problem) ומטרתה היא אכן למצוא אלגוריתם שימצא את המסלול הקצר ביותר שיחבר כמה נקודות גאוגרפיות עד החזרה לנקודה שממנה מתחילים.
זו בעייה ידועה מאוד ומהנושאים המבוקשים ביותר לפתרון בעולם הניווט כיום. היא חברה מכובדת בקבוצת הבעיות נטולות הפתרון של תורת הגרפים ותורת הסיבוכיות. היא גם מהבעיות המרכזיות בתחום האופטימיזציה, כשגם אנשי בינה מלאכותית ומדעני מחשב עוסקים בה לא מעט.
מכיוון שהבעיה נוגעת גם למטיילים, דוורים, מתכנני טיסות לחוצים בכסף ושליחים של וולט עם מנות טייק אוויי חמות, היא זכתה גם לכינוי העממי "בעיית השליחים".
זה פשוט, אתם ודאי אומרים לעצמכם. פשוט נמדוד על המפה את המרחקים בין כל שני מקומות במסלול ונסכם את המרחקים למרחק כולל. כך נמדוד בכמה מסלולים ונבחר את הקצר ביותר מהם.
אבל השיטה בה הולכים מנקודת ההתחלה לנקודה הקרובה ביותר, ממנה לנקודה הקרובה ביותר אליה וכך הלאה - השיטה הזו פשוט לא עובדת. במילים פשוטות, היא לא מציעה כך את המסלול הקצר ביותר.
דרכים אחרות? - בטח לא דרך ידנית.
רק שנבין כמה הבעיה מורכבת - פתרון בניסוי וטעייה הוא בלתי אפשרי כאן, כי אם יש לנו 10 נקודות בלבד, יש לה !N אפשרויות, N עצרת!, כלומר נצטרך להשוות
את המרחקים בלא פחות מ-3,628,800 אפשרויות או מסלולים אפשריים.
יותר מקומות? - זה רק יגדל. כדי שמחשב מהיר יעבור על כל האפשרויות שיש ל-100 יעדים, זה ייקח לו זמן בלתי סביר של 40 מיליון שנה עד שיגיע לתשובה.
ב-1857 המילטון אף פיתח את "משחק איקוסיאן" (Icosian game) שהמטרה בו הייתה למצוא את "המסלול ההמילטוני" שהוא הפתרון הקצר ביותר.
בשנת 1930, חוקר בשם קרל מנגר הגדיר את הבעיה והתייחס לפתרונות כוח גס ושיטת השכן הקרוב, אבל לא מצא פתרון.
בסנטה מניקה הציע תאגיד "ראנד", בשנות ה-50 וה-60 של המאה ה-20, פרסים על התקדמות, אפילו לא פתרון לבעיה. הדבר הפך את העניין לפופולרי מאוד, לפחות הצפון אמריקה ובאירופה. אבל שלל החוקרים, כולל מתמטיקאים, כימאים, פיזיקאים ואנשי מדעי המחשב, לא הניבו את הפתרון המיוחל. הבעייה נותרה ללא פתרון. המאבק היום הוא למצוא פתרון מקורב.
בשנת 2006 הצליחו לחקור ולוודא מסלול אופטימלי שעבר ב-85,900 נקודות. הוא מתוחזק ומאפשר מאז כלי בדיקה לאלגוריתמים שמציעים חוקרים לפתרון הבעיה.
שיטות אחרות בסרטונים שלמטה. הן לא מבטיחות את המסלול הקצר ביותר כמובן.
דמיינו סוכן נוסע שהבוס נותן לו רשימה של ערים ודורש ממנו לתכנן את המסלול הכי קצר ביניהן, כך שיעבור פעם אחת בדיוק בכל עיר ואז ישוב לנקודה שממנה התחיל את המסלול.
המשימה הלכאורה פשוטה הזו היא אחת הבעיות המסובכות בעולם המדעי. היא זכתה לשם "בעיית הסוכן הנוסע" (Travelling Salesman Problem) ומטרתה היא אכן למצוא אלגוריתם שימצא את המסלול הקצר ביותר שיחבר כמה נקודות גאוגרפיות עד החזרה לנקודה שממנה מתחילים.
זו בעייה ידועה מאוד ומהנושאים המבוקשים ביותר לפתרון בעולם הניווט כיום. היא חברה מכובדת בקבוצת הבעיות נטולות הפתרון של תורת הגרפים ותורת הסיבוכיות. היא גם מהבעיות המרכזיות בתחום האופטימיזציה, כשגם אנשי בינה מלאכותית ומדעני מחשב עוסקים בה לא מעט.
מכיוון שהבעיה נוגעת גם למטיילים, דוורים, מתכנני טיסות לחוצים בכסף ושליחים של וולט עם מנות טייק אוויי חמות, היא זכתה גם לכינוי העממי "בעיית השליחים".
הבעיה
דמיינו סוכן מכירות, שרוצה לפקוד את כל המקומות שבהם הוא אמור למכור את הסחורה שלו. האיש מעוניין למצוא את המסלול הקצר ביותר שיאפשר לו לעבור דרך כל המקומות, בכל מקום פעם אחת בלבד, ולסיים בנקודת ההתחלה.
זה פשוט, אתם ודאי אומרים לעצמכם. פשוט נמדוד על המפה את המרחקים בין כל שני מקומות במסלול ונסכם את המרחקים למרחק כולל. כך נמדוד בכמה מסלולים ונבחר את הקצר ביותר מהם.
אבל השיטה בה הולכים מנקודת ההתחלה לנקודה הקרובה ביותר, ממנה לנקודה הקרובה ביותר אליה וכך הלאה - השיטה הזו פשוט לא עובדת. במילים פשוטות, היא לא מציעה כך את המסלול הקצר ביותר.
דרכים אחרות? - בטח לא דרך ידנית.
רק שנבין כמה הבעיה מורכבת - פתרון בניסוי וטעייה הוא בלתי אפשרי כאן, כי אם יש לנו 10 נקודות בלבד, יש לה !N אפשרויות, N עצרת!, כלומר נצטרך להשוות
את המרחקים בלא פחות מ-3,628,800 אפשרויות או מסלולים אפשריים.
יותר מקומות? - זה רק יגדל. כדי שמחשב מהיר יעבור על כל האפשרויות שיש ל-100 יעדים, זה ייקח לו זמן בלתי סביר של 40 מיליון שנה עד שיגיע לתשובה.
תולדות הבעיה
במאה ה-19 היו ראשונים שניסחו את בעיית הסוכן הנוסע, שבראשי תיבות מכונה TSP, המתמטיקאים ויליאם המילטון מאירלנד והמתמטיקאי הבריטי תומאס קירקמן (Thomas Kirkman).
ב-1857 המילטון אף פיתח את "משחק איקוסיאן" (Icosian game) שהמטרה בו הייתה למצוא את "המסלול ההמילטוני" שהוא הפתרון הקצר ביותר.
בשנת 1930, חוקר בשם קרל מנגר הגדיר את הבעיה והתייחס לפתרונות כוח גס ושיטת השכן הקרוב, אבל לא מצא פתרון.
בסנטה מניקה הציע תאגיד "ראנד", בשנות ה-50 וה-60 של המאה ה-20, פרסים על התקדמות, אפילו לא פתרון לבעיה. הדבר הפך את העניין לפופולרי מאוד, לפחות הצפון אמריקה ובאירופה. אבל שלל החוקרים, כולל מתמטיקאים, כימאים, פיזיקאים ואנשי מדעי המחשב, לא הניבו את הפתרון המיוחל. הבעייה נותרה ללא פתרון. המאבק היום הוא למצוא פתרון מקורב.
בשנת 2006 הצליחו לחקור ולוודא מסלול אופטימלי שעבר ב-85,900 נקודות. הוא מתוחזק ומאפשר מאז כלי בדיקה לאלגוריתמים שמציעים חוקרים לפתרון הבעיה.
אז מה עושים?
השיטה הפשוטה היא הגרידית (Greedy). השיטה היא מכל נקודה ללכת אל הכי קרובה אליה.
שיטות אחרות בסרטונים שלמטה. הן לא מבטיחות את המסלול הקצר ביותר כמובן.
