בתשובה לגדי אלכסנדרוביץ', 22/01/08 8:57
NP שלמה + פתרון לינארי 468939
אני כתבתי תאור ארוך של בעיית סידור ההזמנות, חשבתי שתראה את התגובה ההיא לפני זאת ולכן כבר התיחסתי אליה כאל בעיה שאתה מכיר... תיכף אני אתאר אותה שוב. משום מה היא לא עלתה למערכת (תגיד, צריך ללחוץ על "אישור"? :-))

מלבד זאת, אני לא תוקף את P=NP אני רק רוצה לשייך את בעיית סידור ההזמנות למחלקה הנכונה. בשלב ראשון זה מה שאני לא יודע. אח"כ כבר יהיה יותר קל: אם היא שייכת ל P אזי נוכל להניח שהאלגורתם שמסדר הוא נכון תמיד. אם הבעיה שייכת ל NP אזי נצטרך לעבוד קצת יותר קשה ולהראות שיש לפחות קלט אחד שעבורו האלגוריתם רץ בזמן לא סביר.

להלן (שוב) תיאור הבעיה:

נתון צי רכבים N. לכל רכב בצי יש מספר תכונות המאפיינות אותו: מספר מקומות, סוג הילוכים, רשיון נדרש, צבע וכד'.

נתונה רשימת הזמנות R. כל הזמנה מכילה:
1. מאיזו שעה ועד איזו שעה הרכב נדרש.
2. מאפיינים של הרכב הנדרש. הרשימה יכולה להיות ריקה, כלומר כל רכב מתאים.

השאלה: האם קיים סידור ל R ב N? או בגרסה המלאה: מהו הסידור של R ב N?

כל מי שהיה פעם חבר קיבוץ מכיר את הבעיה.

יש לי גם תאור פורמלי יותר של הבעיה, יותר מאוחר אני אעלה אותו.
NP שלמה + פתרון לינארי 468949
בלי לחשוב על הבעיה יותר מדי, היא נראית לי הרחבה של http://en.wikipedia.org/wiki/Knapsack_problem שהיא בעיה NP שלמה.
NP שלמה + פתרון לינארי 468960
במבט חטוף, אני לא מצליח להבין אם יש קשר בין שתי הבעיות. אולי, אם כל פריט הוא הזמנה: משקלו הוא השעות וערכו הוא התיקים אליהם הוא יכול להכנס?... לא נשמע טוב, צריך לבדוק. ודווקא הרחבה יכולה ליצור הקלה בתנאים ולהפוך את הבעיה לפשוטה יותר....
NP שלמה + פתרון לינארי 469122
הנה תיאור של רדוקציה מבעיה דמוית-תרמיל לבעית סידור ההזמנות.

הבעיה (דמוית התרמיל): נתונות n משקולות, במשקל כולל N, וצריך למצוא תת קבוצה שלהן כך שסכום המשקולות בתת הקבוצה הוא *בדיוק* K. בנוסף אני דורש ש- 2K>N.

רדוקציה: בצי הרכבים יש שני רכבים, 1 ו- 2. אורך ה"יממה" הוא K שעות. כל משקולת הופכת להזמנה של רכב למספר שעות השווה לגודל המשקולת, כאשר ההזמנה היא לרכב 1 או לרכב 2. בנוסף, יש הזמנה של 2K-N שעות לרכב 2 בלבד. סכום השעות בכל ההזמנות הוא בדיוק 2K, וכך גם סכום השעות הזמינות. לכן אם יש פתרון, הוא יהיה חייב לקיים שסכום ההזמנות של רכב 1 הוא בדיוק K, כנדרש.

עכשיו, כדי לצמצם את "הפער" בין הבעיה דמוית התרמיל שהצגתי לבין בעית התרמיל המקורית ניתן לפעול בשתי דרכים: או למצוא רדוקציה מבעית התרמיל לבעיה דמוית התרמיל, או לפתח את הרדוקציה הזאת כך שתפתור בעיה יותר כללית. הנה כמה מחשבות על הדרך השניה:

הדרישה ש- 2K>N היא דרישה טכנית, שלדעתי אפשר להיפטר ממנה. מה שבטוח הוא שבאופן טריביאלי אפשר לשים כל קבוע אחר במקום ה- 2.

לגבי העובדה שאנחנו מוצאים פתרון רק אם הסכום הוא בדיוק K - את זה אפשר היה לפתור אילו בבעית ההזמנות היתה איזושהי "עדיפות" (כלומר, כל כותב הזמנה היה כותב באיזה עדיפות הוא רוצה אילו רכבים, והיינו יכולים להכניס garbage collector נוסף - רכב 3 - שהיה אוסף את כל מי שלא קיבל את הזמנתו). זה גם היה מאפשר להכניס פנימה את עניין הערך לעומת גודל המשקולת לדעתי (אם כי לפי זכרוני המעומעם כבר יש רדוקציה לבעיה שבה הערך הוא המשקולת).

זאת בקצרה ובלי לחשוב יותר מדי, והתחושה שלי (בדומה ל- easy) היא שעם נעבוד קצת יותר נגיע לרדוקציה.
NP שלמה + פתרון לינארי 469127
שים לב שכחלק מההזמנה צריך לציין מאיזו שעה עד איזו שעה הרכב נדרש. התכונה הזו מקלה מכיוון שהיא מורידה באופן משמעותי את דרגות החופש של הפתרון.
NP שלמה + פתרון לינארי 469128
מצד אחד היא מקלה כי היא מצמצמת את החופש אך מצד שני היא מקשה על האלגוריתם למצוא סידור. חופש בהזזת עשות ההזמנה היה מקל על האלגוריתם, ויתכן אפילו שאחד חמדן היה מוצא פתרון טוב.

