חיפוש מקומי

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

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

דוגמאות

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

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

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

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

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

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

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

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