פורום קהילת הסטודנטים בטכניון
טכניוני => עזרה בפיתרון תרגילים => נושא נשלח על ידי: Just a Girl על דצמבר 11, 2012, 23:53:55 PM
-
אני מתקשה מאוד עם שאלה 2:
נתון גרף ממושקל G=(V,E) שבו משקל כל קשת הוא 1 או 2. הציעו אלגוריתם המוצא עפ"מ בזמן O(V+E).
אין לי ממש כיוון.
חשבתי על BFS או DFS, אבל אני לא חושבת שזה יעזור לי איכשהו, כי גם אם אני אשנה את האלגוריתם איכשהו אני אצטרך להוכיח שהעץ שקיבלתי הוא מינימום, וזה נראה לי בכלל בכלל לא טריויאלי, כמו שההוכחה של DFS ו-BFS לא טריויאלית.
להשתמש בקרוסקל או פרים - אני חושבת שזה בעייתי מבחינת הסיבוכיות (אגב, מה יותר גדול? E+V או ElogV? אני מניחה מהשאלה ש-ElogV, אחרת אפשר לפתור את זה עם קרוסקל/פרים, אבל לא ממש ברור לי למה...)
בקיצור, אין לי ממש כיוון, אז אשמח לעזרה, כי ההגשה למחר בלילה....
תודה! :)
-
ראשית, אם אנחנו דנים בבעיית העפ"מ, אז הגרף בוודאי קשיר, לכן V=O(E) וכך V+E=O(E) ובפרט קטן מ-ElogV.
יש יותר מפתרון אחד לשאלה, אבל כנראה שהפשוט ביותר הוא להסתכל על האלגוריתמים שנלמדו בכיתה ולראות איפה הם "עולים כסף" ואיך אפשר לחסוך בעזרת הנתון.
-
חשבתי להשתמש באלגוריתמים שלמדנו בכיתה, כמו פרים/קרוסקל, ולחסוך את המיון של הקשתות שעולה לנו ElogE. במקרה הזה, מיון של הקשתות לשתי קבוצות יעלה רק E.
אבל בשניהם יש גם את השלב הבא (בקרוסקל Union-Find ובפרים ערימת מינימום), שממנו אני לא ממש מצליחה להמנע....
כלומר, אני לא מצליחה לחסוך פרט לעניין המיון, אבל נראה שזה לא עוזר לי הרבה....
-
בפרים אין שלב של מיון, אלא רק תור קדימויות (שבאחד המימושים מסופק ע"י ערימת מינימום). אפשר לממש תור קדימויות טוב יותר כאשר המשקלים מוגבלים.