בתשובה לרן, 23/01/08 10:26
 |
|
 |
||
|
||||
 |
לרוב נהוג כשעוסקים בהיבטים תיאורטיים כמו P מול NP לדבר על גודל הייצוג של הקלט. לכן לא סופרים כמה רכבים והזמנות יש, אלא האם כמה מקום לוקח לייצג אותם (בדומה לצורה שבה פונקציות על מספרים נמדדות בסיבוכיות שלהם לא ביחס לגודל המספרים, אלא לגודל הייצוג שלהם, שהוא לוגריתמי בגודל המספר כשאנחנו בבסיס ספירה גדול מ-1). |  |
 |
 |
|
|
|
||
|
||||
|
למעשה אתה טוען שזה שקלול של השניים. זה בסדר, אין לי בעיה עם זה. ומה לגבי מהותו של עניין - לאיזו מחלקה הבעיה שייכת? |
|
|
|
|
|
|
||
|
||||
|
הבעיה שאתה מציג היא מסוג בעיית תזמון משאבים בגרף אינטרוולים. הבעיות האלה מעניינות בהקשר של P/NP כיוון ששינוי מאוד קטן בהגדרת הבעיה מעביר אותה מ- P ל- NPC. ספציפית נראה לי שהבעיה שאתה מתאר נמצאת ב- P אבל אני לא יודע להציג לה אלגוריתם ובפרט אני לא רואה אלגוריתם "סטנדרטי" שעובד בזמן ליניארי (אני חושב שצריך זמן ריבועי או משהו כזה). | |
|
|
|
|
|
||
|
||||
|
כמו שאמרו כאן, זו בעייה בסגנון "Interval Graph". אני לא מבין כלום בנושא, אבל אני מכיר מישהו שמבין ואשאל אותו. | |
|
|
|
|
|
||
|
||||
|
זה מאד יעזור, תודה. | |
|
|
|
|
|
||
|
||||
|
טוב, אין לי תשובה חד משמעית. בבירור זו בעיית צביעה של גרף אינטרוולים. הבעיה ה"כללית" (נתונה כמות צבעים מסויימת והשאלה היא האם את גרף האינטרוולים אפשר לצבוע באמצעותה כך שלא יהיו שני צמתים סמוכים בעלי אותו צבע) אפשר לפתור ביעילות בגלל התכונות הנחמדות של גרף האינטרוולים (משהו בסגנון "תמיד קיימת צומת שהשכנים שלה הם קליק"). אתה לעומת זאת מגביל את הצבעים שיכולים להיות בכל צומת, וזה ככל הנראה מקשה על הבעיה - אבל לא ברור אם עד לרמה של NP-שלמות. (אם הקשר לא ברור - "צבע" מתאים לרכב כלשהו; הצמתים בגרף מסמנים משימות; יש קשת בין שני צמתים אם ורק אם אלו משימות ש"עולות" אחת על השנייה; הצבעים החוקיים לצביעת צומת ספציפית הם צבעי כל הרכבים שהפרמטרים שלהם מתאימים למשימה שהצומת מייצגת). |
|
|
|
|
|
|
||
|
||||
|
טוב, גם לי אין תשובה חד משמעית... :-) כנראה שזה ישאר פתוח. היתה לי איזו תקווה שמישהו מהקוראים ירים את הכפפה, יקח את הבעיה ואת הפתרון ויוכיח משהו. לא נורא. אני אעשה עוד נסיון אחד, להעלות את הניסוח הפורמלי, הן של הבעיה והן של האלגוריתם, אולי זה יעיר מישהו. :-| רן. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |