באלגוריתם חמדני, אנחנו מבצעים את כל הבחירה הנראית הטובה ביותר כרגע בתקווה שהיא תוביל לפתרון אופטימלי גלובלי. בתכנות דינמי אנו מקבלים החלטות בכל שלב בהתחשב בבעיה הנוכחית ובפתרון לבעיית המשנה שנפתרה בעבר כדי לחשב פתרון אופטימלי.
כמה פתרונות אפשריים יש בשיטה החמדנית?
אלגוריתם חמדני עושה בחירות חמדניות בכל שלב כדי להבטיח שפונקציית המטרה תהיה אופטימלית. לאלגוריתם Greedy יש רק 1 shot כדי לחשב את הפתרון האופטימלי כך שלעולם לא יחזור אחורה ויהפוך את ההחלטה.
מהו הרעיון של שיטה חמדנית?
הגדרה: אלגוריתם שתמיד לוקח את הפתרון המיידי, או המקומי, הטוב ביותר תוך מציאת תשובה. אלגוריתמים חמדנים מוצאים את הפתרון האופטימלי הכולל, או הגלובלי, לבעיות אופטימיזציה מסוימות, אך עשויים למצוא פתרונות פחות מאופטימליים עבור מקרים מסוימים של בעיות אחרות.
מה הם היתרונות של גישה חמדנית?
היתרון בשימוש באלגוריתם חמדני הוא שפתרונות למופעים קטנים יותר של הבעיה יכולים להיות פשוטים וקלים להבנה. החיסרון הוא שזה בהחלט אפשרי שהפתרונות האופטימליים ביותר לטווח קצר עשויים להוביל לתוצאה הגרועה ביותר האפשרית לטווח ארוך.
מתי עלינו להשתמש בחמדנות?
להלן מוזכרות כמה בעיות המשתמשות בפתרון האופטימלי בגישה של Greedy
- בעיית איש מכירות מטייל.
- אלגוריתם העץ המינימלי של קרוסקאל.
- Dijkstra's Minimal Spanning Tree Algorithm.
- בעיית תרמיל.
- בעיית תזמון עבודה.
