בתשובה לדורפל, 22/01/08 12:14
 |
|
 |
||
|
||||
 |
נדמה לי שהבעיה נקראת staff scheduling ונהוג לפתור אותה עם integer programming. |  |
 |
 |
|
|
|
||
|
||||
|
http://en.wikipedia.org/wiki/Linear_programming#Inte... היא בכלל בעיה NP קשה (כך שלא ממש נהוג לפתור אותה). | |
|
|
|
|
|
||
|
||||
|
מה זאת אומרת "לא ממש נהוג לפתור אותה"? | |
|
|
|
|
|
||
|
||||
|
לבעיות שמצריכות תכנון בשלמים, במקרה הכללי, אין פתרון ישים. | |
|
|
|
|
|
||
|
||||
|
מה זאת אומרת אין פיתרון ישים? ברור שיש פיתרונות, רק שלא תמיד הם אופטימליים. | |
|
|
|
|
|
||
|
||||
|
נדמה לי, ותקן אותי אם אני טועה, שהבעיה שהוצגה כאן היא בעיית אופטימיזציה. | |
|
|
|
|
|
||
|
||||
|
אכן. לבעיות אופטימיזציה שהן NP-קשות נהוג למצוא פתרונות מקורבים. יש תחום מחקרי שלם (ומרתק) על "עד כמה טוב אפשר לקרב בעיה מסויימת בלי לקבל ש-P=NP". מסתבר שבעיות NP-שלמות נבדלות זו מזו באופן דרסטי במידת הקירוב האפשרית שלהן. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |