streamalism.org

1. סקירה כללית

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

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

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

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

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

2.1. עצים

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

• פוצץ את הצומת הראשון מהתור
• אם הצומת הזה הוא אותו אנו מחפשים, החיפוש הסתיים
• אחרת, הוסף את ילדי הצומת לסוף התור וחזור על השלבים

סיום הביצוע מובטח על ידי היעדר מחזורים. נראה כיצד לנהל מחזורים בחלק הבא.

2.2. גרפים

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

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

3. יישום בג'אווה

כעת, לאחר שהתיאוריה סוקרה, בואו נכניס את היד לקוד וניישם את האלגוריתמים הללו בג'אווה!

3.1. עצים

ראשית, אנו מיישמים את אלגוריתם העץ. בואו נעצב את שלנו עֵץ כיתה, המורכבת מערך וילדים המיוצגים על ידי רשימה של אחרים עֵץs:

עץ קלאסי ציבורי {ערך T פרטי; רשימה פרטית יְלָדִים; עץ פרטי (ערך T) {this.value = value; this.children = ArrayList חדש (); } עץ סטטי ציבורי של (ערך T) {החזרת עץ חדש (ערך); } ציבורי עץ addChild (ערך T) {עץ newChild = עץ חדש (ערך); ילדים. להוסיף (newChild); להחזיר newChild; }}

כדי להימנע מיצירת מחזורים, הילדים נוצרים על ידי הכיתה עצמה, על סמך ערך נתון.

לאחר מכן, בוא נספק א לחפש() שיטה:

