חידה חדשה

[gimik]

חידה חדשה

פרופסור מאקס מחפש את מראה המקום של ציטוט שקרא פעם בספר כלשהו. לרוע המזל הוא אינו זוכר את שם הספר או מחברו. כל מה שהוא זוכר מלבד הציטוט עצמו הוא על מדף מדף בספרייה מונח הספר. על המדף מסודרים n ספרים ובכל ספר מספר עמודים שונה כאשר ידוע מראש כמה עמודים יש בכל ספר. מפאת חשיבות העניין הועמדו לרשות הפרופסור צוות של m עוזרי מחקר שיחלקו ביניהם את עבודת החיפוש. כדי למזער את הבלאגן הפרופסור רוצה לחלק את הספרים בין עוזרי המחקר באופן כזה שכל אחד יקבל רצף של ספרים לחיפוש. הפרופסור רוצה לחלק את הספרים בין העוזרים באופן שזמן החיפוש יהיה קצר ככל האפשר. אנו יוצאים מנקודת הנחה שכל העוזרים מדפדפים וקוראים בקצב אחיד ושכל העמודים בספר דורשים את אותו זמן טיפול. מהי הנוסחה בה יש להשתמש לפי שני עוזרים ומהי הנוסחה לפי m עוזרים?

 

[ליבליך]

הפתרון שאני מכיר לבעיות כאלה

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

 

[gimik]

התעלמת מנתון חשוב בחידה

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

 

[Renatius Cartesius]

נוסחא של...

הספק לא?

 

[gimik]

הספק?

אבל איך לחלק את הספרים נכונה כדי שנקבל את ההספק האופטימלי?

 

[יאיר של תמר]

מצאתי ל- 2

זאת לא נוסחה... זה אלגוריתם... ובאופן כללי הרעיון הוא לנסות לסכום משני הכיוונים את מספר הדפים, באופן שהמקסימום בין הסכומים יהיה הנמוך ביותר. ההנחה היא שהסדרה A1,A2...AN - מייצגת את מספר העמודים בכל ספר במדף לפי הסדר שהם מסודרים בו. שלושת הפלטים של האלגוריתם המצורף הם: מספר הספרים שהראשון יקבל, מספר הספרים שהשני יקבל, כמות הדפים המקסימלית - שזהו הזמן הגרוע ביותר לסיום העבודה. האם לזאת הכוונה?? אם אכן זאת הכוונה, הצלחתי ל-3 באופן מסובך מדי, ולא יודע איך עושים את זה ל-M ...

 

[gimik]

עדיין לא מספיק ועדיין יש בעיות

במקרה של 2 יש אלגוריתם דומה: נחשב את סכום כל העמודים חלקי 2 (ממוצע) נחשב במערך לכל תא i את הסכום של הספרים מתחילת המדף עד אליו כולל. נרוץ על המערך עד שנמצא תא i שערכו קטן (או שווה) מהממוצע שחישבנו, והערך בתא הבא גדול ממנו. אם הממוצע קרוב יותר לערך שבתא ה i אז זהו האינדקס שבו נשים חוצץ בחלוקה, אחרת החוצץ יהיה ב i+1 אבל אלגוריתם זה לא עובד עבור m עוזרים. דוגמאות של קלט עם הפתרון האופטימלי: 2 2 2 2 2 | 5 4 5 | 2 2 2 2 2 (3 עוזרים) 100 | 2 2 2 2 2 | 2 2 2 2 2 (3 עוזרים) 1 1 5 | 8 | 1 1 2 | 3 1 1 1 | 8 (5 עוזרים)

 

[יאיר של תמר]

שים לב לכותרת... ../images/Emo13.gif

הכותרת הייתה .. "מצאתי ל-2..." ולא ל-M ... אז, לא היית צריך לצפות שזה יפתור ל-M...

ומדבריך היה קשה לי להבין אם אתה סבור שהאלגוריתם שלי ל-2 הוא נכון... פשוט כתבת אלגורתם נוסף (שהוא, דרך אגב, שבאותו סדר גודל כמו שלי, אבל עדיין פחות יעיל, מכיוון שהוא מצריך יותר ממעבר אחד על המערך).

 

[עריסטו]

אפשר

תכנות דינמי. הדרך האופטימלית לחלק את 0 הספרים השמאליים ברורה (כל עובד מקבל 0 ספרים והעלות היא 0). נניח שמצאנו לכל k בין 0 ל - x את הדרך האופטימלית לחלק את k הספרים השמאליים. אנו רוצים למצוא את הדרך האופטימלית לחלק את k+1 הספרים השמאליים. נעשה זאת כך: n ירוץ בין 1 ל - k+1. לכל n, נמצא את העלות אם עובד אחד יקבל את n הספרים הימניים, ושאר הספרים יתחלקו בין העובדים האחרים.

 

