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

[guy81]

מקווה שהפורום מתאים לשאלות מהסוג הזה:

מחפש פתרון באמצעות אלגוריתם חמדן לבעיה הבאה:

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

אשמח לרמז או כיוון לפתרון(כיצד החמדן יבחר את המקטע בכל פעם)?

[שניצל]

אתה מתכוון שלכל פעילות בקלט תהיה פעילות כלשהי מ-D החופפת לה? או שלכל פעילות ב-D תהיה פעילות אחרת ב-D החופפת לה?

[guy81]

לכל פעילות בקלט תהיה פעילות כלשהי ב-D החופפת לה

[Dubliner]

הרעיון הכללי באלגוריתם חמדן (GREEDY) הוא למצוא את הפעולה האופטימלית בכל שלב/איטרציה.

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

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

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

המחיר הכולל הוא סכום כל המחירים ש"שילמת" בכל שלב.

בהתאם לכל זה הכיוון שאתה צריך ללכת בו הוא הבא:

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

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

בהצלחה

[guy81]

קודם כל תודה על התגובה.

לדעתי, לא הבנת את השאלה שלי נכון או שאני לא הבנתי אותך נכון.

אני מצרף את השאלה המלאה:

http://www.fastup.co.il/v.php?file=14521733.jpg

אם אכן הבנת אותי נכון, התכוונת שעל החמדן לבחור בכל פעם את הפעילות שמתנגשת עם המספר הרב ביותר של פעילויות?

אם כן, זה לא עובד. מצאתי דוגמא נגדית...

[Dubliner]

מצטער על האיחור בתגובה, נסעתי לכמה ימים, אם זה עדיין אקטואלי:

הבנתי אותך נכון, אך ההסבר שלי היה כללי מדי וארוך מדי ולכן אני חושש שלא הבנת אותו עד הסוף.

אני מתנצל מראש, גם ההסבר הבא לא יהיה קצר אבל אני אשתדל שיהיה מובנה.

קודם כל לא התוויתי קו פעולה ממשי, מכיוון שישנן הרבה אפשרויות.

מה שכתבת שהבנת:

אם אכן הבנת אותי נכון, התכוונת שעל החמדן לבחור בכל פעם את הפעילות שמתנגשת עם המספר הרב ביותר של פעילויות?

אם כן, זה לא עובד. מצאתי דוגמא נגדית...

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

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

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

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

נחזור לבעיה שלך. באלגוריתם הבסיסי בחרנו בכל פעם את הפעילות שמתנגשת עם המספר הגדול ביותר של פעילויות. אבל, מה אם חלק מהפעילויות כבר מכוסות? ברור שאם הפעילות שעונה על הקריטריון מתנגשת עם פעילויות שרובן או כולן כבר מכוסות ע"י בחירות קודמות שעשינו, היא אינה בחירה מוצלחת. לכן, צעד אחד קדימה הוא לבחור את הפעילות שמתנגשת עם המספר הגדול ביותר של פעילויות שעדיין אינן מכוסות ע"י אף פעילות ב-D. צעד נוסף קדימה הוא לתת משקלים. לדוגמא אם בוחנים פעילות מסוימת x אשר מתנגשת עם m פעילויות ב-P שמכוסות כבר ע"י n פעילויות ב-D אפשר לתת "קנס" לבחירה ב-x שיהיה פרופורציוני ל-m ו/או ל-n. בצורה הזו אתה מאלץ את האלגוריתם ללכת לכיוון של כיסוי מקסימלי עם מספר מינימלי של פעילויות.

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

[elrxx]

יש לך את הפתרון בספר מבוא לאלגוריתמים,בחלק של אלגוריתמים חמדניים

[Dubliner]

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

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

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

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

שוב, אני מניח שהפתרון מהספר מספיק טוב לבעיה הזו, אבל במהלך שנות נסיוני במקצוע טרם נתקלתי באלגוריתם "By The Book" שהיה מספיק טוב לפתירת בעיות אמיתיות בעולם האמיתי.

[guy81]

תודה על התגובה:

