stanford-oval/wikipedia huggingface dataset:
ג'יי סטריט
ועידות

באוקטובר 2009 ערך הארגון את הוועידה הארצית הראשונה שלו במלון "גראנד היאט" בוושינגטון, והשתתפו בה מעל 1,500 אנשים. שגריר ישראל, מייקל אורן, הוזמן לוועידה אך לא הגיע, בנימוק שהארגון פועל נגד האינטרסים של ממשלת נתניהו. נשיא המדינה שמעון פרס שלח ברכה לארגון לכבוד ועידתו הראשונה וציין לשבח את יוזמת ג'יי סטריט להקים ארגון למען שלום ישראלי-פלסטיני ושלום ישראלי-ערבי בכלל. יושבת ראש "קדימה", ציפי לבני, שלחה מכתב ברכה, ואת מפלגתה ייצגו יושב ראש מועצת קדימה חיים רמון וחברי הכנסת מאיר שטרית ושלמה מולא. על מכתב תמיכה לקראת הוועידה חתמו חברי כנסת מקדימה, העבודה ומרצ, יחד עם יוצאי מערכת הביטחון הישראלית. עוד השתתפו בוועידה חברי הכנסת קולט אביטל וניצן הורוביץ והשרים לשעבר עמי אילון, עמיר פרץ, יולי תמיר ושלמה בן-עמי. בוועידה נכחו חברי קונגרס אמריקאים ואישי ציבור יהודים ואמריקאים. הנאום המרכזי היה של ג'יימס ג'ונס, היועץ לביטחון לאומי של הנשיא ברק אובמה.
בפברואר 2011 ערך הארגון ועידה שנתית. ממשלת ישראל לא שלחה נציג רשמי לוועידה. חברי כנסת הכנסת שהשתתפו בוועידה הם: דניאל בן סימון (העבודה), יואל חסון (קדימה), שלמה מולא (קדימה), עמיר פרץ (העבודה) ונחמן שי (קדימה). עם המשתתפים בוועידה נמנו מוסטפא ברגותי, עז א-דין אבו אל-עייש, ורון פונדק. עוד הבהיר הארגון כי על פי אמונתו, דיון מהותי על סוגיות שונות הוא חיוני לתרבות הדיון בקהילה היהודית, זאת במיוחד כאשר הדיון נסב על מחלוקות יסודיות. הארגון מאמין – על פי הצהרתו – כי סגירת הדלת בפני שיח פתוח ורציני רק מרחיקה מהקהילה היהודית רבים מאלה שאותם היא שואפת לקרב, בראשם יהודים צעירים.
בוועידה השנתית השלישית, שנערכה במאי 2012, הופיעו לפני הוועידה הסופר עמוס עוז והפעילה החברתית סתיו שפיר, ואת ההרצאה המרכזית נשא ראש ממשלת ישראל לשעבר, אהוד אולמרט.
בוועידה השנתית שהתכנסה באוקטובר 2013 ייצגו את ישראל נציגים בולטים, ובהם שרת המשפטים ציפי לבני וחברי הכנסת צחי הנגבי, שלי יחימוביץ', מאיר שטרית ויצחק וקנין. את נשיא ארצות הברית ייצגו סגנו ג'ו ביידן ומנהיגת הדמוקרטים בבית הנבחרים, ננסי פלוסי. כנס זה הסתיים בהשקת "קמפיין 2" לקידום פתרון של שתי מדינות לשני עמים.
באפריל 2014 דחתה ועידת הנשיאים, ארגון הגג של הארגונים היהודיים בארצות הברית, את בקשת ג'יי סטריט להצטרף כחברה בוועידה. הטענה העיקרית של המתנגדים הייתה, שג'יי סטריט איננו שייך לקונצנזוס היהודי שם. האיחוד ליהדות רפורמית (URJ), המקיף לפי ההערכות יותר ממיליון יהודים ונחשב לגדול ביותר בארצות הברית, יצא בחריפות נגד ההחלטה למנוע את הצטרפות ג'יי סטריט. נשיאו, הרב ריק ג'ייקובס, הודיע שהאיגוד הרפורמי ישקול לפרוש מוועידת הנשיאים.
בוועידה השנתית שהתכנסה באוקטובר 2019 השתתפו חמשה מתמודדים בבחירות לנשיאות ארצות הברית 2020 מטעם המפלגה הדמוקרטית: פיט בוטיג'ג', איימי קלובשר, ג'וליאן קסטרו, מייקל בנט וברני סנדרס. במהלך הוועידה עלה נושא הסיוע האמריקאי לישראל. נשיא הארגון, ג'רמי בן עמי אמר כי "הממשל האמריקאי לא צריך יותר לספק "צ'ק פתוח" לישראל. חשוב שארצות הברית תבחן לעומק את השאלה אם הכסף שלנו צריך ללכת לפעילויות שהופכות את פתרון שתי המדינות לבלתי אפשרי".
מימון

