שיחת משתמש:Yaron1m/בעיית הסוכן הנוסע

הרחבת הערך

הרחבת ערך זה התבססה על תרגומו מוויקיפדיה האנגלית Yaron1m - שיחה 16:34, 23 בנובמבר 2015 (IST)

מקורות בעברית

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

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

המאמר הבא מזכיר את הבעיה ועובר לעסוק בבעיה הכללית:

• נעם ליבנה, על מוגבלותן של מכונות חישוב, באתר המרכז לטכנולוגיה חינוכית, פורסם במקור בגליליאו, ספטמבר 2005

המאמר הבא מזכיר את הנושא באגב בהקשר של מחשב קוונטי:

• משה נחמני, ‏נאס"א וגוגל מתכוונות להשתמש במעין מחשב קוונטי, באתר "הידען", 20 במאי 2013

ובקישור הזה מצאתי ציטוט רלוונטי מספרו של מריו ליביו, "האם אלוהים הוא מתמטיקאי?":

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

עיקרה הוא כדלקמן: אם סוכן מכירות - או פוליטיקאי במסע בחירות - צריך לעבור בין מספר נתון של ערים, ואם הוא מבקש לעשות זאת בדרך החסכונית ביותר, ואם ידועים דמי הנסיעה בין כל שתי ערים, כיצד יוכל הנוסע לחשב ולמצוא את הדרך הכי זולה לבקר בכל הערים הללו ולחזור לנקודת המוצא? בעיית הסוכן הנוסע נפתרה עבור 49 ערים בארצות הברית ב־1954, וב־2004 הוצג פתרונה עבור 24,978 ערים ועיירות בשוודיה. במילים אחרות, תעשיית האלקטרוניקה, החברות המנתבות משאיות להובלת חבילות ואפילו היצרנים היפנים של מכונות פָּצִ'ינקוֹ הדומות לפינבול (שיש בהן אלפי מסמרים) נאלצים להסתייע במתימטיקה בעניינים פשוטים כמו קידוח חורים, בניית לוחות זמנים לנסיעה או עיצובם הפיסי של מחשבים."

מקורות הזמינים בספריות בישראל אפשר למצוא פה ופה.

בברכה, ‏ Uziel302 • שיחה • אמצו ערך יתום! 20:46, 11 בנובמבר 2015 (IST)

תודה, עוזיאל! הערך הזה נכתב במסגרת קורס ויקיפדיה החדש באוני' ת"א, אך נשמח מאוד לקבל עזרה. בשלב ראשון הסטודנטים כותבים ערכים, אח"כ עושים ביקורת עמיתים אחד לשני ומתקנים את עבודתם בהקדם. אז צוות הקורס יעבור על העבודה. ניכר שיש לך עניין בנושא ונשמח להעזר בך בבדיקות. אם אכן כך, אנא הוסף את עצמך כבודק הערך הזה בדף הקורס על מנת שלא תהיה כפילות. :) בברכה, Shani - שיחה 12:42, 13 בנובמבר 2015 (IST)

עבודתך עד כה..

