חיפוש מקומי

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

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

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

אלגוריתם hill-climbing

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

שיפורים אפשריים לאלגוריתם זה הם:

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

אלגוריתם simulate anealing

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

אלגוריתמים גנטיים

ערך מורחב – אלגוריתמים גנטיים

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

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

ערך מורחב – Gradient descent

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

דוגמאות

בעיית כיסוי קודקודים

ערך מורחב – בעיית כיסוי קודקודים

בהינתן גרף $\ G=(V,E)$ (המורכב מאוסף קודקודים $\ V$ ואוסף קשתות $\ E$ המחברות ביניהם), ברצוננו למצוא קבוצת קודקודים $\ U\subseteq V$ בגודל מינימלי, כך שאחד מצדיה של כל קשת יהיה שייך לה.

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

בעיית הספיקות

ערך מורחב – בעיית הספיקות

בבעיית הספיקות, נתון אוסף פסוקיות מעל לאוסף משתנים בוליאניים $\ V$ (פסוקית היא אוסף ליטרלים (ליטרל הוא משתנה או שלילתו). פסוקית מסופקת אם אחד הליטרלים שלה מסופק), ויש למצוא השמת ערכי אמת ($\ False$\$\ True$), עבורה יסופק מספר מרבי של פסוקיות.

ניתן ליישם חיפוש מקומי עבור בעיה זו על ידי בחירת השמת ערכי אמת שרירותית (למשל, השמת $\ True$ בכל המשתנים), והחלפת ערכו של משתנה אחד מדי איטרציה, עד להגעה להשמת ערכי אמת מיטבית מקומית (כזו, שהיפוך ערך האמת של כל אחד ממשתניה יקטין את מספר הפסוקיות המסופקות). ניתן להוכיח שאלגוריתם זה נותן קירוב-$\ {\frac {1}{2}}$ לכל הפחות, ומספר האיטרציות שיתבצעו קטן או שווה למספר הפסוקיות בנוסחה (ולכן, חסום ליניארית על ידי גודל הקלט).

קישורים חיצוניים

• אלגוריתמים לחיפוש יוריסטי מקומי, שאול מרקוביץ, טכניון.