[יאיר של תמר]

הממ...

אפשר לנסות את כל האפשרויות גם כן... האם האלגוריתם שלך יותר יעיל?

 

[עריסטו]

בודאי

אם יש n ספרים, הסיבוכיות שלו היא O(n^2) zzz. אם יש, למשל, 1000 ספרים ו-100 עובדים, מספר האפשרויות לחלוקת הספרים הוא עצום, אבל האלגוריתם שלי יפתור את הבעיה במהירות.

 

[עריסטו]

הבהרת האלגוריתם

יש b ספרים ו - w עובדים. האלגוריתם משתמש במערך של b שורות ו - w עמודות. בשורה r עמודה c נמצא הזמן הדרוש לסריקת rהספרים השמאליים ע"י c עובדים במקרה הגרוע ביותר. אתחול המערך: מאתחלים את שורה 1 (ברור כיצד). כעת יש לנו כבר פתרון עבור הבעיה המכילה ספר אחד. אם יש לנו פתרון עבור הבעיות המכילות עד k ספרים, כלומר מילאנו את k השורות הראשונות בטבלה, נמלא את שורה k+1 לפי סדר עולה של מספרי העמודות, כך: בעמודה 1 נמצא הזמן הדרוש לסריקת k+1 ספרים ע"י עובד אחד - אין מה לחשב. בעמודה x יימצא הזמן הדרוש לסריקת k+1 ספרים ע"י x עובדים. הוא יחושב כך: נקרא מהטבלה את העלות של סריקת k ספרים ע"י x-1 עובדים, ונחשב את המקסימום של זה ושל ספר מס' k+1; נקרא מהטבלה את העלות של סריקת k-1 ספרים ע"י x-1 עובדים, ונחשב את המקסימום של זה ושל ספרים מס' k+1 ו-k; וכך הלאה. נשמור בשורה k+1 עמודה x את המינימום מבין כל המקסימומים האלה.

 

[gimik]

הבהרת החידה

הפרופסור רוצה לחלק את הספרים בין העוזרים באופן שזמן החיפוש יהיה קצר ככל האפשר. הצע חלוקה כזו! ז"א למשל עבור שלושת הספרים באורכים 4 4 8 ושלושה עוזרים, נרצה לתת ספר אחד לכל עוזר. כלומר חלוקה: 4|4|8 האלגוריתם שלך מייצר את הטבלה הזו: 8 8 8 12 8 8 16 8 8 מה שאפשר להסיק מהטבלה זה רק את משך הזמן הגרוע ביותר לחיפוש 8 שזה נכון, אבל זו לא דרישת השאלה. הדרישה היא להחזיר אינדקסים האומרים לפרופסור איך לחלק את הספרים. שים לב שלמרות שבמקרה הגרוע בדוגמה זו זמן החיפוש הוא 8, התשובה האופטימלית היא 4|4|8 ולא 0|4 4|8 כיוון שיתכן שהמשפט אותו מחפש הפרופסור ימצא בספר השלישי (4) ואם כך, זמן החיפוש בפועל קטן יותר בתשובה האופטימלית.

 

[עריסטו]

אבל אבל...

לא הבנתי למה התשובה האופטימלית היא 4|4|8 ולא 0|4 4|8. חשבתי שהמדד היחיד לאופטימליות של תשובה הוא הזמן המקסימלי שיכול לעבור עד שיימצא המשפט, לא כך אמרת?

 

[עריסטו]

ובקשר לחלוקה

ניתן להשתמש בטבלה נוספת. כל פעם שכתבנו ערך בטבלה הראשונה - נשמור בטבלה השניה את מיקום החלוקה שיצרה ערך זה.

 

[gimik]

עדיין בעיות

נכון, זוהי שאלה בנושא תכנות דינאמי. אך לא הסברת איך האלגוריתם שלך מוצא את החלוקה. אם הוא מחשב לכל n את הסכום, זה, כמו לחשב מערך של הסכומים מההתחלה עד לכל ספר (כמו בתגובה שרשמתי ל 'יאיר של תמר') אבל מה האלגוריתם שמחליט על ה n המסויים שתרצה לחצוץ בו את החלוקה? אני אוסיף גם כאן את הדוגמאות של קלט עם הפתרון האופטימלי: 2 2 2 2 2 | 5 4 5 | 2 2 2 2 2 (3 עוזרים) 100 | 2 2 2 2 2 | 2 2 2 2 2 (3 עוזרים) 1 1 5 | 8 | 1 1 2 | 3 1 1 1 | 8 (5 עוזרים)