.jpg)
🗺️ Πώς γεννήθηκε ο αλγόριθμος του Dijkstra
.jpg)
Το 1956, στο Mathematical Centre του Άμστερνταμ, ετοιμαζόταν η επίσημη παρουσίαση του νέου υπολογιστή ARMAC.
Ο Edsger W. Dijkstra χρειαζόταν ένα πρόβλημα που να μπορούσε να καταλάβει εύκολα ακόμη και ένα κοινό χωρίς γνώσεις υπολογιστών.
Η ιδέα ήταν απλή:
Σε μεταγενέστερη συνέντευξή του, ο Dijkstra χρησιμοποίησε ως χαρακτηριστικό παράδειγμα τη διαδρομή Ρότερνταμ–Χρόνινγκεν και θυμήθηκε ότι σχεδίασε τον αλγόριθμο σε περίπου 20 λεπτά, ενώ είχε καθίσει για καφέ σε μια βεράντα στο Άμστερνταμ.
Το εντυπωσιακότερο; Όπως ο ίδιος αφηγήθηκε, το έκανε χωρίς χαρτί και μολύβι.
Ο Dijkstra παρατήρησε αργότερα ότι η εργασία χωρίς χαρτί είχε ένα απροσδόκητο πλεονέκτημα: τον ανάγκαζε να αποφεύγει κάθε περιττή πολυπλοκότητα.
Για την επίδειξη του ARMAC χρησιμοποίησε έναν απλοποιημένο χάρτη του ολλανδικού σιδηροδρομικού δικτύου. Κάποιος από το κοινό μπορούσε να ζητήσει τη συντομότερη σύνδεση μεταξύ δύο πόλεων και ο υπολογιστής εμφάνιζε τη διαδρομή πόλη προς πόλη.
Τρία χρόνια αργότερα, το 1959, ο αλγόριθμος δημοσιεύθηκε στο περιοδικό Numerische Mathematik, στο σύντομο άρθρο
Το άρθρο καταλάμβανε μόλις λίγες σελίδες, αλλά η ιδέα του έγινε θεμελιώδης στη θεωρία γράφων και στους αλγορίθμους συντομότερων διαδρομών.
Η βασική ιδέα του Dijkstra αποτελεί σήμερα κλασικό εργαλείο για προβλήματα δρομολόγησης σε οδικά και υπολογιστικά δίκτυα και βρίσκεται πίσω από πολλές από τις ιδέες που χρησιμοποιούνται στα σύγχρονα συστήματα πλοήγησης και δικτύων.
Και όλα ξεκίνησαν από μια εξαιρετικά απλή ερώτηση: «Ποιος είναι ο συντομότερος δρόμος;»
Πηγή: E. W. Dijkstra, A Note on Two Problems in Connexion with Graphs, Numerische Mathematik 1 (1959), 269–271, και μεταγενέστερες αναμνήσεις του Dijkstra.
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου