היוריסטיקה קבילה

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

אלגוריתמים לחיפוש

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

$f(n)=g(n)+h(n)$

כאשר

$n$ = הצומת הנוכחי.

$f(n)$ = פונקציית העלות.

$g(n)$ = עלות המסלול מצומת ההתחלתי לצומת הנוכחי.

$h(n)$ = העלות משוערת מהצומת הנוכחי ליעד.

$h(n)$ היא בעצם הפונקציה ההיוריסטית. אם ההיוריסטיקה בלתי קבילה, אלגוריתם A* לא בהכרח יחזיר את הפתרון המיטבי לבעיית החיפוש, עקב הערכת יתר של $f(n)$ .

ניסוח פורמלי

$n$ הוא צומת

$h$ היא פונקציה היוריסטית

$h(n)$ הוא ההערכה של $h$ בנוגע לעלות הגעה למטרה מ-$n$

$h^{*}(n)$ הוא העלות המיטבית (מינימלית) של הגעה הגעה למטרה מ-$n$

$h(n)$ תקרא קבילה אמ"ם, $\forall n$

$h(n)\leq h^{*}(n)$

הפונקציה $h^{*}$ היא ההיוריסטיקה המיטבית, מאחר שהיא תמיד מעריכה את המחיר של צומת מסוים באופן מדויק, ולכן באלגוריתם A*, שימוש בה יוביל לפיתוח של כמות מינימלית של צמתים. לכן, פונקציות קבילות שקרובות יותר לפונקציה $h^{*}$ עדיפות. נאמר שפונקציה היוריסטית קבילה $h_{2}$ יותר מיודעת מפונקציה היוריסטית וקבילה $h_{1}$ אמ"ם, $\forall n$

$h_{1}(n)\leq h_{2}(n)\ \left[\ \leq h^{*}(n)\ \right]$

דוגמאות

חידת ה-15

שתי דוגמאות שונות להיוריסטיקה קבילה עבור בעיית פתירת חידת ה-15:

• מרחק המינג
• מרחק מנהטן

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

מרחק מנהטן של פאזל מסוים במצב $n$ מוגדר להיות:

$h(n)=\sum _{\text{all tiles}}{\mathit {distance}}({\text{tile, correct position}})$

כאשר הפונקציה ${\mathit {distance}}$ היא מרחק מנהטן בין שתי הלוחיות.

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

81	30	61	43
144	93	123	72
54	14	132	153
__	111	101	24

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

$h(n)=3+1+0+1+2+3+3+4+3+2+4+4+4+1+1=36$

בנייה

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

לדוגמה, עבור חידת ה-15 שראינו מקודם, נוכל להגדיר שלוש בעיות פשוטות יותר: האילוץ המקורי שמגדיר את המשחק הוא "לוחית יכולה לנוע ממיקום א' למיקום ב' אם מיקום א' צמוד למיקום ב', וגם מיקום ב' ריק".

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

1. לוחית יכולה לנוע ממיקום א' למיקום ב' אם מיקום א' צמוד למיקום ב'.
2. לוחית יכולה לנוע ממיקום א' למיקום ב' אם מיקום ב' ריק.
3. לוחית יכולה לנוע ממיקום א' למיקום ב'.

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

חישוב ואכסון פתרונות מדויקים לבעיות משנה גם יכול לשמש כדרך לבנות פונקציה היוריסטית: הרעיון הוא לחשב מראש את הפתרונות עבור כל התבניות ההתחלתיות. לדוגמה, עבור חידת ה-15, נוכל לחשב את כמות המהלכים המיטבית לפתרון הבעיה עבור כל המיקומים ההתחלתיים האפשריים של הלוחיות 1,2,3,4,5,9,13 ושל המקום הריק (אנחנו לא מניחים שהתאים האחרים ריקים - עדיין צריך לפעול על פי הכללים של לוח מלא, אנחנו פשוט לא מעוניינים בסידור של הלוחיות האחרות)

4	3	2	1
			5
			9
__			13

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

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

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

שימוש למציאת פתרון מיטבי

אלגוריתמי חיפוש (למשל אלגוריתם A*) יכולים להשתמש בהיוריסטיקה קבילה על מנת למצוא פתרון מיטבי. דוגמה ידועה וקלה להבנה היא אלגוריתם חיפוש לרוחב. במקרה זה, פונקציית ההערכה ההיוריסטית $h(n)$ שווה ל-$0$ עבור כל צומת $n$. ברור שהפונקציה ההיוריסטית נמוכה מהעלות בפועל. ההיוריסטיקה הזו תגרום לאלגוריתם לבחון את כל הנתיבים האפשריים ובסופו של דבר למצוא את הפתרון המיטבי (כלומר, הדרך הקצרה ביותר ליעד).

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

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

ברור שנתחיל לבקר בצומת האמצעי העליון, שכן העלות הכוללת הצפויה, כלומר $f(n)$, הוא $10+0=10$. ואז הצמתים המועמדים הם צומת היעד, עם $f(n)$ ששווה ל-$10+100+0=110$, והצומת התחתונה. אנחנו נבחר את הצמתים התחתונים בזה אחר זה, ורק לבסוף ביעד, עם העלות המעודכנת, שכן לכולם יש $f(n)$ נמוך מה-$f(n)$ של היעד, בהתחשב בדרך הנוכחית (העליונה). כלומר מאחר שה-$f(n)$ שלהם הוא $100,101,102,102$, אז אף על פי שצומת היעד היה מועמד, לא בחרנו בו כי עדיין היו דרכים טובות יותר. בדרך זו, היוריסטיקה קבילה יכולה להבטיח מיטביות.

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

הערות שוליים

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