|
|
עמוד:343
6 . 3 . 3 אלגוריתם חמדן ( greedy ) אלגוריתמים הפותרים בעיות אופטימיזציה מבצעים סדרה סופית של צעדים ובכל צעד מקבלים מספר הכרעות בין אפשרויות שונות . אלגוריתם חמדן בוחר באפשרות הטובה ביותר ברגע נתון בתקווה שבחירה כזו תוביל לפתרון אופטימלי כולל . באופן כללי , אלגוריתמים חמדנים אינם מספקים בהכרח פתרונות אופטימליים כוללים לבעיות , ואולם בעבור בעיות לא מעטות הם נותנים פתרון אופטימלי כולל . גם במקרה של בעיית העץ הפורש המינימלי , ניתן להראות שאלגוריתמיס חמדנים מסוימים מחזירים עץ פורש בעל משקל מינימלי . האלגוריתם של קרוסקל מוצא , בכל שלב , קשת ( a , b ) בעלת משקל מינימלי מבין כל הקשתות המחברות שני עצים כלשהם ביער . מכאן נובע , שהאלגוריתם של קרוסקל הוא אלגוריתם חמדן , כיוון שבכל צעד הוא מוסיף ליער קשת בעלת משקל קטן ככל האפשר . במילים אחרות , בחירת הקשת בעלת משקל קטן ככל האפשר היא האפשרות הטובה ביותר בכל שלב , מכיוון שברצוננו למצוא עץ פורש שסכום המשקלות של הקשתות שלו הוא מינימלי . השאלה המרכזית היא ! האם גישה חמדנית כזו נותנת פתרון אופטימלי כולל לבעיית עץ פורש מינימלי ? התשובה לשאלה זו היא חיובית , ונראה בהמשך ( משפט ( 6 . 3 . 4 . 1 כי אסטרטגיה חמדנית , כפי שבאה לידי ביטוי באלגוריתם של קרוסקל , מחזירה עץ פורש בעל משקל מינימלי . 6 . 3 . 4 הנכונות של האלגוריתם של קרוקסל מצד אחד , האלגוריתם של קרוסקל מתבסס על גישה חמדנית , שאינה מבטיחה תמיד פתרון אופטימלי כולל . מצד שני , נאמר שהאלגוריתם של קרוסקל מניב עץ פורש מינימלי . המשפט הבא מראה את הנכונות של הטענה הזאת .
|
|