streamalism.org

1. הקדמה

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

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

בהינתן מבוך כזה, אנו רוצים למצוא נתיב מכניסה ליציאה.

2. דוגמנות המבוך

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

• 0 -> כביש
• 1 -> קיר
• 2 -> כניסה למבוך
• 3 -> יציאת מבוך
• 4 -> חלק תא של הנתיב מהכניסה ליציאה

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

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

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

בואו נגדיר את חתימת השיטה:

רשימה ציבורית לפתור (מבוך מבוך) {}

הקלט לשיטה הוא א מבוך, המכיל את מערך הדו-ממד, עם מוסכמות שמות שהוגדרה לעיל.

תגובת השיטה היא רשימת צמתים, המהווה נתיב מצומת הכניסה לצומת היציאה.

3. Backtracker רקורסיבי (DFS)

3.1. אַלגוֹרִיתְם

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

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

ניתן לתאר אלגוריתם זה כ:

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

בואו נשתמש באלגוריתם הזה על המבוך שמוצג באיור -1 (א), כאשר S היא נקודת ההתחלה, ו- E היא היציאה.

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

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

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

3.2. יישום

בואו נראה עכשיו את יישום Java:

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

פרטי סטטי פרטי [] [] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; 

אנו זקוקים גם לשיטת שירות שתוסיף שני קואורדינטות:

פרטי קואורדינטות getNextCoordinate (int שורה, int col, int i, int j) {להחזיר Coordinate חדש (שורה + i, col + j); }

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

רשימה ציבורית לפתור (מבוך מבוך) {נתיב רשימה = ArrayList חדש (); אם (חקירה (מבוך, מבוך. getEntry (). getX (), מבוך. getEntry (). getY (), נתיב)) {נתיב חזרה; } להחזיר Collections.emptyList (); }

בואו נגדיר את לַחקוֹר השיטה המוזכרת לעיל. אם יש נתיב אז חזור נכון, עם רשימת הקואורדינטות בטיעון נָתִיב. לשיטה זו יש שלושה חסימות עיקריות.

ראשית, אנו משליכים צמתים לא חוקיים כלומר הצמתים שנמצאים מחוץ למבוך או שהם חלק מהקיר. לאחר מכן, אנו מסמנים את הצומת הנוכחי כביקור, כך שלא נבקר באותו צומת שוב ושוב.

לבסוף, אנו נעים רקורסיבית לכל הכיוונים אם היציאה לא נמצאת:

חקירה בוליאנית פרטית (מבוך מבוך, שורה int, int col, נתיב רשימה) {if (! maze.isValidLocation (row, col) || maze.isWall (שורה, col) || maze.isExplored (שורה, col)) { להחזיר כוזב; } path.add (קואורדינטות חדש (שורה, קול)); maze.setVisited (שורה, קול, נכון); if (maze.isExit (row, col)) {return true; } עבור (int [] כיוון: DIRECTIONS) {קואורדינטות קואורדינטות = getNextCoordinate (שורה, עמודה, כיוון [0], כיוון [1]); אם (לחקור (מבוך, coordinate.getX (), coordinate.getY (), נתיב)) {להחזיר נכון; }} path.remove (path.size () - 1); להחזיר כוזב; }

פתרון זה משתמש בגודל הערימה עד לגודל המבוך.

4. וריאנט - הנתיב הקצר ביותר (BFS)

4.1. אַלגוֹרִיתְם

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

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

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

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

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

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

4.2. יישום

מאפשר כעת ליישם את האלגוריתם הזה ב- Java. אנו נשתמש שוב ב הוראות משתנה שהוגדר בסעיף הקודם.

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

backtrackPath של רשימה פרטית (cur koordination) {נתיב רשימה = ArrayList חדש (); תיאום איטר = cur; ואילו (iter! = null) {path.add (iter); iter = iter.parent; } דרך חזרה; }

בואו נגדיר כעת את שיטת הליבה לִפְתוֹר. נשתמש שוב בשלושת הבלוקים המשמשים בהטמעת DFS כלומר לאמת את הצומת, לסמן את הצומת שביקרנו ולעבור את הצמתים הסמוכים.

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

רשימת ציבורי לפתור (מבוך מבוך) {LinkedList nextToVisit = חדש LinkedList (); התחל לתאם = maze.getEntry (); nextToVisit.add (התחל); while (! nextToVisit.isEmpty ()) {Coordinate cur = nextToVisit.remove (); אם (! maze.isValidLocation (cur.getX (), cur.getY ()) || maze.isExplored (cur.getX (), cur.getY ())) {המשך; } אם (maze.isWall (cur.getX (), cur.getY ())) {maze.setVisited (cur.getX (), cur.getY (), true); לְהַמשִׁיך; } אם (maze.isExit (cur.getX (), cur.getY ())) {return backtrackPath (cur); } עבור (int [] כיוון: DIRECTIONS) {קואורדינטות קואורדינטות = קואורדינטות חדשות (cur.getX () + כיוון [0], cur.getY () + כיוון [1], cur); nextToVisit.add (קואורדינטות); maze.setVisited (cur.getX (), cur.getY (), נכון); }} להחזיר Collections.emptyList (); }

5. מסקנה

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

לקריאה נוספת, חפש שיטות אחרות לפתרון מבוך, כמו אלגוריתם A * ו- Dijkstra.

כמו תמיד, ניתן למצוא את הקוד המלא ב- GitHub.