streamalism.org

1. הקדמה

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

2. מהו אלגוריתם מסלולי דרך?

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

("מפת הרכבת התחתית תת קרקעית תת קרקעית של לונדון" מאת sameboat מורשית תחת CC BY-SA 4.0)

יש לזה הרבה מרכיבים מעניינים:

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

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

3. מה זה A *?

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

גם זיכרון וגם מורכבות ביצועים יכולים להיות O (b ^ d) במקרה הגרוע ביותר, למרות שזה תמיד יסתדר במסלול היעיל ביותר, זה לא תמיד הדרך היעילה ביותר לעשות זאת.

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

4. איך A * עובד?

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

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

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

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

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

בכל איטרציה, אנו:

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

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

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

4.1. דוגמא עובדת

לדוגמה, בואו נתחיל מ- "Marylebone" וננסה למצוא את הדרך ל "Street Bond".

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

התחנות הבאות שלנו יכולות להיות "דרך אדגוואר", בעלות של 0.4403 ק"מ, או "רחוב בייקר", בעלות של 0.4153 ק"מ. עם זאת, "דרך אדג'וור" בכיוון הלא נכון, כך שהיוריסט שלנו מכאן ליעד נותן ציון של 1.4284 ק"מ, ואילו ל"רחוב בייקר "יש ציון יוריסטי של 1.0753 ק"מ.

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

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

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

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

5. יישום ג'אווה

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

5.1. ייצוג הגרף

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

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

ממשק ציבורי GraphNode {String getId (); }

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

הגרף הכללי שלנו מיוצג אז על ידי מחלקה הנקראת בפשטות גרָף:

גרף בכיתה ציבורית {פרטיים סופיים קבעו צמתים; מפת גמר פרטית קשרים; ציבורי T getNode (מחרוזת מזהה) {return nodes.stream () .filter (node ​​-> node.getId (). equals (id)) .findFirst () .orElseThrow (() -> IllegalArgumentException ("לא נמצא צומת עם תְעוּדַת זֶהוּת")); } ציבורי הגדר getConnections (צומת T) {החזר חיבורים.גט (node.getId ()). זרם () .מפה (זה :: getNode) .collect (Collectors.toSet ()); }}

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

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

5.2. צעדים בדרך שלנו

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

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

ממשק ציבורי סקורר {כפול computeCost (T מ, T ל); }

בהתחלה וצומת סיום, נקבל ציון על נסיעה ביניהם.

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

מחלקה מיישמת RouteNode השוואה {זרם T פרטי סופי; פרטי T קודם; ציון מסלול כפול פרטי; אומדן כפול פרטי RouteNode (T הנוכחי) {this (הנוכחי, null, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY); } RouteNode (T הנוכחי, T הקודם, מסלול נתיב כפול, הערכה כפולה) {this.current = הנוכחי; this.previous = הקודם; this.routeScore = מסלול ציון; this.estimatedScore = estimatedScore; }}

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

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

@Override int intl publicTo (RouteNode אחר) {if (this.estimatedScore> other.estimatedScore) {return 1; } אחר אם (this.estimatedScore <other.estimatedScore) {return -1; } אחר {להחזיר 0; }}

5.3. למצוא את המסלול שלנו

כעת אנו יכולים ליצור את המסלולים שלנו לאורך הגרף שלנו. זו תהיה שיעור שנקרא RouteFinder:

RouteFinder בכיתה ציבורית {גרף גרף סופי פרטי; גמר פרטי סקורר nextNodeScorer; פרט הסופי סקורר targetScorer; רשימה ברשימה ציבורית findRoute (T from, T to) {throw new IllegalStateException ("לא נמצא מסלול"); }}

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

שיטה זו אמורה להיות אלגוריתם A * שלנו. כל שאר הקוד שלנו נכנס לשיטה זו.

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

תור openSet = PriorityQueue חדש (); מַפָּה allNodes = HashMap חדש (); RouteNode התחלה = RouteNode חדש (מ, null, 0d, targetScorer.computeCost (מ, ל)); openSet.add (התחל); allNodes.put (מ, התחל);

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

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

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

בעוד (! openSet.isEmpty ()) {RouteNode הבא = openSet.poll (); if (next.getCurrent (). שווה ל- (to)) {List route = ArrayList new (); RouteNode הנוכחי = הבא; לעשות {route.add (0, current.getCurrent ()); הנוכחי = allNodes.get (current.getPrevious ()); } בעוד (הנוכחי! = null); מסלול חזרה; } // ...

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

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

 graph.getConnections (next.getCurrent ()). forEach (חיבור -> {RouteNode nextNode = allNodes.getOrDefault (חיבור, RouteNode חדש (חיבור)); allNodes.put (חיבור, nextNode); כפול newScore = next.getRouteScore () + nextNodeScorer.computeCost (next.getCurrent (), חיבור); אם (newScore <nextNode.getRouteScore ()) {nextNode.setPrevious (next.getCurrent ()); nextNode.setRouteScore (newScore); nextNode.setEstimatedScore (newScore + targetScorer .computeCost (חיבור, אל)); openSet.add (nextNode);}}); לזרוק IllegalStateException חדש ("לא נמצא מסלול"); }

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

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

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

5.4. פרטים ספציפיים לרכבת התחתית בלונדון

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

הצמתים שלנו הם תחנות במחתרת, ונדגם אותם עם ה- תַחֲנָה מעמד:

תחנה בכיתה ציבורית מיישמת את GraphNode {מזהה מחרוזת סופי פרטי; פרטי סופי מחרוזת; קו רוחב כפול סופי פרטי; קו אורך כפול סופי פרטי; }

השם שימושי לצפייה בפלט, וקו הרוחב והאורך הם לניקוד שלנו.

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

מחלקה ציבורית HaversineScorer מיישם את Scorer {@Override כפול ציבורי computeCost (תחנה מ, תחנה ל) {כפול R = 6372.8; // רדיוס כדור הארץ, בקילומטרים כפול dLat = Math.toRadians (to.getLatitude () - from.getLatitude ()); כפול dLon = Math.toRadians (to.getLongitude () - from.getLongitude ()); כפול lat1 = Math.toRadians (from.getLatitude ()); lat2 כפול = Math.toRadians (to.getLatitude ()); כפול a = Math.pow (Math.sin (dLat / 2), 2) + Math.pow (Math.sin (dLon / 2), 2) * Math.cos (lat1) * Math.cos (lat2); כפול c = 2 * Math.asin (Math.sqrt (a)); להחזיר R * c; }}

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

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

חלל ציבורי findRoute () {List route = routeFinder.findRoute (underground.getNode ("74"), underground.getNode ("7")); System.out.println (route.stream (). מפה (תחנה :: getName) .collect (Collectors.toList ())); }

זה יוצר מסלול של ארל'ס קורט -> דרום קנזינגטון -> גרין פארק -> יוסטון -> אנג'ל.

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

6. מסקנה

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

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

ושוב, הקוד השלם למאמר זמין באתר GitHub.