דוגמה לאלגוריתם טיפוס גבעה בג'אווה

1. סקירה כללית

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

2. ליצור אלגוריתם ולבדוק אותו

זו טכניקה מאוד פשוטה המאפשרת לנו לאלגוריתם למצוא פתרונות:

  1. הגדר את המצב הנוכחי כמצב התחלתי
  2. החל כל פעולה אפשרית במצב הנוכחי וצור פיתרון אפשרי
  3. השווה פתרון חדש שנוצר עם מצב היעד
  4. אם המטרה מושגת או שלא ניתן ליצור מדינות חדשות, צא. אחרת, חזור לשלב 2

זה עובד טוב מאוד עם בעיות פשוטות. מכיוון שמדובר בחיפוש ממצה, אין זה אפשרי לשקול זאת תוך כדי התמודדות עם מרחבים בעייתיים גדולים. זה ידוע גם כאלגוריתם של המוזיאון הבריטי (מנסה למצוא חפץ במוזיאון הבריטי על ידי חקירה אקראית).

זהו גם הרעיון המרכזי העומד מאחורי התקפת טיפוס הגבעה בעולם הביומטריה. גישה זו יכולה לשמש ליצירת נתונים ביומטריים סינתטיים.

3. מבוא לאלגוריתם פשוט טיפוס לגבעה

בטכניקה של טיפוס גבעה, החל מבסיס גבעה, אנו הולכים למעלה עד שנגיע לראש הגבעה. במילים אחרות, אנו מתחילים במצב התחלתי ואנחנו ממשיכים לשפר את הפתרון עד שהוא מיטבי.

זוהי וריאציה של אלגוריתם ייצור ובדיקה אשר זורק את כל המדינות שאינן נראות מבטיחות או שנראות כאילו לא יובילו אותנו למצב היעד. כדי לקבל החלטות כאלה, היא משתמשת ביוריסטיקה (פונקציית הערכה) המציינת עד כמה המצב הנוכחי קרוב למצב היעד.

במילים פשוטות, טיפוס גבעה = ליצור-ולבדוק + היוריסטיקה

בואו נסתכל על אלגוריתם הטיפוס של Simple Hill:

  1. הגדר את המצב הנוכחי כמצב התחלתי
  2. לולאה עד להשגת מצב היעד או שלא ניתן להחיל אופרטורים נוספים על המצב הנוכחי:
    1. החל פעולה על המצב הנוכחי להשיג מדינה חדשה
    2. לְהַשְׁווֹת את המדינה החדשה עם המטרה
    3. לְהַפְסִיק אם מצב היעד מושג
    4. הערך מצב חדש עם פונקציה יוריסטית ו להשוות את זה למצב הנוכחי
    5. אם המדינה החדשה יותר קרובה למטרה בהשוואה למצב הנוכחי, עדכן את המצב הנוכחי

כפי שאנו רואים, הוא מגיע למצב היעד עם שיפורים איטרטיביים. באלגוריתם של טיפוס גבעה, מציאת המטרה שווה ערך להגיע לראש הגבעה.

4. דוגמא

ניתן לסווג את האלגוריתם לטיפוס גבעה כחיפוש מושכל. כך שנוכל ליישם כל חיפוש מבוסס צומת או בעיות כמו בעיית n-queens באמצעותו. כדי להבין את המושג בקלות, ניקח דוגמה מאוד פשוטה.

בואו נסתכל על התמונה למטה:

נקודת המפתח בעת פיתרון כל בעיה בטיפוס גבעה היא בחירת פונקציה יוריסטית מתאימה.

בואו נגדיר פונקציה כזו h:

h (x) = +1 לכל הבלוקים במבנה התמיכה אם הבלוק ממוקם כראוי אחרת -1 לכל הבלוקים במבנה התמיכה.

כאן, אנו נקרא לכל בלוק הממוקם כהלכה אם יש לו מבנה תמיכה זהה למצב המטרה. לפי נוהל טיפוס הגבעה שנדון קודם לכן בואו נסתכל על כל האיטרציות והיוריסטיות שלהם להגיע למצב היעד:

5. יישום

עכשיו, בואו נשתמש באותה דוגמא באמצעות האלגוריתם Hill-Climbing.