אני מצרף דוגמא: תוכל לתאר לי הרצה של ההסבר שלך על הקלט הזה?(יש משהו שאנ לא במין בפתרון שלך) .תודה

-------------- ------------

------------- ----------- ----------------

-- --

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

2 התחתונים מתנגשים עם האמצע האמצעי ובנוסף הימני התחתון מתנגש עם הימני העליון והשמאלי התחתון מתנגש עם השמאלי התחתון.

[שניצל]

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

[guy81]

צודק:

פעילות 1: [2,6]

פעילות 2: [7,11]

פעילות 3: [1,3]

פעילות 4: [4,9]

פעילות 5: [10,12]

פעילות 6: [5,6]

פעילות 7: [7,8]

יש לך את הפתרון בספר מבוא לאלגוריתמים,בחלק של אלגוריתמים חמדניים

אתה בטוח שמדובר באותה שאלה בדיוק? ולא בבעיה בה צריך לשבץ מספר מקסימלי של פעילויות בלי חפיפה?

אם כן, אשמח לעמוד ספצפיפי כי לא מצאתי..

[guy81]

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

כל עוד נותרו קטעים מהקלט שלא הוסרו:

1. הסתכל על הקטע x בעל זמן סיום מוקדם ביותר.

2. מבין כל הקטעים המתנגשים איתו(כולל x), בחר את הקטע y בעל הזמן סיום הגבוה ביותר . הסר את כל הקטעים החופפים איתו(כולל הוא)

(למה זה נכון לדעתי: תמיד תהיה נקודת זמן כלשהי הקרובה לזמן סיום של x איתה מתנגשים כל הקטעים המסתיימים עד זמן הסיום y ואם מבינהם. עכשיו, הקטע x חייב להיות מכוסה איכשהו ולכן מכל הקטעים שמכסים אותו, אנו בוחרים את ההוא שיכסה מספר מרבי)

מה אתם אומרים?

(אגב אמור להיות פתרון בפחות מ n^2 ולדעתי שלי לפחות n^2 כי צריך לחפש כל פעם את הקטעים החופפים)

עריכה: מצאתי דוגמא נגדית אבל אולי משהו אחר בכיוון...

___ _____ __________

____________ ___ ___

[Dubliner]

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

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

לכן, העקרונות הראשוניים של האלגוריתם שלך צריכים להיות:

1) העדפת איברים עם חפיפה מינימלית ביניהם.

2) העדפת איברים שתחום הכיסוי שלהם הוא כמה שיותר גדול.

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

דבר ראשון שהייתי משנה באלגוריתם שהצעת הוא שלא להסתכל על זמן הסיום המוקדם ביותר - האיבר בעל זמן הסיום המוקדם ביותר הוא [1,3] שהוא איבר "קצר" ולכן סותר את עקרון 2.

שים לב שאם היית הולך על כל אחד מהעקרונות הללו בנפרד לא היית מגיע לפתרון האופטימלי. לדוגמא, האיבר הארוך ביותר הוא [4,9] ובחירה בו לא תוביל לפתרון האופטימלי. באותו אופן הייתי יכול להרכיב לך דוגמא שבה הפתרון האופטימלי כולל דווקא איברים לא זרים. למעשה זה מדגים בדיוק את הבעיתיות באלגוריתמים חמדניים - פתרון שבהתחלה נראה לך מתבקש (לבחור באיבר הארוך ביותר צריך להיות הדבר הראשון שחושבים עליו) לא בהכרח מביא לתוצאות הרצויות. מצד שני אם תשלב את שני העקרונות הללו בצורה חכמה עם עוד קצת לוגיקה אתה תגיע לפתרון (רמזים - א) צריך להסתכל גם על מספר האיברים הנחתכים עם האיבר שבחרת כקריטריון; ב) תסתכל על אורך ה"שוליים" שכל איבר משאיר משני צדדיו כקריטריון, שוליים שהם בקירוב סימטריים מהווים סתירה לעקרון 1 + דרישת קב' מינימלית).

אני משאיר לך את השאר, אחרת זה כבר לרשום ממש את הפתרון.

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

בהצלחה