כל מה שאתה צריך לדעת על רוחב אלגוריתם החיפוש הראשון

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

כדי לקבל ידע מעמיק בנושא בינה מלאכותית ולמידת מכונה, אתה יכול להירשם לשידור חי מאת אדוריקה עם תמיכה 24/7 וגישה לכל החיים.

הנה רשימה של נושאים שיהיו מכוסה בבלוג זה:

1. מבוא לחציית גרפים
2. מהו החיפוש רוחב ראשון?
3. הבנת האלגוריתם Breadth-First Search עם דוגמה
4. רוחב-אלגוריתם חיפוש פסאודוקוד
5. יישומים של חיפוש רוחב ראשון

מבוא לחציית גרפים

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

זה נשמע פשוט! אבל יש מלכוד.

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

מהו האלגוריתם לחיפוש רוחב ראשון?

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

מיזוג קוד מקור + ++

לפני שנתקדם ונבין את החיפוש 'רוחב ראשון' בדוגמה, בואו נכיר שני מונחים חשובים הקשורים לחציית גרפים:

1. ביקור בצומת: בדיוק כמו שהשם מרמז, ביקור בצומת פירושו לבקר או לבחור צומת.
2. חקר צומת: לחקור את צמתים סמוכים (צמתים צאצאים) של צומת נבחר.

עיין באיור לעיל כדי להבין זאת טוב יותר.

הבנת האלגוריתם לחיפוש רוחב ראשון

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

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

תור הוא מבנה נתונים מופשט שעוקב אחר מתודולוגיית First-in-First-Out (תחילה ייגשו לנתונים שהוכנסו ראשונים). הוא פתוח בשני הקצוות, כאשר קצה אחד משמש תמיד להכנסת נתונים (enqueue) והשני משמש להסרת נתונים (dequeue).

עכשיו בואו נסתכל על הצעדים הכרוכים במעבר גרף באמצעות חיפוש רוחב ראשון:

שלב 1: קח תור ריק.

שלב 2: בחר צומת התחלה (ביקור בצומת) והכנס אותו לתור.

שלב 3: בתנאי שהתור אינו ריק, חילץ את הצומת מהתור והכנס את צמתי הצאצא שלו (חקר צומת) לתור.

שלב 4: הדפיס את הצומת שחולץ.

אל תדאג אם אתה מבולבל, נבין זאת עם דוגמא.

הפעל שאילתת כוורת משורת הפקודה

התבונן בגרף שלמטה, נשתמש באלגוריתם החיפוש הראשון-רוחב כדי לחצות את הגרף.

במקרה שלנו, נקצה את הצומת 'a' כצומת השורש ונתחיל לחצות כלפי מטה ונקיים את השלבים שהוזכרו לעיל.

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

1. הקצה 'a' כצומת השורש והכנס אותו לתור.
2. חילץ את הצומת 'a' מהתור והכנס את צמתי הילד של 'a', כלומר 'b' ו- 'c'.
3. הדפסת צומת 'א'.
4. התור אינו ריק ויש בו צומת 'b' ו- 'c'. מכיוון ש- 'b' הוא הצומת הראשון בתור, נחלץ אותו ונכניס את צמתי הילד של 'b', כלומר, צומת 'd' ו- 'e'.
5. חזור על שלבים אלה עד שהתור מתרוקן. שים לב כי אין להוסיף את הצמתים שכבר ביקר בתור שוב.

עכשיו בואו נסתכל על הפסאוד-קוד של אלגוריתם החיפוש הראשון.

רוחב-אלגוריתם חיפוש פסאודוקוד

הנה הפסאוד-קוד ליישום האלגוריתם לחיפוש רוחב ראשון:

קלט: s כצומת המקור BFS (G, s) מאפשר ל- Q להיות תור. Q. Enqueue (s) סמן s כביקור בזמן ש (Q אינו ריק) v = Q. dequeue () לכל השכנים w of v בגרף G אם w לא ביקרו Q.

בקוד לעיל, השלבים הבאים מבוצעים:

1. (G, s) הוא קלט, כאן G הוא הגרף ו- s הוא צומת השורש
2. תור 'Q' נוצר ומאותחל עם צומת המקור 's'
3. כל צמתי הילד של 's' מסומנים
4. חלץ 's' מהתור ובקר בצמתים של הילד
5. עבד את כל צמתי הילד של v
6. מאחסן w (צמתים לילד) ב- Q כדי לבקר בהמשך את צמתי הילד שלה
7. המשך עד 'Q' ריק

לפני שנסכם את הבלוג, בואו נסתכל על כמה יישומים של אלגוריתם Breadth-First Search.

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

חיפוש רוחב ראשון הוא שיטת מעבר גרף פשוטה שיש לה מגוון יישומים מפתיע. להלן מספר דרכים מעניינות בהן נעשה שימוש בחיפוש ראשון-לחם:

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

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

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

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

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

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

3. מבוא לשרשרות מרקוב עם דוגמאות - מרקוב שרשראות עם פיתון

עם זה, אנו מגיעים לסוף הבלוג הזה. אם יש לך שאלות בנוגע לנושא זה, השאיר תגובה למטה ונחזור אליך.

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