אגב,
האלגוריתם הנאיבי שפותר את הבעיה הוא:
1. כל עוד אין התנגשות שבץ את ההזמנה הנוכחית במקום שמתאים לה.
2. אם אין מקום להזמנה הנוכחית, חזור להזמנה הקודמת ומקם אותה במקום אחר שמתאים לה ושהיא עוד לא היתה בו אף פעם.
3. חזור ל 1.

נאיבי, אקספוננציאלי אבל עובד.
NP שלמה + פתרון לינארי 469143
צודק, פספסתי את זה (דרישה הגיונית כשמדובר בהזמנת מכוניות...). ברור שהתכונה הזאת מקלה. אני אחשוב על הבעיה עם ההגבלה הזאת.
NP שלמה + פתרון לינארי 468956
הערה טכנית: אלגוריתם דטרמיניסטי לא "עובד תמיד נכון", הוא או עובד נכון (תמיד), או לא נכון (מספיק שבמקרה אחד).

עוד הערה טכנית: את הבעיה לא הסברת "שוב", הסברת אותה לראשונה. אם אתה מתכתב בנושא בכמה פורומים, מן הנימוס שתזכור עם מי דיברת על מה, או לפחות לא תנזוף באף אחד על שכחה.
NP שלמה + פתרון לינארי 468957
הוא הסביר אותה "שוב", בפעם הראשונה "משום מה היא לא עלתה למערכת" תגובה 468939 (אם אתה נוזף באחרים כדאי שתבדוק שאתה לא נוזף בהם בטעות).
NP שלמה + פתרון לינארי 468958
לא הבנתי שכשהוא אומר שהוא ''תיכף יתאר אותה שוב'', הוא מתכוון באותה הודעה ממש. חשבתי שהוא מתכוון עוד שעתיים, כשיגיע זמן הפסקת הצהריים. תודה על התיקון, וסליחה לרן.
NP שלמה + פתרון לינארי 469103
עוד לא העליתי את התאור הפורמלי של בעיית סידור ההזמנות, פשוט זה בבית ועוד לא היה לי את הפנאי.
אם זה ידרבן מישהו מהקוראים להתעסק עם זה, אני אעלה גם את האלגוריתם.

שאלה: מה המשתנה, n, שעליו ניתן לומר שהאלגוריתם עובד ב O כלשהו של n? האם זה צי הרכבים N, האם מספר ההזמנות R?

ועוד שאלה: האם טווח השעות בבעיה משנה לשייכותה למחלקה זו או אחרת? כלומר, אם הזמן בו ניתן לבקש רכב הוא סופי, למשל 24 שעות. או אם הזמן הוא לאינסוף.
NP שלמה + פתרון לינארי 469106
לרוב נהוג כשעוסקים בהיבטים תיאורטיים כמו P מול NP לדבר על גודל הייצוג של הקלט. לכן לא סופרים כמה רכבים והזמנות יש, אלא האם כמה מקום לוקח לייצג אותם (בדומה לצורה שבה פונקציות על מספרים נמדדות בסיבוכיות שלהם לא ביחס לגודל המספרים, אלא לגודל הייצוג שלהם, שהוא לוגריתמי בגודל המספר כשאנחנו בבסיס ספירה גדול מ-‏1).
NP שלמה + פתרון לינארי 469108
למעשה אתה טוען שזה שקלול של השניים. זה בסדר, אין לי בעיה עם זה.

ומה לגבי מהותו של עניין - לאיזו מחלקה הבעיה שייכת?
NP שלמה + פתרון לינארי 469118
הבעיה שאתה מציג היא מסוג בעיית תזמון משאבים בגרף אינטרוולים. הבעיות האלה מעניינות בהקשר של P/NP כיוון ששינוי מאוד קטן בהגדרת הבעיה מעביר אותה מ- P ל- NPC. ספציפית נראה לי שהבעיה שאתה מתאר נמצאת ב- P אבל אני לא יודע להציג לה אלגוריתם ובפרט אני לא רואה אלגוריתם "סטנדרטי" שעובד בזמן ליניארי (אני חושב שצריך זמן ריבועי או משהו כזה).
NP שלמה + פתרון לינארי 469149
כמו שאמרו כאן, זו בעייה בסגנון "Interval Graph". אני לא מבין כלום בנושא, אבל אני מכיר מישהו שמבין ואשאל אותו.
NP שלמה + פתרון לינארי 469152
זה מאד יעזור, תודה.
NP שלמה + פתרון לינארי 469230
טוב, אין לי תשובה חד משמעית. בבירור זו בעיית צביעה של גרף אינטרוולים. הבעיה ה"כללית" (נתונה כמות צבעים מסויימת והשאלה היא האם את גרף האינטרוולים אפשר לצבוע באמצעותה כך שלא יהיו שני צמתים סמוכים בעלי אותו צבע) אפשר לפתור ביעילות בגלל התכונות הנחמדות של גרף האינטרוולים (משהו בסגנון "תמיד קיימת צומת שהשכנים שלה הם קליק"). אתה לעומת זאת מגביל את הצבעים שיכולים להיות בכל צומת, וזה ככל הנראה מקשה על הבעיה - אבל לא ברור אם עד לרמה של NP-שלמות.

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

:-|

רן.

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים