עוד לפני הופעת גוגל מפות, אנשים השתמשו בתוכנות כמו MapQuest כדי להדפיס הנחיות ולהבין את המסלול הקצר ביותר בין שני מיקומים. אמנם קל לקחת אפליקציות מיפוי כמובן מאליו בימינו, אבל יש כמה אלגוריתמים מתמטיים מעניינים שפועלים מאחורי הקלעים שמאפשרים הכל.
טק. בידור. מַדָע. תיבת הדואר הנכנס שלך.
הירשם לחדשות הטכנולוגיה והבידור המעניינות ביותר שיש.
בהרשמה אני מסכים ל תנאי שימוש וסקרו את הודעת פרטיות.
לא הרבה אנשים מודעים לכך, אבל האלגוריתם הממוחשב שהופך תוכניות מיפוי לכל כך נוחות מתוארך לשנת 1956, כאשר מתכנת בשם Edsger W. Dijkstra היה צריך להמציא בעיה פתירה כאמצעי להציג את הכוח של מחשב ARMAC חדש. דיקסטרה עצמו הוא קצת אגדת מחשוב, לאחר שקיבל את פרס טיורינג ב-1972.
קָשׁוּר: תוסף Gmail בחינם מאפשר לך לראות אם עוקבים אחר הודעות הדוא"ל שלך לפני שאתה פותח אותן
בחיפוש אחר בעיה ניתנת לזיהוי, דייקסטרה הסתפק ב"דרך הקצרה ביותר לנסוע מרוטרדם לחרונינגן".
סְגָן דיווחים:
"בשביל הדגמה לאנשים שאינם מחשובים אתה צריך להיות בעל הצהרת בעיה שלא מתמטיקאים יכולים להבין", נזכר דיקסטרה בראיון זמן לא רב לפני מותו ב-2002. "הם אפילו צריכים להבין את התשובה. אז תכננתי תוכנית שתמצא את המסלול הקצר ביותר בין שתי ערים בהולנד, באמצעות מפת דרכים מצומצמת מעט של הולנד, שבה בחרתי 64 ערים".
האלגוריתם שעמד בבסיס עבודתו של דיג'יקסטרה, ואכן, פונקציונליות המיפוי הבסיסית בתוכניות רבות, היה משהו שהוא אמר שהוא הגיע אליו תוך כדי שתיית קפה כלאחר יד. האלגוריתם עצמו הודגש ב-a מאמר שפורסם משנת 1959 ונקרא כראוי האלגוריתם של דיקסטרה.
יש לציין כי לאלגוריתם של דיקסטרה יש יישומים מעבר לניווט המסורתי. זה שימש גם לדברים כמו תכנון עירוני, פרוטוקולי ניתוב רשת ועיצוב שבבים אופטימלי.
