אלגוריתם חמדן – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
הרחבה, עריכה |
אין תקציר עריכה |
||
שורה 3:
==יעילות==
במקרים מסוימים האלגוריתם החמדן הוא גם האלגוריתם האופטימלי. כלומר, סדרת בחירות חמדניות נותנת את הפתרון האופטימאלי הכללי לבעיה. למשל, [[האלגוריתם של פרים]] למציאת [[עץ פורש מינימלי]] בגרף. ▼
לעתים כאשר לא ניתן למצוא את הפתרון האופטימאלי בזמן סביר, שימוש באלגוריתם חמדן עשוי לתת קירוב טוב לפתרון המיטבי בזמן קצר. בהתחשב בעובדה שבעיות אופטימיזציה רבות הן [[NP-קשה|NP-קשות]], שימוש באלגוריתמים חמדניים יכול להיות יעיל במיוחד.
▲במקרים מסוימים האלגוריתם החמדן הוא גם האלגוריתם האופטימלי. כלומר, סדרת בחירות חמדניות נותנת את הפתרון האופטימאלי הכללי לבעיה. למשל, [[האלגוריתם של פרים]] למציאת [[עץ פורש מינימלי]] בגרף.
==בעיית הסוכן הנוסע==
| |||