תוכן עניינים:
הגדרה - מה המשמעות של אלגוריתם חמדן?
אלגוריתם חמדן הוא אסטרטגיה אלגוריתמית שעושה את הבחירה האופטימלית הטובה ביותר בכל שלב קטן במטרה זו תביא בסופו של דבר לפיתרון אופטימלי בעולם. המשמעות היא שהאלגוריתם בוחר כרגע את הפיתרון הטוב ביותר ללא התחשבות בתוצאות. הוא בוחר את התפוקה המיידית הטובה ביותר, אך אינו מחשיב את התמונה הגדולה, ולכן היא נחשבת לחמדנית.
Techopedia מסביר את האלגוריתם החמדן
אלגוריתם חמדן פועל על ידי בחירת התשובה הטובה ביותר האפשרית בכל שלב ואז מעבר לשלב הבא עד שהוא מגיע לסופו, בלי להתייחס לפיתרון הכללי. זה רק מקווה שהנתיב שהוא לוקח הוא האופטימלי הגלובלי, אך כפי שמוכח שוב ושוב, לעיתים קרובות שיטה זו אינה מציאה פיתרון אופטימלי גלובלי. למעשה, ייתכן בהחלט שהפתרונות האופטימליים ביותר לטווח הקצר מובילים לתוצאה הגלובלית הגרועה ביותר האפשרית.
חשבו על זה כמי שמקבלים קיצורי דרך רבים בעסקי ייצור: בטווח הקצר חוסכים כמויות גדולות בעלות הייצור, אך בסופו של דבר הדבר מוביל לנפילה מכיוון שהאיכות נפגעת, וכתוצאה מכך תשואות מוצרים ומכירות נמוכות ככל שהלקוחות מתוודעים ל מוצר "זול". אבל זה לא תמיד המקרה, יש הרבה יישומים שבהם האלגוריתם החמדן עובד בצורה הטובה ביותר כדי למצוא או להתקרב לפיתרון האופטימלי הגלובלי, כמו למשל בניית עץ Huffman או עץ למידת החלטות.
לדוגמה: סע בדרך עם הסכום הגדול ביותר בסך הכל. אלגוריתם חמדן ייקח את הנתיב הכחול, כתוצאה ממבט קוצר ראייה, ולא בשביל השביל הכתום, שמניב את הסכום הגדול ביותר.
רכיבים:
- סט נתונים מועמד שצריך פיתרון
- פונקציית בחירה שבוחרת את התורם הטוב ביותר לפיתרון הסופי
- פונקציית היתכנות המסייעת לפונקציית הבחירה על ידי קביעה אם מועמד יכול להיות תורם לפיתרון
- פונקציה אובייקטיבית המקצה ערך לפיתרון חלקי
- פונקציית פתרונות המצביעה על כך שהתגלה הפיתרון האופטימלי
