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