קודם כל, אנחנו צריכים א מדינה מחלקה שתאחסן את רשימת הערימות המייצגות מיקומי בלוקים בכל מדינה. זה יאחסן גם את היוריסטיקה עבור אותה מדינה מסוימת:

מדינה ציבורית (מדינה פרטית) מדינה; היוריסטיקה פרטית; // בונה העתקות, מגדירים וגטרים}

אנו זקוקים גם לשיטה שתחשב את הערך היוריסטי של המדינה.

public int getHeuristicsValue (רשימה currentState, Stack goalStateStack) {HeeristicValue שלם; heuristicValue = currentState.stream () .mapToInt (stack -> {return getHeuristicsValueForStack (stack, currentState, goalStateStack);}). sum (); החזר heuristicValue; } public int getHeuristicsValueForStack (מחסנית מחסנית, רשימה currentState, Stack goalStateStack) {int stackHeuristics = 0; בוליאני isPositioneCorrect = נכון; int goalStartIndex = 0; עבור (String currentBlock: stack) {if (isPositioneCorrect && currentBlock.equals (goalStateStack.get (goalStartIndex))) {stackHeuristics + = goalStartIndex; } אחר {stackHeuristics - = goalStartIndex; isPositioneCorrect = false; } goalStartIndex ++; } להחזיר stackHeuristics; } 

יתר על כן, עלינו להגדיר שיטות אופרטור שיעניקו לנו מדינה חדשה. לדוגמא שלנו נגדיר שתיים משיטות אלה:

  1. פוצץ בלוק מערימה ודחף אותו לערימה חדשה
  2. פתח גוש מערימה ודחף אותו לאחת הערימות האחרות
מדינה פרטית pushElementToNewStack (רשימה currentStackList, חסימת מחרוזות, int currentStateHeuristics, Stack goalStateStack) {State newState = null; מחסנית newStack = מחסנית חדשה (); newStack.push (חסום); currentStackList.add (newStack); int newStateHeuristics = getHeuristicsValue (currentStackList, goalStateStack); אם (newStateHeuristics> currentStateHeuristics) {newState = מדינה חדשה (currentStackList, newStateHeuristics); } אחר {currentStackList.remove (newStack); } להחזיר newState; }
מדינה פרטית pushElementToExistingStacks (מחסנית currentStack, רשימה currentStackList, Block String, int currentStateHeuristics, Stack goalStateStack) {return currentStackList.stream () .filter (stack -> stack! = currentStack) .map (stack -> {return pushElementToStack (stack, block, currentStackList, currentStateHeuristics, goalStateStack); }) .filter (אובייקטים :: nonNull) .findFirst () .orElse (null); } pushElementToStack של מדינה פרטית (מחסנית מחסנית, חסימת מחרוזות, רשימה currentStackList, int currentStateHeuristics, Stack goalStateStack) {stack.push (חסום); int newStateHeuristics = getHeuristicsValue (currentStackList, goalStateStack); אם (newStateHeuristics> currentStateHeuristics) {להחזיר מדינה חדשה (currentStackList, newStateHeuristics); } stack.pop (); החזר אפס; }

עכשיו, כשיש לנו את שיטות העוזר שלנו, בואו נכתוב שיטה ליישום טכניקת טיפוס גבעה.

פה, אנו ממשיכים לחשב מדינות חדשות הקרובות יותר למטרות מקודמותיהן. אנו ממשיכים להוסיף אותם בדרכנו עד שנגיע למטרה.

אם לא נמצא מצבים חדשים, האלגוריתם מסתיים עם הודעת שגיאה:

