חיפוש מקומי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

דוגמאות[עריכת קוד מקור | עריכה]

בעיית כיסוי קודקודים[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – בעיית כיסוי קודקודים

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

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

בעיית הספיקות[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – בעיית הספיקות

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

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