אז הזכרתי באחר הפוסטים האחרונים את הבעיה הבאה:
בהנתן קבוצת S של n מספרים שלמים, איך נחלק אותה לk קבוצות כך שסכום המספרים בכל קבוצה הוא קרוב לסכום המספרים בקבוצות האחרות.
למשל:
אם
[code]
S = {2,2,3,2,3}
k=2
split(S,k)={{2,2,2},{3,3}}
S1={1,5,11,2,10}
k1=3
split(S1,k1)={{5,2,1},{10},{11}}
[/code]
עבור k=2 הבעיה היא בעצם בעיית תיק הגב (Knapsack)
.
בבעיה זו יש לנו תיק גב בגודל מוגבל, וערמת חפצים במשקלים שונים ובערכים שונים ועלינו לבחור תת קבוצה של החפצים שנכנסים כולם לתיק וערכם מקסימלי.
אם הערך של כל חפץ שווה למשקל שלו (נניח כל החפצים עשויים מזהב טהור), ונפח התיק הוא חצי מסכום המשקל של כל החפצים אז הבעיה שקולה לגמרי לבעיה שלנו עבור K=2, כי רשימת החפצים שבתיק שקולה לחלוקה של החפצים לשתי קבוצות (אלו שבתיק ואלו שמחוץ לתיק).
עבור k גדול מ2, הבעיה קשה יותר.
הפתרון שמצאתי פותר את הבעיה בצורה קרובה לאופטימלית (החלוקה לא תמיד הטובה ביותר, אבל קרובה מאוד), והוא גם פשוט למימוש ויעיל במיוחד.
בשמיעה ראשונה הוא ישמע פשוט מדי מכדי להיות נכון, ואתם יותר ממוזמנים להוכיח לי שאני טועה:
1. מיינו את רשימת המספרים בסדר יורד.
2. צרו k קבוצות ריקות
3. לכל איבר ברשימה הממוינת (בסדר יורד) הכניסו אותו לקבוצה הריקה ביותר.
זה הכל.
לא היה קל מדי למצוא דוגמא שבה האלגוריתם הפשוט הזה נותר תשובה שאינה אופטימלית, אבל למעשה הדוגמא הראשונה שלי למעלה היא דוגמא כזו. בחלוקה האופטימלית שתי הקבוצות בגודל שש. בחלוקה לפי האלגוריתם שלי הגדלים יהיו שבע וחמש.
ובכל זאת, השגיאה פה היא השגיאה המינימלית האפשרית בדוגמא הזו (Off by one).
אז מה אתם אומרים, יש לכם פתרון יותר טוב?
יש לכם דוגמא שמראה לי שהפתרון שלי הוא בעצם לא טוב?
והנה בעיה נוספת עליה אני ארחיב באחד הפוסטים הקרובים:
יש לכם תמונה שחורה בגודל N על N פיקסלים ועליה מפוזרים נקודות באופן אקראי. נניח משהו דומה כזה:
הבעיה היא כזו. בהינתן קואורדינטה (x,y) מסויימת בתמונה, מצא במהירות את כל הנקודות שנמצאות בתוך חלון בגודל K על K (כאשר K קבוע בבעיה) שמרכזו (x,y), משהו כזה:
הדרישה היחידה פה היא המהירות של הפעולה הזו. מותר לכם להשתמש בכמה זכרון שתרצו ולעבד את התמונה מראש כאוות נפשכם (כמובן, העיבוד מראש לא יכול להיות איטי מדי)
כשאני אומר מהר, אני מתכוון ממש מהר, גם עבור תמונות גדולות.
אם עיבוד תמונה כולל הכנה מראש של מפה(ות) עם התשובה(ות) עבור K (או מרחב הKים) עבור כך פיקסל אז בזמן אמת תקבל תשובה בזמן מינימאלי…
מכיר את המושג היוריסטיקה (Heuristic ) ?
אחד מהתענוגות של המרצים שלי היה לדרוש מאיתנו חסם עליון על זמן ריצה ועל המרחק של היוריסטיקה מהפתרון האופטימלי.
אם יש לך הרבה זמן פנוי כחלק מ-Pre-processing הייתי הולך על Bit map מוכן וביצוע משחקים על bit array.
יואב, תן לי לחדד:
העיבוד המקדים צריך להיות בזמן סביר בעצמו. אם אתה מסוגל לחשב מהר (לינארי במספר הפיקסלים) את התשובה עבור כל פיקסל אז אתה לא צריך עיבוד מקדים. ואם העיבוד המקדים שלך הוא איטי מדי אז לא עשינו פה כלום.
צביקה:
מכיר. התלבטתי אם לנסות למצוא את המרחק של הפתרון שלי מהפתרון האופטימלי ואת המאפיינים של המרחק הזה (כמה רע הוא יכול להיות במקרים הקיצוניים), אבל ירדתי מזה. כמו שרמזת זה תענוג מפוקפק למדי :).
לגבי העיבוד המקדים: הוא צריך להיות מהיר בעצמו, אפשר מן הסתם לחשב מראש טבלא שנותנת את הפתרון לכל פיקסל בזמן מטורף (למשל סדר גודל של N^4) ואז לפנות לטבלא ברגע האמת, אבל לא על הפתרון הזה אני חושב.
הוא יקר מדי בזמן עיבוד מקדים (וגם בצריכת זכרון, אבל נעזוב את זה לרגע).
אני מניח שאתה יודע, אבל בכל מקרה: הבעיה שהצגת נקראת range searching. יש עליה המון ספרות. אפשר למשל להסתכל בספר של Cormen ושותפים. בפרט, range tree יתן לך תפוסת מקום סבירה וזמן שאילתה מהיר למדי. זו בעיה נפוצה וחשובה ויש עליה מאות מאמרים, ואני מניח שאפשר לעשות אופטימיזציות לרוב.
אלעד, מהיר למדי – כן. אבל אני רוצה מהיר מאוד :).
אחרי שאני אציג את הפתרון שלי, אני אשמח להשוות אותו למימוש מבוסס range tree ולראות מה נותן ביצועים טובים יותר.
אלעד: שם לב שעץ טווחים יודע לתת תשובה עבור כל טווח – ובשאלה שלי הטווח הוא יחיד וקבוע (K על K). ההבדל הזה מאפשר אופטימיזציה משמעותית.
אני לא מבין למה זו לא שאלת דוקטור-האוס. כלומר, למה זו לא שאלה שהקורא הנבוך לא יכול לענות עליה כיהוא לא יודע לאיזה פרמטרים אתה מתכוון (פחות או יותר), על איזה מודל אתה חושב (מחשב שולחני רגיל? האם אתה עושה אבסטרקציה ל-cache או לא, וכולי), על מה לא איכפת לך לוותר, וכן הלאה. כדי להפוך את זה ל"חידה" היה צריך לפרט יותר. אם אתה לא מתכוון לפרט יותר, אפשר לבקש מהקוראים הצעות לגבי פתרונות אפשריים למגוון פרמטרים ושיסבירו מה טוב בפתרון שלהם, אבל אין לי אישית עניין מיוחד להציע מגוון אפשרויות לפתרום, כשיש על הבעיה ספרות מקיפה. אני לא אומר שזו לא משימה מהנה, אני רק אומר שהיא לא מהנה בשבילי.
* פרמטרים :
תמונה בגודל 1000 על 1000, עד תמונה בגודל 10000 על 10000.
גודל חלון : נניח 20 על 20.
* מחשב שולחני רגיל (או שרת).
* איזה אבסטרקציה לקש? למה אתה מתכוון?
כשאני אציג את הפתרון שלי, הוא הוא יכלול גם מדידת ביצועים.
המדידה תתבצע באופן הבא:
לכל פיקסל בתמונה (כולל השחורים) ספור כמה פיקסלים שכנים יש בחלון שלו.
הבדיקה תבצע כ10 פעמים על אותה תמונה, שתהיה בגודל 1000 על 1000, עם חלון בגודל 20 על 20, ולא תכלול את הזמן של העיבוד המקדים (ושוב – הוא צריך להיות מהיר למדי, אני לא אמור להרגיש אותו בכלל עבור תמונה בגודל הזה).
המטרה היא לקבל תוצאה מהירה ככל האפשר.
הפתרון שלך לבעיית החלוקה ההוגנת באמת נותן תוצאה מעולה בהרבה מאןד מקרים.
עם זאת, ניתן לבנות דוגמאות שבהם הוא שוגה ולהגדיל את השגיאה כמה שנראה. בשביל זה צריך להקצין את הדוגמה שנתת. למשל, אם יש לי 2 יחידות של 15, ו-3 יחידות של 10, אז הקבוצות יוצאות עם הפרש 10 ביניהן למרות שהחלוקה האופטימלית נותנת שתי קבוצות עם סכום זהה.
אריה, זה נכון – אבל בלי להכנס לכל מני הגדרות פורמליות : אם כל הקבוצות שלך גדולות, כנראה תהיה יותר סלחן כלפי הפרשים יותר גדולים.
בדוגמא הקיצונית שלך, כל הקבוצות וגם ההפרשים הוכפלו בחמש.
אבל להרבה מאוד ישומים זה עדיין מאותו סדר גודל של OFF BY ONE.
Create a voronoi diagram; the rest should be easy 🙂
you will have to be more specific than this, because to me it sounds like you are transforming a problem by a similar problem.
supposed you made a vornoi diagram, how will that help solve this problem?