מציאת מעגל מכוון בעזרת DFS

[אלוהים1980]

מציאת מעגל מכוון בעזרת DFS

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

 

[superman19]

לדעתי

אם אתה מריץ DFS ואז אתה עובר על כל הקשתות לאחור ומוצא את זו שיוצאת מהצומת שעומקו מינימלי אז זה פותר את הבעיה. הזמן ריצה יוצא הזמן של DFS שאני כמעט בטוח שזה O(

+|E|) ואז עוד ריצה על כל הקשתות. סה"כ

+2|E| שזה O(

+|E|), תלוי בגודל הקלט.

 

[אלוהים1980]

אתה יכול לפרט קצת יותר.

לא ברור לי איך אתה מוצא את המעגל הקצר ביותר.

 

[סתם אחת....]

אם אני לא טועה יש לי אחד כזה

כתוב איפשהו. אני רק צריכה לחפש.

 

[אלוהים1980]

אף אחד לא מכיר?

מקפיץ 1 2 3 4 5 6 7 8 9 10.

 

[ahab]

רעיון

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

 

[vinney]

למה צריך את ה-1?

 

[ahab]

תשובה

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

 

[vinney]

נשמע הגיוני

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

 

[vinney]

למה דווקא DFS?

בDFS אתה סורק לעומק, ז"א המעגל הראשון שתתקל בו הוא לא בהכרח הקצר ביותר, לא?

 

[ahab]

זה משנה?

בכל מקרה אתה חייב לסרוק את כל הגרף כדי למצוא את המעגל הקצר ביותר.

 

[vinney]

לא ממש משנה

פשוט BFS נראה לי הרבה יותר בנוי לזה

 

[אלוהים1980]

ובכן,

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

 

[vinney]

אני חושב שהבוחן צודק

כמו שאמרתי, כשאתה מריץ DFS, אתה הולך לעומק. אתה יכול לגלות מעגל, אבל לא תדע אם הוא הקצר ביותר. גם אם יש כזאת וריאציה, הסיבוכיות שלה תהיה יותר גדולה מוריאציה של BFS. בערעור אתה צריך, בין היתר, להוכיח שלמדת כזאת וריאציה באלגוריתמים => להראות אותה בחומר הלימוד, לא רק שהיא קיימת.

 

[ahab]

אבל..

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

 

[vinney]

יש הבדל בין שאלה תיאורטית

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

 

[ahab]

נכון...

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

 

[אלוהים1980]

פעם הבאה לא תהיה ../images/Emo13.gif

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

 

[אלוהים1980]

העניין הוא שאני בכלל לא זוכר שלמדנו

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

 

[vinney]

שוב, זאת לא השאלה שצריכה להעסיק

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