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