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