 |
|
 |
||
|
||||
 |
טוב, אין לי תשובה חד משמעית. בבירור זו בעיית צביעה של גרף אינטרוולים. הבעיה ה"כללית" (נתונה כמות צבעים מסויימת והשאלה היא האם את גרף האינטרוולים אפשר לצבוע באמצעותה כך שלא יהיו שני צמתים סמוכים בעלי אותו צבע) אפשר לפתור ביעילות בגלל התכונות הנחמדות של גרף האינטרוולים (משהו בסגנון "תמיד קיימת צומת שהשכנים שלה הם קליק"). אתה לעומת זאת מגביל את הצבעים שיכולים להיות בכל צומת, וזה ככל הנראה מקשה על הבעיה - אבל לא ברור אם עד לרמה של NP-שלמות. (אם הקשר לא ברור - "צבע" מתאים לרכב כלשהו; הצמתים בגרף מסמנים משימות; יש קשת בין שני צמתים אם ורק אם אלו משימות ש"עולות" אחת על השנייה; הצבעים החוקיים לצביעת צומת ספציפית הם צבעי כל הרכבים שהפרמטרים שלהם מתאימים למשימה שהצומת מייצגת). |
 |
 |
 |
|
|
|
||
|
||||
|
טוב, גם לי אין תשובה חד משמעית... :-) כנראה שזה ישאר פתוח. היתה לי איזו תקווה שמישהו מהקוראים ירים את הכפפה, יקח את הבעיה ואת הפתרון ויוכיח משהו. לא נורא. אני אעשה עוד נסיון אחד, להעלות את הניסוח הפורמלי, הן של הבעיה והן של האלגוריתם, אולי זה יעיר מישהו. :-| רן. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |