בתשובה לeasy, 22/01/08 11:50
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
צודק, פספסתי את זה (דרישה הגיונית כשמדובר בהזמנת מכוניות...). ברור שהתכונה הזאת מקלה. אני אחשוב על הבעיה עם ההגבלה הזאת.

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

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