בשער-קהילה אקדמית למען החברה בישראל בשער בפייסבוק - קהילה אקדמית למען החברה בישראל בשער - קהילה אקדמית למען החברה בישראל בשער - קהילה אקדמית למען החברה בישראל
דף הבית   |   על בשער   |   פעילויות בשער   |   ספר אורחים   |   צור קשר      רשימת תפוצה
 
 
 > שלח שאלה למומחה
 
 
 
     כל התחומים
     
     
     
     
     
     אסטרופיזיקה
     הנדסת חשמל
     הנדסת מזון
     כימיה
     פרקינסון
     קרקע ומים
     ננוטכנולוגיה
     הנדסה
     מדעי המחשב
     כימיה
     ביולוגיה
     פיזיקה
     רפואה
     מתמטיקה
     מדעי הסביבה
     גיאוגרפיה
     מוט"ב
     הוראת המדעים
     אזרחות
     כלכלה
     היסטוריה
     משפטים
     פסיכולוגיה
     תנ"ך
 
 
 
 
 
 
 
 
 
 
 > בשער האזרחות
 
 
 > הרצאות מומחים ברשת
 
 
 > רשימת תפוצה
 
 > חתום בספר האורחים
 
 > כניסה לשואלים רשומים
 
 
 > English
 
שאלה מספר 3433 - מודל לינארי לבעיית הסוכן הנוסע תאריך: 04/04/2008
תחומי דעת:  מדעי המחשב  , מתמטיקה  

האם קיים מודל תכנות בשלמים לבעיית הסוכן הנוסע שגודלו (מספר המשתנים + המשוואות + אברים שונים מאפס במטריצה) פרופורציוני לגודל הקלט


תשובה מאת: פרופ' נתן ליניאל
   

שלום רב,

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

Lawler, Lenstra, Rinnooy Kan, Shmoys

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

בברכה,

פרופ' נתן ליניאל
ביה"ס להנדסה ומדעי המחשב
האוניברסיטה העברית

הוסף תגובה הדפס שאלה      שלח לחבר      שאלות מועדפות
שלח שאלה למומחה   |   שמור כדף הבית   |   הוסף למועדפים   |   תנאי שימוש באתר   |   Powered By Art-Up