צריך כיוון

[JohnnyPiloni]

צריך כיוון

במסיבה משתתפים n בנים ו-n בנות. כל בן מכיר בדיוק k בנות וכל בת מכירה בדיוק k בנים (k>0). יחס ההיכרות הוא הדדי. 1.מצאו אלגוריתם שמארגן ריקוד זוגות כאשר כל זוג מורכב מבן ובת שמכירים זה את זו. 2.מצאו אלגוריתם שמארגן k ריקודים כך שכולם ירקדו פעם אחת בדיוק עם כל מי שהם מכירים.

 

[Maha Vailo]

צפון מערב

אם אין כאן עניין של סיבוכיות, אז הדרך הכי קלה היא ליצור מערך של nXn כך שהתא ה i, j יהיה אחד אם בן i מכיר את בת j ואפס אם הם לא מכירים. עכשיו כל שנותר זה למצוא n תאים שיש בהם 1, כך שכל אחד נמצא בשורה ועמודה שונים. אפשר לעשות את זה למשל ע"י בחירת תא עם אחד מכל עמודה ככה שלא יתנגש עם בחירות מעמודות קודמות. אם בודקים את כל האפשרויות, כמו בשאלה השנייה זה ייקח k^n זמן לכל היותר, שזה הרבה מאוד, אבל פותר את הבעיה.

 

[JohnnyPiloni]

?

1.1. נגיד ואני צריך לממש את השאלה הראשונה, אני אצטרך לרוץ לולאה בתוך לולאה סיבוכיות(^ O(n נכון? 1.2.בשאלה שניה למה זה יקח n^k זה צריך להיות k כפול הסיבוכיות שקיבלנו בסעיף א יש אפשרות לעשות זאת בסיבוכיות יותר קטנה?

 

[Maha Vailo]

סיבוכיות

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

 

[JohnnyPiloni]

לעשות מעבר bfs?

 

[1ca1]

בעיות זרימה מכיר?

צד אחד בנים, צד שני בנות, בין בן לבת יש קשת אם הם מכירים, מריצים על זה בעיית זרימה (למשל עם פורד-פולקרסון או אדמונד-קארפ) ומוציאים זרימה מקסימלית. הזרימה הזאת בוודאי מבטיח לך שכל זוג מורכב מבן ובת שמכירים זה את זו. למעשה EK זה EV, כעת V=2n, וE שווה nk ולכן סה"כ נקבל 2n^2k שזה קטן מn^3,פולינומיאלי והכל סבבה. לגבי הבעיה השנייה, הדבר הטריוויאלי הוא להריץ את הבעיה הראשונה בשלבים, וכל פעם ל"הוריד" את הבנים ובנות שכבר רקדו (כלומר להוריד קשתות שמילאת, כלומר לקחת בעיית זרימה שיורית בגרף הזה), וזה יקח לכל היותר n סיבובים להריץ את זה (כי בסוף בכל סיבוב, הבת חייבת לרקוד עם בן אחר כי הורדנו את הקשת הקודמת), אז סה"כ תקבל בסיבוכיות את הסיבוכיות הקודמת בחזקת n, שזה בעייתי מאוד, אני צריך להמשיך לחשוב קצת על הבעיה (אפשר בקלות לתת כאן משהו הסתברותי, אבל אני מניח שאתה מחפש משהו דטרמיניסטי).

 

[1ca1]

כמובן רשמתי שטויות

אם תריץ את הבעיה הקודמת n פעמים בעצם תקבל את הסיבוכיות הקודמת כפול n, עדיין פולינומיאלי, היפ היפ הוראי... (ד"א ניתוח מדוייק יותר (אולי אפילו amortized) כנראה יעשה את החיים אפילו יותר פשוטים (עם ההורדה של אנשים לאט לאט לקראת הסוף -> פחות E וK))

 

[JohnnyPiloni]

אין לי מושג מה זה בעיות זרימה

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

 

[1ca1]

בבקשה

http://en.wikipedia.org/wiki/Flow_network בכל האופן, העניין בגדול עובד כך: יש לנו נקודת כניסה, שיכולה להזרים "כמות אינסופית" של חומר, כעת יש לנו קבוצה של קשתות שיוצאות ממנה, ועוברות באיזה גרף כלשהו, ובסוף מתרכזות בנקודת יציאה (הכי טוב לראות את זה בשרטוטים בויקיפדיה). כל כל קשת כזאת, יש לנו "מגבלת קיבול", כלומר יש לנו מגבל שכמות החומר שאפשר להזרים דרך הצינור (תחשוב על זה כקובע כמה צול הצינור שלך, וההזרמה היא במהירות קבועה והמים אי-דחיסים, אז הצול קובע את הכמות). כעת המטרה שלנו היא להגדיר כמה להזרים לכל אחת מהקשתות שיוצאת בהתחלה מחור הכניסה, כך שהכמות הזאת תהיה מקסימלית, והזרימה תעמוד בהגדרות הקיבול (זה בעצם מעין אופטימיזציה כזאת), שים לב שאם למשל עוברים מצינור בעל קיבול גדול לצינור בעל קיבול קטן, הצינור הקטן יהווה bottleneck שלא תוכל לעקוף, מצד שני, נניח צינור גדול מתפצל לשני צינורות קטנים, אז אולי אפשר להזרים דרכו את כל חומר? ואולי בכלל הצינור הגדול בעצמו מהווה את הbottleneck? האלגוריתמים שהזכרתי (ford fulkerson ו edmonds karp (שלמעשה מממש את FF בצורה מיוחדת...)) מוצאים פתרון לבעיה הזאת בסיבוכיות פולינומיאלית, ודרך הבעיה הזאת גם קל מאוד לגשת לבעיות זיווג...

 

[HaifaMan]

השאלה הזו מוכרת לי../images/Emo6.gif

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

 

[JohnnyPiloni]

אשמח לשמוע את הפתרון של

 

[HaifaMan]

הפתרון בקצרה

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