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