סטטי ציבורי אופציונלי חיפוש (ערך T, שורש עץ) {// ...}

כפי שהזכרנו קודם, האלגוריתם של BFS משתמש בתור כדי לחצות את הצמתים. קודם כל, אנו מוסיפים את שלנו שורש צומת לתור זה:

תוֹר תור = ArrayDeque חדש (); queue.add (שורש);

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

בעוד (! queue.isEmpty ()) {Tree currentNode = queue.remove (); }

אם הצומת הזה הוא אותו אנו מחפשים, אנו מחזירים אותו, אחרת אנו מוסיפים את ילדיו לתור:

אם (currentNode.getValue (). שווה (ערך)) {return Optional.of (currentNode); } אחר {queue.addAll (currentNode.getChildren ()); }

לבסוף, אם ביקרנו בכל הצמתים מבלי למצוא את זה אותו אנו מחפשים, אנו מחזירים תוצאה ריקה:

החזרה Optional.empty ();

בואו נדמיין כעת מבנה עץ לדוגמא:

מה שמתורגם לקוד Java:

שורש העץ = Tree.of (10); עץ rootFirstChild = root.addChild (2); עץ depthMostChild = rootFirstChild.addChild (3); עץ rootSecondChild = root.addChild (4);

ואז, אם נחפש את הערך 4, אנו מצפים שהאלגוריתם יחצה את הצמתים עם הערכים 10, 2 ו -4, בסדר זה:

BreadthFirstSearchAlgorithm.search (4, שורש)

אנו יכולים לאמת שעם רישום הערך של הצמתים שביקרתם:

[main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - צומת ביקור עם ערך: 10 [main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - צומת מבוקרת עם ערך: 2 [main] INFO c.b.a.b.BreadthFirstSearchAlgorithm - צופה שנצפה עם ערך: 4

3.2. גרפים

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

צומת מחלקה ציבורית {ערך T פרטי; סט פרטי שכנים; צומת ציבורי (ערך T) {this.value = value; this.neighbors = HashSet חדש (); } connect public void (Node node) {if (this == node) לזרוק IllegalArgumentException חדש ("לא יכול לחבר את הצומת לעצמו"); this.neighbors.add (צומת); node.neighbors.add (זה); }}

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

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

קודם כל, בואו נעשה שימוש חוזר באלגוריתם מלמעלה, המותאם למבנה החדש:

סטטי ציבורי אופציונלי חיפוש (ערך T, התחלת צומת) {תור תור = ArrayDeque חדש (); queue.add (התחל); צומת currentNode; בעוד (! queue.isEmpty ()) {currentNode = queue.remove (); אם (currentNode.getValue (). שווה (ערך)) {return Optional.of (currentNode); } אחר {queue.addAll (currentNode.getNeighbors ()); }} להחזיר Optional.empty (); }

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

בעוד (! queue.isEmpty ()) {currentNode = queue.remove (); LOGGER.info ("צומת ביקור עם ערך: {}", currentNode.getValue ()); אם (currentNode.getValue (). שווה (ערך)) {return Optional.of (currentNode); } אחר {alreadyVisited.add (currentNode); queue.addAll (currentNode.getNeighbors ()); queue.removeAll (alreadyVisited); }} להחזיר Optional.empty ();

כפי שאנו רואים, ראשית אנו מאתחלים את מַעֲרֶכֶת שיכיל את הצמתים שביקרו בהם.

מַעֲרֶכֶת alreadyVisited = HashSet חדש ();

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

alreadyVisited.add (currentNode);

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

queue.removeAll (alreadyVisited);

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

בואו נראה איך זה עובד דרך דוגמא. קודם כל נגדיר גרף עם מחזור:

ואותו דבר בקוד Java:

התחלת צומת = צומת חדש (10); צומת firstNeighbor = צומת חדש (2); start.connect (firstNeighbor); צומת firstNeighborNeighbor = צומת חדש (3); firstNeighbor.connect (firstNeighborNeighbor); firstNeighborNeighbor.connect (התחל); צומת secondNeighbor = צומת חדש (4); start.connect (secondNeighbor);

בואו נגיד שוב שאנחנו רוצים לחפש את הערך 4. מכיוון שאין צומת שורש, אנו יכולים להתחיל את החיפוש בכל צומת שנרצה, ונבחר firstNeighborNeighbor:

BreadthFirstSearchAlgorithm.search (4, firstNeighborNeighbor);

שוב, נוסיף יומן כדי לראות אילו צמתים מבקרים, ואנו מצפים שהם יהיו 3, 2, 10 ו -4, רק פעם אחת בכל סדר זה:

[main] INFO cbabBreadthFirstSearchAlgorithm - צומת מבוקרת עם ערך: 3 [main] INFO cbabBreadthFirstSearchAlgorithm - צומת שנצפתה עם ערך: 2 [main] INFO cbabBreadthFirstSearchAlgorithm - צומת מבוקרת עם ערך: 10 [main] INFO cfabbread : 4

3.3. מוּרכָּבוּת

עכשיו כשסקרנו את שני האלגוריתמים בג'אווה, בואו נדבר על מורכבות הזמן שלהם. נשתמש בסימון Big-O כדי לבטא אותם.

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

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

בואו נשקול נ מספר הצמתים ו- ג מספר החיבורים של הגרף. ואז, במקרה הגרוע ביותר (בהיותנו לא נמצא צומת), אנו עשויים להשתמש הוסף הכל() ו להסיר את כל() שיטות להוסיף ולהסיר צמתים עד למספר החיבורים, מה שנותן לנו O (c) מורכבות לפעולות אלה. אז בתנאי שזה c> n, המורכבות של האלגוריתם הכולל תהיה O (c). אחרת זה יהיה עַל). זה מצוין בדרך כלל O (n + c), שניתן לפרש כמורכבות בהתאם למספר הגדול ביותר בין נ ו ג.

מדוע לא הייתה לנו בעיה זו לחיפוש העצים? מכיוון שמספר החיבורים בעץ מוגבל במספר הצמתים. מספר החיבורים בעץ של נ צמתים הוא n - 1.

4. מסקנה

במאמר זה למדנו על האלגוריתם Breadth-First Search וכיצד ליישם אותו ב- Java.

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

כרגיל, הקוד זמין ב- GitHub.