- אלגוריתם טיפוס גבעות הוא אלגוריתם חיפוש מקומי אשר נע ללא הרף בכיוון של עלייה בגובה/ערך כדי למצוא את פסגת ההר או את הפתרון הטוב ביותר לבעיה. הוא מסתיים כאשר הוא מגיע לערך שיא שבו לאף שכן אין ערך גבוה יותר.
- אלגוריתם טיפוס גבעות הוא טכניקה המשמשת לאופטימיזציה של הבעיות המתמטיות. אחת הדוגמאות הנדונות רבות של אלגוריתם טיפוס היל היא בעיית מכירות נסיעות שבה עלינו למזער את המרחק שעבר איש המכירות.
- זה נקרא גם חיפוש מקומי חמדני מכיוון שהוא מסתכל רק על שכנתו המיידית הטובה ולא מעבר לכך.
- לאלגוריתם של צומת טיפוס גבעות שני מרכיבים שהם מצב וערך.
- טיפוס גבעות משמש בעיקר כאשר יש היוריסטיקה טובה.
- באלגוריתם זה, איננו צריכים לתחזק ולטפל בעץ החיפוש או בגרף מכיוון שהוא שומר רק על מצב נוכחי בודד.
תכונות של טיפוס גבעות:
להלן כמה מאפיינים עיקריים של אלגוריתם טיפוס הגבעות:
תרשים מדינה-מרחב לטיפוס גבעות:
נוף מצב-מרחב הוא ייצוג גרפי של אלגוריתם טיפוס גבעות המציג גרף בין מצבים שונים של אלגוריתם ופונקציית אובייקטיבית/עלות.
js settimeout
בציר Y לקחנו את הפונקציה שיכולה להיות פונקציה אובייקטיבית או פונקציית עלות, ו-state-space על ציר ה-x. אם הפונקציה בציר Y היא עלות אז, מטרת החיפוש היא למצוא את המינימום הגלובלי והמינימום המקומי. אם הפונקציה של ציר Y היא פונקציה אובייקטיבית, אזי מטרת החיפוש היא למצוא את המקסימום הגלובלי והמקסימום המקומי.
אזורים שונים בנוף החלל של המדינה:
מקסימום מקומי: מקסימום מקומי הוא מדינה שהיא טובה יותר מהמדינות השכנות שלה, אבל יש גם מדינה אחרת שהיא גבוהה ממנה.
מקסימום גלובלי: המקסימום הגלובלי הוא המצב הטוב ביותר האפשרי של נוף שטח המדינה. יש לו את הערך הגבוה ביותר של פונקציה אובייקטיבית.
מצב נוכחי: זהו מצב בתרשים נוף שבו סוכן נמצא כעת.
אתחול המילון c#
מקסימום מקומי שטוח: זהו מרחב שטוח בנוף שבו לכל המדינות השכנות של המדינות הנוכחיות יש אותו ערך.
כָּתֵף: זהו אזור רמה שיש לו קצה עלייה.
סוגי אלגוריתם לטיפוס גבעות:
- טיפוס פשוט על גבעה:
- טיפוס גבעה התלול ביותר:
- טיפוס גבעה סטוכסטי:
1. טיפוס פשוט על גבעות:
טיפוס פשוט על גבעות הוא הדרך הפשוטה ביותר ליישם אלגוריתם טיפוס גבעות. זה רק מעריך את מצב הצומת השכן בכל פעם ובוחר את הראשון שמייעל את העלות הנוכחית ומגדיר אותו כמצב נוכחי . זה רק בודק שזהו מצב יורש אחד, ואם הוא מוצא טוב יותר מהמצב הנוכחי, אז העבר אחר יהיה באותו מצב. לאלגוריתם זה יש את התכונות הבאות:
- פחות זמן גוזל
- פתרון פחות אופטימלי והפתרון אינו מובטח
אלגוריתם לטיפוס פשוט על גבעות:
- אם זה מצב המטרה, אז החזר הצלחה ועזוב.
- אחרת, אם הוא טוב יותר מהמצב הנוכחי, הקצה מצב חדש כמצב נוכחי.
- אחרת אם לא יותר טוב מהמצב הנוכחי, אז חזור לשלב 2.
2. טיפוס על הגבעה התלול ביותר:
אלגוריתם העלייה התלול ביותר הוא וריאציה של אלגוריתם פשוט לטיפוס גבעות. אלגוריתם זה בוחן את כל הצמתים השכנים של המצב הנוכחי ובוחר צומת שכן אחד הקרוב ביותר למצב המטרה. אלגוריתם זה גוזל יותר זמן כשהוא מחפש שכנים מרובים
אלגוריתם לטיפוס על הגבעה התלולה ביותר:
- תן ל-SUCC להיות מדינה כזו שכל יורש של המדינה הנוכחית יהיה טוב ממנה.
- עבור כל מפעיל שחל על המצב הנוכחי:
- החל את האופרטור החדש וצור מצב חדש.
- להעריך את המצב החדש.
- אם זה מצב המטרה, החזר אותו וצא, אחרת השווה אותו ל-SUCC.
- אם זה טוב יותר מ-SUCC, הגדר מצב חדש כ-SUCC.
- אם ה-SUCC טוב יותר מהמצב הנוכחי, הגדר את המצב הנוכחי ל-SUCC.
3. טיפוס גבעות סטוכסטי:
טיפוס גבעות סטוכסטי לא בוחן את כל שכנו לפני המעבר. במקום זאת, אלגוריתם החיפוש הזה בוחר צומת שכן אחד באקראי ומחליט אם לבחור בו כמצב נוכחי או לבחון מצב אחר.
java system.out.println
בעיות באלגוריתם טיפוס הרים:
1. מקסימום מקומי: מקסימום מקומי הוא מצב שיא בנוף שהוא טוב יותר מכל אחת מהמדינות השכנות לו, אך קיימת גם מדינה אחרת שהיא גבוהה מהמקסימום המקומי.
פִּתָרוֹן: טכניקת החזרה לאחור יכולה להיות פתרון של המקסימום המקומי בנוף המרחב של המדינה. צור רשימה של הנתיב המבטיח כך שהאלגוריתם יוכל לעקוב אחר מרחב החיפוש ולחקור גם נתיבים אחרים.
2. מישור: רמה היא השטח השטוח של מרחב החיפוש שבו כל המצבים השכנים של המצב הנוכחי מכילים את אותו ערך, בגלל שהאלגוריתם הזה לא מוצא שום כיוון הכי טוב לנוע בו. חיפוש טיפוס גבעות עלול ללכת לאיבוד באזור הרמה.
פִּתָרוֹן: הפתרון לרמה הוא לעשות צעדים גדולים או קטנים מאוד תוך כדי חיפוש, כדי לפתור את הבעיה. בחר באופן אקראי מצב שנמצא רחוק מהמצב הנוכחי, כך שייתכן שהאלגוריתם יוכל למצוא אזור שאינו מישור.
רשימה מקושרת כפולה
3. רכסים: רכס הוא צורה מיוחדת של המקסימום המקומי. יש לו שטח שהוא גבוה מהשטחים שמסביבו, אבל עצמו יש שיפוע, ולא ניתן להגיע אליו בתנועה אחת.
פִּתָרוֹן: בעזרת חיפוש דו-כיווני, או תנועה לכיוונים שונים, נוכל לשפר את הבעיה הזו.
חישול מדומה:
אלגוריתם טיפוס גבעות שלעולם לא עושה מהלך לעבר ערך נמוך יותר מובטח שאינו שלם כי הוא יכול להיתקע על מקסימום מקומי. ואם האלגוריתם מחיל הליכה אקראית, על ידי הזזת יורש, אז זה עשוי להשלים אבל לא יעיל. חישול מדומה הוא אלגוריתם אשר מניב גם יעילות וגם שלמות.
במונח מכני רִכּוּך הוא תהליך של התקשות מתכת או זכוכית לטמפרטורה גבוהה ואז קירור הדרגתי, כך שזה מאפשר למתכת להגיע למצב גבישי באנרגיה נמוכה. אותו תהליך משמש בחישול מדומה שבו האלגוריתם בוחר מהלך אקראי, במקום לבחור את המהלך הטוב ביותר. אם המהלך האקראי משפר את המצב, אז הוא הולך באותו נתיב. אחרת, האלגוריתם עוקב אחר הנתיב שיש לו הסתברות של פחות מ-1 או שהוא נע במורד ובוחר נתיב אחר.