אלגוריתם חיפוש לרוחב – הבדלי גרסאות

מתוך ויקיפדיה, האנציקלופדיה החופשית
תוכן שנמחק תוכן שנוסף
Luckas-bot (שיחה | תרומות)
Luckas-bot (שיחה | תרומות)
מ r2.7.1) (בוט מוסיף: lv:Meklēšana plašumā (grafu teorija)
שורה 49: שורה 49:
[[ko:너비 우선 탐색]]
[[ko:너비 우선 탐색]]
[[lt:Paieška į plotį]]
[[lt:Paieška į plotį]]
[[lv:Meklēšana plašumā (grafu teorija)]]
[[nl:Breedte-eerst zoeken]]
[[nl:Breedte-eerst zoeken]]
[[no:Bredde-først-søk]]
[[no:Bredde-først-søk]]

גרסה מ־10:19, 13 באוקטובר 2011

סדר סריקת הקודקודים בחיפוש לרוחב

אלגוריתם חיפוש לרוחב (אנגלית: Breadth-first search, ראשי תיבות: BFS) הוא אלגוריתם המשמש למעבר על צמתי גרף, לרוב תוך חיפוש צומת המקיים תכונה מסוימת. צומת כלשהו בגרף נקבע להיות הצומת ההתחלתי , והאלגוריתם עובר על כל הצמתים במרחק צלע אחת מ, ואז על כל הצמתים במרחק 2 צלעות מ וכן הלאה . צורת חיפוש זו היא חיפוש לרוחב הגרף, בניגוד לחיפוש לעומק הגרף.

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

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

סיבוכיות הזמן והמקום של האלגוריתם היא

תיאור אינטואיטיבי

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

תיאור פורמלי

קטע הקוד הבא הוא פסאודו קוד.

 function breadthFirstSearch (Start, Goal) { 
     enqueue(Queue,Start)
     while notEmpty(Queue)) {
         Node := dequeue(Queue)
         if Node = Goal {
             return Node
         }
         for each Child in Expand(Node) {
             if notVisited(Child) {
                 setVisited(Child)
                 enqueue(Queue, Child)
             }
         }
     }
 }