בתשובה לeasy, 22/01/08 11:50
 |
|
 |
||
|
||||
 |
במבט חטוף, אני לא מצליח להבין אם יש קשר בין שתי הבעיות. אולי, אם כל פריט הוא הזמנה: משקלו הוא השעות וערכו הוא התיקים אליהם הוא יכול להכנס?... לא נשמע טוב, צריך לבדוק. ודווקא הרחבה יכולה ליצור הקלה בתנאים ולהפוך את הבעיה לפשוטה יותר.... |  |
 |
 |
|
|
|
||
|
||||
|
הנה תיאור של רדוקציה מבעיה דמוית-תרמיל לבעית סידור ההזמנות. הבעיה (דמוית התרמיל): נתונות n משקולות, במשקל כולל N, וצריך למצוא תת קבוצה שלהן כך שסכום המשקולות בתת הקבוצה הוא *בדיוק* K. בנוסף אני דורש ש- 2K>N. רדוקציה: בצי הרכבים יש שני רכבים, 1 ו- 2. אורך ה"יממה" הוא K שעות. כל משקולת הופכת להזמנה של רכב למספר שעות השווה לגודל המשקולת, כאשר ההזמנה היא לרכב 1 או לרכב 2. בנוסף, יש הזמנה של 2K-N שעות לרכב 2 בלבד. סכום השעות בכל ההזמנות הוא בדיוק 2K, וכך גם סכום השעות הזמינות. לכן אם יש פתרון, הוא יהיה חייב לקיים שסכום ההזמנות של רכב 1 הוא בדיוק K, כנדרש. עכשיו, כדי לצמצם את "הפער" בין הבעיה דמוית התרמיל שהצגתי לבין בעית התרמיל המקורית ניתן לפעול בשתי דרכים: או למצוא רדוקציה מבעית התרמיל לבעיה דמוית התרמיל, או לפתח את הרדוקציה הזאת כך שתפתור בעיה יותר כללית. הנה כמה מחשבות על הדרך השניה: הדרישה ש- 2K>N היא דרישה טכנית, שלדעתי אפשר להיפטר ממנה. מה שבטוח הוא שבאופן טריביאלי אפשר לשים כל קבוע אחר במקום ה- 2. לגבי העובדה שאנחנו מוצאים פתרון רק אם הסכום הוא בדיוק K - את זה אפשר היה לפתור אילו בבעית ההזמנות היתה איזושהי "עדיפות" (כלומר, כל כותב הזמנה היה כותב באיזה עדיפות הוא רוצה אילו רכבים, והיינו יכולים להכניס garbage collector נוסף - רכב 3 - שהיה אוסף את כל מי שלא קיבל את הזמנתו). זה גם היה מאפשר להכניס פנימה את עניין הערך לעומת גודל המשקולת לדעתי (אם כי לפי זכרוני המעומעם כבר יש רדוקציה לבעיה שבה הערך הוא המשקולת). זאת בקצרה ובלי לחשוב יותר מדי, והתחושה שלי (בדומה ל- easy) היא שעם נעבוד קצת יותר נגיע לרדוקציה. |
|
|
|
|
|
|
||
|
||||
|
שים לב שכחלק מההזמנה צריך לציין מאיזו שעה עד איזו שעה הרכב נדרש. התכונה הזו מקלה מכיוון שהיא מורידה באופן משמעותי את דרגות החופש של הפתרון. | |
|
|
|
|
|
||
|
||||
|
מצד אחד היא מקלה כי היא מצמצמת את החופש אך מצד שני היא מקשה על האלגוריתם למצוא סידור. חופש בהזזת עשות ההזמנה היה מקל על האלגוריתם, ויתכן אפילו שאחד חמדן היה מוצא פתרון טוב. אגב, האלגוריתם הנאיבי שפותר את הבעיה הוא: 1. כל עוד אין התנגשות שבץ את ההזמנה הנוכחית במקום שמתאים לה. 2. אם אין מקום להזמנה הנוכחית, חזור להזמנה הקודמת ומקם אותה במקום אחר שמתאים לה ושהיא עוד לא היתה בו אף פעם. 3. חזור ל 1. נאיבי, אקספוננציאלי אבל עובד. |
|
|
|
|
|
|
||
|
||||
|
צודק, פספסתי את זה (דרישה הגיונית כשמדובר בהזמנת מכוניות...). ברור שהתכונה הזאת מקלה. אני אחשוב על הבעיה עם ההגבלה הזאת. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |