הוכחת אלגוריתמים חמדניים

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

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

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

אלגוריתם של עץ פורש מינימלית

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

כל צלע המתווספת חייבת לאחד שני תתי-עצים. אם הצלע הזולה ביותר הבאה, Eх, תאחד

שני תתי-עצים, Ta ו- Tb, מכאן שנהיה חייבים, בשלב מאוחר כלשהו, להשתמש בצלע יקרה יותר, Ey, על מנת לאחד את Ta ל- Tb (ישירות או על ידי חיבור צומת של אחד מהם לצומת המקושרת לאחר). אולם, לפיכך, אנו יכולים לאחד כעת את Ta ל- Tb (וכל צומת אשר כעת מקושרת אליהם) באופן זול יותר על ידי שימוש ב- Ex, מה שמוכיח את ההנחה המוקדמת כי בחרנו את הצלע הזולה ביותר בכל שלב.

סיבוכיות

השלבים באלגוריתם קרוסקל הם:

· אתחול של היער O(|V|)

· מיון הצלעות O(|E|log|E|)

· עד לצירוף |V|-1 צלעות O(|V|) X

· בדיקה האם נוצר מעגל O(|V|) = O(|V|²)

ובסך הכל: O(|V|+|E|log|E|+|V|²)

ומאחר ש: |E|=O(|V|²)

נקבל: O(|V|²log|V|)

לכן, נתייחס לאלגוריתם קרוסקל כאלגוריתם של O(n²logn), כאשר n הוא מספר הקדקודים. בכל אופן, ניתן לראות כי אם |E| דומה ל-|V|, הסיבוכיות היא O(n²).

אלגוריתם אלטרנטיבי לקבלת עץ פורש מינימלית, הנקרא אלגוריתם פרים (Prim), יכול להתבצע בזמן של O(|E|+|V|log|V|, על ידי שימוש בערמות פיבונאצ'י.

בגלל יישומיו המעשיים הרבים, בעיית העץ הפורש מינימלית נחקרה רבות, ועבור גרפים דלילים (|E|@|V|), ידוע אפילו אלגוריתם מהיר יותר בעל סיבוכיות של O(|E| log log|V|).

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

חזור ל: עצים פורשים מינימלית חזור ל: תוכן עניינים