שלומות, ירון. לבקשתך העפתי מבט במה שעשית עד כה. ראשי הפרקים שבחרת נראים הגיוניים וזורמים באופן נכון. תחילת העבודה עצמה גם נראית טוב הדבר היחיד שלא הבנתי הוא פסקת הטיוטה למטה (מס' 8). בטוחני שיש לזה הסבר, אך היא כמובן לא יכולה להיות חלק ממבנה הערך הסופי. שים לב להערות החשובות של עוזיאל לגבי מקורות. כמו כן, לאחר הפרק "בתרבות", אנא הוסף את הפרקים הבאים: "ראו גם", "לקריאה נוספת", "קישורים חיצוניים" ו"הערות שוליים". אדבר על הכל בשיעור הקרוב. בהצלחה! Shani - שיחה 12:46, 13 בנובמבר 2015 (IST)

הערות

• ידועה גם בקיצור כ-TSP - Travelling Salesman Problem -> באנגלית: Travelling Salesman Problem ובראשי תיבות: TSP
• לא ברור לפי הערך אם הקירובים במיליוני ערים מגיעים ל-1% מהאופטימלי או ל-2-3%.
• בעברית לא מקובל להדגיש בכתב נטוי.
• מהו המסלול המסלול הקצר - מילה כפולה.
• כשמתרגמים מאנגלית לעברית יש להעדיף ניסוח עברי רהוט על פני היצמדות למקור. כך למשל הייתי מעדיף במקום זמן הריצה הגרוע ביותר - זמן הריצה הארוך ביותר.
• "קטגוריה NP-קשה" - לפי הערך NP (מחלקת סיבוכיות) נראה שהטרמינולוגיה היא מחלקת NP ו"קשה" היא לא קטגוריה או מחלקה נפרדת אלא אפיון של בעיה. ברמת הפתיח הייתי מעדיף ניסוח כזה: הבעיה נכללת במחלקת הסיבוכיות NP. על השאלה אם היא קשה או שלמה כדאי להרחיב בגוף הערך (כרגע מופיעים בערך שני המושגים ולא ברור מה היחס ביניהם). ‏ Uziel302 • שיחה • אמצו ערך יתום! 13:43, 13 בנובמבר 2015 (IST)

תודה רבה על הערותיך! מעריך זאת! Yaron1m - שיחה 19:17, 13 בנובמבר 2015 (IST)

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

רק כאשר הבעיה מוצגת כבעיית הכרעה (בהינתן האורך L, האם קיים מסלול קצר יותר מ-L) אני מבין למה אם נתון מסלול קצר יותר ניתן לבדוק בקלות אם הוא פיתרון. בעיני יש להבחין בין גרסאות שונות של השאלה. ‏ Uziel302 • שיחה • אמצו ערך יתום! 23:54, 13 בנובמבר 2015 (IST)

הערכת עמיתים

הייי ירון. קראתי את הערך שלך והתרשמתי מאוד. ראיתי שתרגמת את הערך מהוויקיפדיה האנגלית ועושה רושם שעשית עבודה נהדרת. פתיחת הערך ברורה לקורא שלא מתעסק בתחום זה. ישנו סדר כרונולוגי טוב רציף ומובן ומרגיש שהכתיבה היא אכן אובייקטיבית. למשתמש שקורא את הערך ישנה אפשרות לפתח את קריאתו ולהעשיר את ידעו מלבד קריאה שאינה דיגיטלית (לקריאה נוספת). הערכים מקושרים גם מוויקיפדיה וגם מקריאה חיצונית ברחבי הרשת בצורה טובה מכותרת ונגישה.--Tomervaturi - שיחה 19:20, 25 בנובמבר 2015 (IST)

תודה רבה על הערכתך! Yaron1m - שיחה 23:35, 25 בנובמבר 2015 (IST)

שלום Yaron1m, אני גם לומד מדעי המחשב ומאוד התרשמתי מהעבודה שעשית כאן! הערך חשוב ובסיסי בתחום שלנו ואני שמח שהשקעת כ"כ הרבה בהרחבה שלו, כי כעת סטודנטים כמונו יוכלו להבין אותו יותר טוב אחרי ששמעו עליו פעם ראשונה בהרצאה. יש לי הערה אחת קטנה, וזה שכשהזכרת מסלול המילטוני בפעם הראשונה, לא עשית ממנו קישור, ורק בפעם השנייה עשית זאת. אני חושב שהיה עדיף בסדר ההפוך (אם לא להשאיר את שניהם) כיוון שאני הייתי רוצה להבין מה זה כבר בפעם הראשונה שזה מופיע. כל הכבוד על העבודה, Turingstine - שיחה 11:46, 30 בנובמבר 2015 (IST)

תודה רבה על הערכתך! אתקן בהתאם Yaron1m - שיחה 16:48, 30 בנובמבר 2015 (IST)