הצגת המקור של הדף "חיפוש מקומי"

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

שיטת החיפוש המקומי לא תמיד תפיק [[פתרון אופטימלי]], אך לעיתים קרובות תיצור [[אלגוריתם קירוב]] לבעיה הנתונה ותרוץ בזמן סביר, מה שגורם לכך שפעמים רבות בוחרים בשיטה כזו עבור בעיות [[NP-קשיות|NP קשות]].{{הערה|[http://www.designofapproxalgs.com/book.pdf the desine of approximation algorithms], david p. williamson, david b.  fhmoys, pg 35|כיוון=שמאל}}

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

==אלגוריתם hill-climbing==

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

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

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

==אלגוריתמים גנטיים==
{{ערך מורחב|אלגוריתמים גנטיים}}

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

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

{{ערך מורחב|Gradient descent}}
עבור התכנסות אל מינימום מקומי במרחב עבור פונקציה נתונה, ניתן להגריל נקודה כלשהי בפונקציה, וללכת לאט לכיוון ההפוך מה[[גרדיאנט]].

==דוגמאות ==
=== בעיית כיסוי קודקודים ===
{{ערך מורחב|בעיית כיסוי קודקודים}}

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

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

=== בעיית הספיקות ===
{{ערך מורחב|בעיית הספיקות}}

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

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

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

*[https://webcourse.cs.technion.ac.il/236501/Winter2011-2012/ho/WCFiles/local-search.pdf אלגוריתמים לחיפוש יוריסטי מקומי], [[שאול מרקוביץ]], [[טכניון]].
==הערות שוליים==
{{הערות שוליים}}
[[קטגוריה:אלגוריתמי חיפוש]]
[[קטגוריה:אופטימיזציה בדידה]]