דייקסטרה

[susi]

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

[אורן בקר]

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

כדי להבין איך הוא עובד, מומלץ להשתמש בדימויים:

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

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

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

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

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

הכתובת המצורפת מכילה את מאגר כתביו של דייקסטרה עצמו בנושאים שונים.
בנוסף, למידע נוסף על "ערימות", ראה:
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/heaps.html
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Priority-Q/

אורן.

[סוסי]

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

[מאת]

תגובות