אלגוריתם דייקסטרה ויישומה

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

מהו גרף מתמטי

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

מציאת המסלול הקצר

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

דרכים לפתור

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

אלגוריתם דייקסטרה

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

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