רשימה ציבורית getRouteWithHillClimbing (Stack initStateStack, Stack goalStateStack) זורק Exception {// instantiate initState with initStateStack // ... List resultPath = new ArrayList (); resultPath.add (מדינה חדשה (initState)); ציין currentState = initState; noStateFound בוליאני = שקר; בזמן (! currentState.getState (). get (0) .equals (goalStateStack) || noStateFound) {noStateFound = true; ציין nextState = findNextState (currentState, goalStateStack); אם (nextState! = null) {noStateFound = false; currentState = nextState; resultPath.add (מדינה חדשה (nextState)); }} להחזיר resultPath; }

בנוסף לכך, אנחנו גם צריכים findNextState שיטה המשתמשת בכל הפעולות האפשריות במצב הנוכחי כדי לקבל את המצב הבא:

public state findNextState (State currentState, Stack goalStateStack) {List listOfStacks = currentState.getState (); int currentStateHeuristics = currentState.getHeuristics (); listlistOfStacks.stream () .map (stack -> {return applyOperationsOnState (listOfStacks, stack, currentStateHeuristics, goalStateStack);}) .filter (Objects :: nonNull) .findFirst () .orElse (null); } מדינה ציבורית להחיל OperationsOnState (רשימה listOfStacks, Stack stack, int currentStateHeuristics, Stack goalStateStack) {State tempState; רשימה tempStackList = ArrayList חדש (listOfStacks); בלוק מחרוזת = stack.pop (); אם (stack.size () == 0) tempStackList.remove (stack); tempState = pushElementToNewStack (tempStackList, block, currentStateHeuristics, goalStateStack); אם (tempState == null) {tempState = pushElementToExistingStacks (stack, tempStackList, block, currentStateHeuristics, goalStateStack); stack.push (חסום); } להחזיר tempState; }

6. אלגוריתם טיפוס גבעה בעלייה תלולה ביותר

אלגוריתם טיפוס גבעה בעלייה תלולה (חיפוש שיפוע) הוא גרסה של אלגוריתם טיפוס גבעה. אנו יכולים ליישם את זה בשינויים קלים באלגוריתם הפשוט שלנו. באלגוריתם זה אנו שקול את כל המדינות האפשריות מהמצב הנוכחי ואז בחר את הטוב ביותר כיורששלא כמו בטכניקת טיפוס הגבעה הפשוטה.

במילים אחרות, במקרה של טכניקת טיפוס גבעה בחרנו בכל מדינה כממשיכה שהייתה קרובה יותר למטרה מאשר למצב הנוכחי ואילו באלגוריתם טיפוס הגבעה Steepest-Ascent, אנו בוחרים את היורש הטוב ביותר מבין כל היורשים האפשריים ואז מעדכנים המצב הנוכחי.

7. חסרונות

טיפוס גבעה היא טכניקה קצרת רואי שכן היא מעריכה רק אפשרויות מיידיות. כך שהוא עלול להסתיים במצבים ספורים מהם הוא לא יכול לבחור מדינות נוספות. בואו נסתכל על מצבים אלה וכמה פתרונות עבורם:

  1. מקסימום מקומי: זו מדינה שהיא טובה יותר מכל השכנים, אך קיימת מדינה טובה יותר והיא רחוקה מהמצב הנוכחי; אם המקסימום המקומי מתרחש בטווח הראייה של הפתרון, הוא מכונה "הגבעות"
  2. מִישׁוֹר: במצב זה, לכל המדינות השכנות יש ערכי היוריסטיקה זהים, ולכן לא ברור לבחור במדינה הבאה על ידי עריכת השוואות מקומיות
  3. רֶכֶס: זהו אזור הגבוה מהמדינות הסובבות אותו, אך לא ניתן להגיע אליו בצעד אחד; לדוגמא, יש לנו ארבעה כיוונים אפשריים לחקור (N, E, W, S) ואזור קיים בכיוון NE

ישנם מעט פתרונות להתגברות על מצבים אלה:

  1. אנחנו יכולים לַחֲזוֹר עַל עִקבוֹתָיו לאחת המדינות הקודמות ולחקור כיוונים אחרים
  2. אנחנו יכולים לדלג על כמה מדינות ולעשות קְפִיצָה בכיוונים חדשים
  3. אנחנו יכולים לחקור כמה כיוונים כדי להבין את הדרך הנכונה

8. מסקנה

למרות שטכניקת טיפוס הגבעה טובה בהרבה מחיפוש ממצה, היא עדיין לא אופטימלית במרחבים בעייתיים גדולים.

אנחנו תמיד יכולים לקודד מידע גלובלי לפונקציות היוריסטיות כדי לקבל החלטות חכמות יותר, אבל אז המורכבות החישובית תהיה הרבה יותר גבוהה ממה שהיה קודם.

אלגוריתם טיפוס על גבעות יכול להועיל מאוד כשמגדירים אותו בטכניקות אחרות. כמו תמיד, ניתן למצוא את הקוד השלם לכל הדוגמאות ב- GitHub.