תקציב התנועה לשנת 2009 היה כ-1.5 מיליון דולר (לצורך השוואה, תקציב איפא"ק עומד על כ-100 מיליון דולר). שליש מהתקציב נתרם על ידי ג'ורג' סורוס ושני ילדיו. בשנת תקציב העמותה עלה ל-1.8 מיליון דולר לתפעול הארגון ו-1.3 מיליון דולר למימון קרן החינוך שלו. ועדת הכספים שלו כוללת כ-120 חברים, שכל אחד מהם תרם לפחות 10,000 דולרים. במועצת הנשיאות חברים 46 תורמים שתרמו לפחות 25,000 דולרים לכל תורם. ברשימת התורמים ישנם עשרות מוסלמים ואמריקאים שפעלו בשירות גופים ערביים בארצות הברית, דבר נדיר בארגונים פרו-ישראליים. ג'רמי בן עמי הסביר את הדבר ברצון לכלול בין תומכי הארגון גם לא-יהודים.
ביקורת

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

איפא"ק
יהדות ארצות הברית
מרי קייט ואשלי אולסן

| --- | --- |

אשלי (משמאל) ומרי קייט (מימין), 2011
 לידה:  13 ביוני 1986 (גיל: 38)
 סוגה מועדפת:  מוזיקת פופ 
 תקופת הפעילות:  מ-1987
 פרסים והוקרה:  כוכב בשדרת הכוכבים בהוליווד 
 
מרי־קייט ואשלי אולסן (באנגלית: Mary-Kate and Ashley Olsen; נולדו ב-13 ביוני 1986), או "התאומות אולסן", הן זוג שחקניות ומעצבות אופנה אמריקאיות. התפרסמו כשחקניות ילדות בסדרה "צער גידול בנות". אחותן הצעירה היא השחקנית אליזבת אולסן.
ביוגרפיה

האחיות נולדו בלוס אנג'לס, קליפורניה שבארצות הברית. הוריהן הם דייב וג'רני אולסן. להן אח גדול בשם טרנט אולסן, ואחותן הקטנה היא השחקנית אליזבת אולסן.
בגיל שבעה חודשים התקבלו לתפקיד התינוקת מישל טאנר בסיטקום הטלוויזיוני "צער גידול בנות", ששודרה מספטמבר 1987 עד מאי 1995 ברשת ABC. ב-1995 התגרשו הוריהן של התאומות. לאחר צילומי הסדרה, שיחקו האחיות בסרטי טלוויזיה וקולנוע והשיקו קו מוצרים על שמן, הכולל בין השאר בגדים, אביזרים, תחליבי רחצה, מוצרים לבית הספר, ספרים, סרטים, בשמים, משחקי מחשב, בובות ואף סדרת טלוויזיה מצוירת. בשנת 2004 זכו לכוכב בשדרת הכוכבים של הוליווד ובאותה שנה החלו לימודי תואר ראשון באוניברסיטת ניו יורק.
מקצוע הלימודים הראשי אותו לומדת אשלי הוא פסיכולוגיה, ואילו מרי קייט לומדת צילום.
האחיות אולסן זכו לביקורת קשה מצד ארגון זכויות בעלי חיים, PETA, לאחר שהשתמשו בפרווה בקו האופנה שלהן, "The Row".
מרי קייט שיחקה בעונה השלישית של הסדרה "העשב של השכן".
פילמוגרפיה

צער גידול בנות (1987–1995)
יופי של צרות (1993)
חבורת השובבים (1994)
איך שהמערב היה כיף (1994)
מותק, הילדות התחלפו (1995)
דרכון לפריז (1999)
גול כפול (1999)
שפתינו חתומות (2000)
לונדון המנצחת (2001)
מרי קייט ואשלי בפעולה! (2001)
חופשה בשמש (2001)
להגיע לשם (2002)
להתאהב ברומא (2002)
שגעון של הישרדות (2003)
המלאכיות של צ'רלי: בהילוך גבוה (2003) (אורחות)
יום בניו יורק (2004)
השיגעון (2008) (מרי קייט)
ביסטלי (2011) (מרי קייט)
ג'יימס יוברט פרייס

ג'יימס יוברט פרייס (באנגלית: James Hubert Price;‏ 7 בספטמבר 1878 –  22 בנובמבר 1943) היה פוליטיקאי אמריקאי מווירג'יניה, איש המפלגה הדמוקרטית, שכיהן כחבר בית הנבחרים של וירג'יניה בשנים 1916–1930, לאחר מכן ועד 1938 כסגן מושל המדינה, ולאחר מכן ועד 1942 כמושל וירג'יניה ה-53.
כהונתו של פרייס כמושל אירעה במהלך השפל הגדול והוא נודע בווירג'יניה כ"מושל הניו דיל". לנוכח התנגדותו של המנגנון הפוליטי של הארי פ. בירד, פרייס, שהיה עורך דין ואיש עסקים, העביר תוכניות חברתיות רבות ויישם תוכניות רווחה פדרליות עבור תושבי וירג'יניה.
ראשית חייו

ג'יימס יוברט פרייס נולד במחוז גרינברייר שבווירג'יניה המערבית, כבנם של צ'ארלס ויליאם פרייס ושל ננסי סי. בון, שניהם מלואיסבורג שבווירג'יניה המערבית. המשפחה עברה לסטאונטון שבווירג'יניה, שם פרייס גדל, ושם חיו גם קרובי משפחתו בתקופה בה פרצה מלחמת העולם הראשונה. פרייס למד בקולג' לעסקים דנסמור וקיבל תואר בעסקים ב-1898. לאחר מכן הוא לימד חשבונאות בקולג' והקים משרד משלו לחשבונאות. ב-1907 הוא החל ללמוד משפטים בבית הספר למשפטים של אוניברסיטת וושינגטון ולי, שם סיים ב-1909.
באוקטובר 1918, כשהיה בן 37, כחודש לאחר שנרשם לגיוס לצבא, והיה יועץ משפטי של מועצות הגיוס המקומיות, נשא פרייס לאישה את ליליאן מרטין, ולשניים נולדו בן ובת. פרייס היה פעיל מאוד בבונים החופשיים ובין שאר שימש בשנים 1922–1924 כנשיא הגדול של הלשכה הגדולה של וירג'יניה.
עם קבלתו ללשכת עורכי הדין של וירג'יניה, פתח פרייס משרד עורכי דין בסטאונטון, אך עד מהרה עבר ב-1910 לריצ'מונד, שם הוא עסק בעריכת דין בדיני תאגידים.
מחוקק בווירג'יניה

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

ב-1929 נבחר פרייס כסגן מושל וירג'יניה ה-23 לאחר שגבר בבחירות על מועמד המפלגה הרפובליקנית קאלום ב. ג'ונס בהפרש של 64 מול 36 אחוזים מקולות הבוחרים. עם תחילת השפל הגדול ראה פרייס עד מהרה שהמושל ג'ון גרלנד פולארד, שהיה חבר במנגנון הפוליטי של המפלגה הדמוקרטית בראשותו של הארי פ. בירד, קיצץ בשכר עובדי המדינה במקום לנצל את ההזדמנויות שהתגלמו בתוכניות של הנשיא פרנקלין דלאנו רוזוולט, זאת על אף שהיה חבר מפלגתו.
ב-1933 לא עלה בידו של פרייס לזכות בתמיכתו של בירד להתמודדות על משרת המושל. תחת זאת בחר בירד לתמוך במועמדותו של חבר בית הנבחרים של ארצות הברית לשעבר ג'ורג' פירי, שהסכים עם מדיניות "שלם כשאתה עובר" (pay as you go) של בירד. בבחירות אלו נבחר פרייס לתקופת כהונה שנייה כסגן המושל לאחר שגבר על מועמד הרפובליקנים ג'. פאוול רויאול ועל המועמד הסוציאליסט ג'. לותר קיבלר וזכה ב-75.73 אחוזים מקולות הבוחרים.
מושל וירג'יניה

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

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

Sobel, Robert, and John Raimo, eds. Biographical Directory of the Governors of the United States, 1789–1978, Vol. 4, Westport, Conn.; Meckler Books, 1978, pp. 1662-1663
בעיית הסוכן הנוסע

ערך זה עוסק בבעיה בתורת הגרפים. אם התכוונתם לדילמה במדעי החברה ובניהול, ראו .
בעיית הסוכן הנוסע – מסלולים קצרים
בעיית הסוכן הנוסע (באנגלית: Travelling Salesman Problem ובראשי תיבות: TSP) היא בעיה ידועה בתורת הגרפים ובתורת הסיבוכיות, המעלה את השאלה הבאה: "בהינתן רשימת ערים והמרחק בין כל שתי ערים, מהו המסלול הקצר ביותר, אשר יעבור בכל עיר פעם אחת, ויחזור לעיר ממנה התחיל?"
הבעיה נכללת במחלקת הסיבוכיות NP-קשיות, והיא אחת מהבעיות המרכזיות בתחום האופטימיזציה.
היסטוריה

מקורות הבעיה לא ברורים. מדריך לסוכן הנוסע משנת 1832 מזכיר את הבעיה ומכיל דוגמאות למסלולים בגרמניה ושווייץ, אבל לא מכיל התייחסות מתמטית לנושא.
בעיית הסוכן הנוסע נוסחה לראשונה במאה ה-19 על ידי המתמטיקאי האירי ויליאם רואן המילטון והמתמטיקאי הבריטי תומאס קירקמן (אנ'). המילטון פיתח בשנת 1857 את "משחק איקוסיאן" (אנ') שמטרתו הייתה למצוא מסלול המילטוני שיעבור בכל הקודקודים של דודקהדרון בדיוק פעם אחת ויחזור לנקודת ההתחלה.
הצורה הכללית של בעיית הסוכן הנוסע נחקרה לראשונה על ידי מתמטיקאים בשנת 1930, בפרט על ידי קרל מנגר שהגדיר את הבעיה והתייחס לפתרונות כוח גס ושיטת השכן הקרוב:
מבעיית השליחים (כיוון שבפועל הבעיה צריכה להיפתר על ידי כל דוור, וגם על ידי הרבה טיילים) אנו שמים לב למשימה למצוא למספר סופי של נקודות, שהמרחק בין כל צמד ידוע, את המסלול הקצר ביותר שיחבר את כל הנקודות. הבעיה פתירה מכך שיש מספר סופי של מסלולים. חוקים שיורידו את מספר המסלולים מתחת למספר התמורות אינם ידועים. השיטה בה יש ללכת מנקודת ההתחלה לנקודה הקרובה ביותר, ואז לקרובה ביותר אליה וכדומה, בכלליות לא מפיקה את המסלול הקצר ביותר.
בשנות ה-50 וה-60 של המאה ה-20 הבעיה הפכה פופולרית באירופה וארצות הברית לאחר שתאגיד ראנד מסנטה מוניקה הציע פרסים על מציאת שלבים בפתרון הבעיה. בשנות ה-60 התפתחה גישה חדשה – במקום לחפש את הפתרון האופטימלי, החלו אנשים לחפש את הפתרון הגרוע ביותר ובכך למצוא חסם עליון לבעיה. בעשורים שלאחר מכן נחקרה הבעיה על ידי מתמטיקאים, חוקרי מדעי המחשב, פיזיקאים ומדענים אחרים.
בשנת 1972 ריצ'רד קארפ הראה שמסלול המילטון היא בעיה השייכת לקטגוריה NP-שלמה, ובכך סיפק הסבר מתמטי לקושי החישובי במציאת מסלול אופטימלי.
בשנת 1991 פרסם ג'רארד ריינלט ספרייה בשם TSPLIB שכללה אוסף של רשימות ערים לדוגמה בדרגות קושי שונות. חוקרים רבים עשו שימוש נרחב בספרייה, ובשנת 2006 ויליאם ג'ון קוק (אנ') וחוקרים נוספים חישבו מסלול אופטימלי שעבר ב-85,900 נקודות, נכון להיום החישוב הגדול ביותר מתוך TSPLIB. ספריה זו מתוחזקת לצורך בדיקת אלגוריתמים לפתרון הבעיה.
מאפיינים > הצגה כבעיית גרפים

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

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

בעיה זו נכללת בקטגוריה NP-קשה, והצגתה כבעיית הכרעה (בהינתן האורך X, קבע האם קיים מסלול שאורכו קטן מ-X) שייכת לקטגוריה NP-שלמה. לכן, אם מניחים ש-P שונה מ-NP, זמן הריצה הגרוע ביותר של כל אלגוריתם לפתרון הבעיה יהיה יותר מפולינומי כתלות בקלט (מספר הערים).
מאפיינים > מאפיינים נוספים

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

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

פתרון פשוט לבעיה הוא בדיקת כל התמורות האפשריות וחיפוש המסלול הקצר ביותר (תוך שימוש בכוח גס). פתרון זה מצריך בדיקה של  n! אפשרויות (עצרת של מספר הערים), ולכן סיבוכיות זמן הריצה במקרה כזה תהיה  O(n!). חישוב כזה הופך מהר מאוד לבלתי מעשי (לבלתי יעיל, במינוח של מדעי המחשב). דוגמה להמחשת הבעיה: אם ישנן 70 ערים בהן על הסוכן לבקר, יצטרך הסוכן לבחון  70! מסלולי נסיעה אפשריים, אשר מהווים מספר רב יותר ממספר האטומים ביקום כולו.
בשנת 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.
ראו גם

NP (מחלקת סיבוכיות)
בעיית הדוור הסיני
הגשרים של קניגסברג
VRP (בעיית ניתוב רכבים)
הערות שוליים

↑  "הסוכן הנוסע — איך הוא צריך להיות ומה הוא צריך לעשות כדי לקבל עמלה ולהיות בטוח בהצלחת עסקיו" מאת סוכן מכירות לא ידוע (מגרמנית - "Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur")
↑  מגרמנית: "Wir bezeichnen als Botenproblem (weil diese Frage in der Praxis von jedem Postboten, übrigens auch von vielen Reisenden zu lösen ist) die Aufgabe, für endlich viele Punkte, deren paarweise Abstände bekannt sind, den kürzesten die Punkte verbindenden Weg zu finden. Dieses Problem ist natürlich stets durch endlich viele Versuche lösbar. Regeln, welche die Anzahl der Versuche unter die Anzahl der Permutationen der gegebenen Punkte herunterdrücken würden, sind nicht bekannt. Die Regel, man solle vom Ausgangspunkt erst zum nächstgelegenen Punkt, dann zu dem diesem nächstgelegenen Punkt gehen usw., liefert im allgemeinen nicht den kürzesten Weg."
↑  הטיול האופטימלי בשוודיה (אנגלית), ‏2004
↑  Rego, César; Gamboa, Dorabela; Glover, Fred; Osterman, Colin, "Traveling salesman problem heuristics: leading methods, implementations and latest advances", European Journal of Operational Research 211 (3): 427–441, 2011
↑  Johnson, D.S. and McGeoch, L.A., The traveling salesman problem: A case study in local optimization, Local search in combinatorial optimization, 1997
↑  Macgregor, J. N.; Ormerod, T. (June 1996), "Human performance on the traveling salesman problem", Perception & Psychophysics 58 (4): 527–539, doi:10.3758/BF03213088
↑  James N. MacGregor, Yun Chu, סקירת ביצועים אנושיים בבעיית הסוכן הנוסע ובעיות קשורות (מאנגלית - Human Performance on the Traveling Salesman and
Related Problems: A Review), The Journal of Problem Solving כרך 3, חורף 2011
↑  DUNCAN GEERE, 'Travelling Salesman' movie considers the repercussions if P equals NP (Wired UK), Wired, ‏26/04/2012
| --- | --- |
בקרת זהויות :  NLI: 987007568164305171  GND: 4185966-2  LCCN: sh85137179 
ויליאם רואן המילטון
בעיית הסוכן הנוסע סימטרית עם 4 ערים
פתרון בעיה סימטרית עם 7 ערים. משמאל – האפשרות הנבדקת. מימין – האפשרות הטובה ביותר עד כה. מספר האפשרויות – 360=2/!(7-1)
דוגמה לאלגוריתם השכן הקרוב. הפתרונות משתנים לפי נקודת המוצא
אלפרד מרשל

אלפרד מרשל
אלפרד מרשל (באנגלית: Alfred Marshall‏; 26 ביולי 1842 – 13 ביולי 1924), כלכלן בריטי, אחד הכלכלנים רבי ההשפעה של בני זמנו. בספרו "עקרונות הכלכלה" הציג את רעיונותיו בענייני היצע וביקוש, תועלת שולית ועלות ייצור. ספר זה הפך לספר לימוד דומיננטי למשך זמן רב בתחום הכלכלה.
תרומות תאורטיות

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

↑  Buchholz, Todd G. 1989. New Ideas from Dead Economists. New York: Penguin Group. p. 151
| --- | --- |
בקרת זהויות :  NLI: 987007274276705171  PLWABN: 9810584883005606  BIBSYS: 90544121  BNE: XX1018004  BnF: cb12278419p (data)  CANTIC: a11070675  CiNii: DA00585006  GND: 118782126  ICCU: RAVV030763  ISNI: 0000 0001 0866 8978  LCCN: n50040963  LNB: 000050900  NDL: 00448925  NKC: mzk2005272975  NLA: 35329656  NLK: KAC200100771  NSK: 000030519  NTA: 069072310  RERO: 02-A003564681  SELIBR: 250069  SNAC: w6b868ns  SUDOC: 031601049  Trove: 913801  ULAN: 500241539  VcBA: 495/350228  VIAF: 7451112   WorldCat (עם VIAF): 7451112 
Elements of economics of industry, 1892
אבלה נפשי וחשך תארי

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

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