בעיית הסוכן הנוסע נוסחה לראשונה במאה ה-19 על ידי המתמטיקאי האירי ויליאם רואן המילטון והמתמטיקאי הבריטי תומאס קירקמן (Thomas Kirkman). המילטון פיתח בשנת 1857 את "משחק איקוסיאן" (Icosian game) שמטרתו הייתה למצוא מסלול המילטוני שיעבור בכל הקודקודים של דודקהדרון בדיוק פעם אחת ויחזור לנקודת ההתחלה.
הצורה הכללית של בעיית הסוכן הנוסע נחקרה לראשונה על ידי מתמטיקאים בשנת 1930, בפרט על ידי קרל מנגר שהגדיר את הבעיה והתייחס לפתרונות כוח גס ושיטת השכן הקרוב:בשנות ה-50 וה-60 של המאה ה-20 הבעיה הפכה פופולרית באירופה וארצות הברית לאחר שתאגיד ראנד מסנטה מוניקה הציע פרסים על מציאת שלבים בפתרון הבעיה. בשנות ה-60 התפתחה גישה חדשה - במקום לחפש את הפתרון האופטימלי, החלו אנשים לחפש את הפתרון הגרוע ביותר ובכך למצוא חסם עליון לבעיה. בעשורים שלאחר מכן נחקרה הבעיה על ידי מתמטיקאים, חוקרי מדעי המחשב, כימאים, פיזיקאים ומדענים אחרים.
בשנת 1972 ריצ'רד קארפ הראה שמסלול המילטון היא בעיה השייכת לקטגוריה NP-שלמה, ובכך סיפק הסבר מתמטי לקושי החישובי במציאת מסלול אופטימלי.
בשנת 1991 פרסם ג'רארד ריינלט ספרייה בשם TSPLIB שכללה אוסף של רשימות ערים לדוגמה בדרגות קושי שונות. חוקרים רבים עשו שימוש נרחב בספרייה, ובשנת 2006 ויליאם ג'ון קוק וחוקרים נוספים חישבו מסלול אופטימלי שעבר ב-85,900 נקודות, נכון להיום החישוב הגדול ביותר מתוך TSPLIB. ספריה זו מתוחזקת לצורך בדיקת אלגוריתמים לפתרון הבעיה, ומכילה נתונים רבים, חלקם ערים ומעגלים מודפסים אמיתיים.
מאפיינים.
הצגה כבעיית גרפים.
ניתן להציג את בעיית הסוכן הנוסע כגרף ממושקל לא מכוון, בו כל עיר היא צומת, דרך בין עיר לעיר היא קשת, והמרחק בין כל שתי ערים מצוין על ידי משקל הקשת המחברת ביניהן. בצורה כזו ניתן לשאול מהו המסלול עם המשקל הנמוך ביותר, שיצא ויחזור לאותו צומת לאחר שעבר בכל צומת אחר פעם אחת בדיוק. לרוב הבעיה תוצג על גבי גרף שלם (גרף בו כל זוג צמתים מחוברים בקשת). אם לא קיימת דרך בין שתי ערים ניתן להוסיף לגרף קשת עם משקל גבוה מאוד ובכך להשלים את הגרף לגרף שלם מבלי לפגוע בפתרון האופטימלי.
סימטריות.
בגרסה הסימטרית של הבעיה, המרחק בין כל שתי ערים זהה למרחק בכיוון ההפוך בין אותן שתי ערים. במקרה כזה תוצג הבעיה כגרף לא מכוון. סימטריה זו מקטינה את מספר הפתרונות האפשריים פי שניים. בגרסה הא-סימטרית של הבעיה, ייתכן ודרך לא תתאפשר לשני הכיוונים, או שהמרחק בכיוונים שונים יהיה שונה. במקרה כזה תוצג הבעיה כגרף מכוון. דוגמאות לדרכים בהן ניתן להפוך את הבעיה לבעיה א-סימטרית הן כבישים חד סטריים, נתיבי תעופה בין ערים עם זמני הגעה או עלויות שונות, תאונות דרכים ועוד.
סיבוכיות חישוב.
בעיה זו נכללת בקטגוריה NP-קשה, והצגתה כבעיית הכרעה (בהינתן האורך X, קבע האם קיים מסלול שאורכו קטן מ-X) שייכת לקטגוריה NP-שלמה. לכן, אפשרי שזמן הריצה הגרוע ביותר של כל אלגוריתם לפתרון הבעיה יפעל בסדר גודל מעריכי כתלות בקלט (מספר הערים).
פתרון הבעיה.
הקווים המנחים לטיפול בבעיות NP-קשות הם:
אלגוריתמים מדויקים.
פתרון פשוט לבעיה הוא בדיקת כל התמורות האפשריות וחיפוש המסלול הקצר ביותר (תוך שימוש בכוח גס). פתרון זה מצריך בדיקה של formula_1 אפשרויות (עצרת של מספר הערים), ולכן סיבוכיות זמן הריצה במקרה כזה תהיה formula_2. חישוב כזה הופך מהר מאוד לבלתי מעשי (לבלתי יעיל, במינוח של מדעי המחשב). דוגמה להמחשת הבעיה: אם ישנן 70 ערים בהן על הסוכן לבקר, יצטרך הסוכן לבחון formula_3 מסלולי נסיעה אפשריים, אשר מהווים מספר רב יותר ממספר האטומים ביקום כולו.
בשנת 2001 נמצא פתרון מדויק של הבעיה עם 15,112 ערים בגרמניה מתוך TSPLIB. החישובים התבצעו ברשת של 110 מעבדים באוניברסיטאות רייס ופרינסטון שבארצות הברית. במאי 2004 נמצא מסלול באורך 72,500 קילומטרים שעבר בכל 24,978 הערים בשוודיה והוכח כמסלול הקצר ביותר שקיים. במרץ 2005 נמצא מסלול שעבר דרך 33,810 נקודות על מעגל מודפס שאורכו היה 66,048,945 (יחידות TSPLIB). חישוב המסלול ארך זמן המקביל ל-15.7 שנות חישוב של מעבד ממוצע באותה התקופה. באפריל 2006 נמצא מסלול שעבר דרך 85,900 נקודות, בכוח עיבוד שהקביל ל-136 שנות חישוב.
קירובים לפתרון.
אף על פי שהבעיה קשה לחישוב, כיום ידועות מספר היוריסטיקות לפתרונות מקורבים שלה. שיטות מודרניות יכולות למצוא פתרונות לבעיות גדולות מאוד (מיליוני ערים), בזמן סביר, שמובטחים להיות בסטייה של עד 2-3% מהמסלול האופטימלי.
אלגוריתם חמדן.
דוגמה לאלגוריתם חמדן המחפש קירוב למסלול הקצר ביותר היא "שיטת השכן הקרוב". בשיטה זו בכל צעד הסוכן יפנה לעיר הקרובה אליו ביותר שעוד לא ביקר בה. בעזרת אלגוריתם זה ניתן לקבל במהירות מסלול קצר ויעיל. עבור מספר מסוים של ערים בפיזור אקראי לרוב יתקבל מסלול ארוך ב-25% מהמסלול הקצר ביותר. עם זאת, קיימים סידורי ערים מיוחדים שגורמים לאלגוריתם זה להניב את התוצאה הגרועה ביותר, הן בגרסה הסימטרית והן בגרסה הא-סימטרית.
יישומים נוספים.
בנוסף לחשיבותה התאורטית בתחום חקר ביצועים, לבעיה גם חשיבות מעשית - לא רק בתחום התחבורה והלוגיסטיקה, אלא גם בייצורו של מעגל מודפס, שבו על מכונת הייצור לעבור מסלול מסוים בעת שהיא יוצרת חורים בלוח שעליו נמצא המעגל. שימוש נוסף מגיע מתחום האסטרונומיה - אסטרונומים הצופים בגופים רבים בחלל רוצים לצמצם את הזמן שנדרש לכיוון הטלסקופ בין גוף לגוף ככל האפשר, ובכך לייעל את עבודתם.
ביצועים אנושיים.
בעיית הסוכן הנוסע עניינה חוקרים מתחום הפסיכולוגיה הקוגניטיבית שבדקו את הביצועים האנושיים בהתמודדות עם הבעיה. מחקרים מראים שאנשים מסוגלים ליצור פתרונות איכותיים במהירות, מסקנה שרומזת שייתכן וביצועי מחשבים בתחום יכולים להשתפר על ידי הבנה וחיקוי של דרכי חשיבה של בני אדם. מחקרים אלו גם הובילו לגילויים חדשים על המנגנון שמאחורי המחשבה האנושית. הגיליון הראשון של כתב העת "Journal of Problem Solving" הוקדש לנושא של ביצועים אנושיים בניסיון פתרון הבעיה.
בתרבות.
סרט הקולנוע "הסוכן הנוסע" ("Travelling Salesman)" מאת הבמאי טימותי לנזון הוא סיפור על ארבעה מתמטיקאים שנשכרו על ידי ממשלת ארצות הברית כדי לפתור את הבעיה הפתוחה במדעי המחשב: שאלת P=NP.
מיתולוגיה כנענית
המיתולוגיה הכנענית היא אוסף המיתוסים שהתפתחו על ידי העמים השונים באזור ארץ כנען. באמונות הכנענים ניכרת השפעה תרבותית מגוונת ויש דמיון רב בין סיפורי עמי כנען לבין סיפורים מהתנ"ך.
הכנענים.
ארץ כנען הייתה מקום מושבם של קבוצות אתניות שונות והיא השתרעה מעזה בדרום עד לאוגרית בצפון סוריה. העמים הכנעניים עסקו בחקלאות, דיג, מסחר, בנייה ופיסול. לכל קבוצה כנענית היו אלים משלה, לעיתים עבדו אלים זהים בעלי שם שונה ולעיתים עבדו אלים שונים לחלוטין. הם חיו בערי-מדינה שנשלטו על ידי מלכים. ייתכן כי שמם של הכנענים ושל ארצם נגזר מהמילה 'כִּנָעֻ' שמשמעותה בשפה החורית היא 'ארגמן' - צבע שאותו הפיקו מחלזונות ימיים ממשפחת הארגמונים, שהיו נפוצים בחופי הארץ. ישנה השקה תרבותית ניכרת בין תרבות כנען לבין התרבות המצרית העתיקה, זאת כיוון שהכנענים חיו שנים רבות תחת שלטון מצרי, כפי שעולה למשל ממכתבי אל עמארנה ומכתבים מצריים.
מקורות המידע על המיתולוגיה הכנענית.
כעל יתר עמי העולם העתיק, גם על עמי כנען למדים דרך חפירות ארכאולוגיות, ניתוח טקסטים והצלבות מידע בין מקורות שונים מהתקופה. מכל אלו מתברר שלכנענים היו חיי רוח מפותחים מאוד. הייתה להם הגמוניה כהנית, חכמי דת וסופרים והם ניהלו פולחן קבוע ומדוקדק.
סיפורי אלים רבים נכתבו, על מוצאם וקורותיהם, על תפקידם בפנתאון ויחסם אל בני האדם - אלו מהווים את המיתולוגיה הכנענית.
שרידים רבים ממיתולוגיה ענפה זו נמצאו בחפירות ארכאולוגיות שונות. דוגמה לכך הן הממצאים שנחשפו בחפירות העיר אוגרית ובחפירות כונתילת עג'רוד. בחפירות נמצאו יצירות רבות הכוללות ספרות פואטית וכתבי קודש שמהווים את המיתוס הכנעני. בין היצירות שנמצאו נמנים "עלילות בעל וענת", "אגדת כרת", "אגדת אקהת", "נישואי ניכל והירח" ועוד.
מקורות נוספים לחקר המיתוס הכנעני הם התנ"ך והספרים החיצוניים מימי בית שני, שיש בהם הדים למיתוסים כנעניים ולעיתים אף התייחסויות מפורטות לאלים שונים בתקופה הכנענית ודרכי עבודתם.
מקור נוסף הוא חיבורו של פילון מגבל, שכתב במאה הא' לפני הספירה, פילון מגבל ליקט את המיתוסים הכנענים ממקורות כתובים או בעל פה שהיו לפניו ולא שרדו עד זמננו.
המיתוסים הכנעניים.
הדת הכנענית היא דת טבע והדבר מתבטא בפסיכולוגיה שעומדת מאחורי המיתוסים של דת זאת. התנאים הגאוגרפיים של הארץ השפיעו מאוד על דמותם של האלים. רוב האלים הכנענים היו אנתרופורמורפיים (בדמות אדם) ומיעוטם כמו הכושרות אלות הפיריון הסנוניות היו אנימיסטיים (בדמות חיות). לעיתים אלים בדמות אדם יכלו להתחפש ולעטות על עצמם דמות חיה כמו האלה ענת שהופכת את עצמה לעוף דורס. ישנם אלים שיש להם תיאור קבוע כמו אל שמתואר כדמות אדם זקן היושב על כיסא מלכות בעל הדום, או בעל שמתואר כלוחם עומד כשבידו קרדום וברק.
בראש פנתאון האלים יושב 'אלו', או בשמו המוכר יותר 'אל'. אל, שהוא אל השמים, התחתן עם אשרה, אלת האדמה, ויחד הם הולידו את בעל, עשתורת, ענת, ים, מות ועוד מספר אלים, אלו הם שאר כוחות הטבע.