Ελάχιστο γεννητικό δέντρο

Μια πρώτη προσπάθεια

Μπορεί να είναι πολύ απλό να φτιάξετε έναν αλγόριθμο που θα ανακαλύψει ένα ελάχιστο δέντρο:

 συνάρτηση MST(G,W):     T = {} ενώ το T δεν σχηματίζει δένδρο διάσχισης: βρείτε την ελάχιστη σταθμισμένη ακμή στο E που είναι ασφαλής για το T T = T union {(u,v)} return T

Σε αυτή την περίπτωση, "ασφαλές" σημαίνει ότι η συμπερίληψη της ακμής δεν σχηματίζει κύκλο στο γράφημα. Κύκλος σημαίνει ότι ξεκινάμε από μια κορυφή, ταξιδεύουμε σε έναν αριθμό άλλων κορυφών και καταλήγουμε ξανά στο σημείο εκκίνησης χωρίς να χρησιμοποιήσουμε την ίδια ακμή δύο φορές.

Ιστορία

Ο Τσέχος επιστήμονας Otakar Borůvka ανέπτυξε τον πρώτο γνωστό αλγόριθμο για την εύρεση ενός ελάχιστου δέντρου, το 1926. Ήθελε να λύσει το πρόβλημα της εύρεσης μιας αποτελεσματικής κάλυψης της Μοραβίας με ηλεκτρικό ρεύμα. Σήμερα, ο αλγόριθμος αυτός είναι γνωστός ως αλγόριθμος του Borůvka. Δύο άλλοι αλγόριθμοι χρησιμοποιούνται συνήθως σήμερα. Ο ένας από αυτούς αναπτύχθηκε από τον Vojtěch Jarník το 1930 και τέθηκε σε εφαρμογή από τον Robert Clay Prim το 1957. Ο Edsger Wybe Dijkstra τον ανακάλυψε εκ νέου το 1959 και τον ονόμασε αλγόριθμο του Prim. Ο άλλος αλγόριθμος ονομάζεται αλγόριθμος του Kruskal και αναπτύχθηκε από τον Joseph Kruskal το 1956. Και οι τρεις αλγόριθμοι είναι άπληστοι και εκτελούνται σε πολυωνυμικό χρόνο.

Ο γρηγορότερος αλγόριθμος ελάχιστου δέντρου που έχει αναπτυχθεί μέχρι σήμερα αναπτύχθηκε από τον Bernard Chazelle. Ο αλγόριθμος βασίζεται στον μαλακό σωρό, μια προσεγγιστική ουρά προτεραιότητας. Ο χρόνος λειτουργίας του είναι O(m α(m,n)), όπου m είναι ο αριθμός των ακμών, n είναι ο αριθμός των κορυφών και α είναι η κλασική αντίστροφη συνάρτηση Ackermann. Η συνάρτηση α αυξάνεται εξαιρετικά αργά, έτσι ώστε για όλους τους πρακτικούς σκοπούς μπορεί να θεωρηθεί σταθερά όχι μεγαλύτερη από 4. Έτσι, ο αλγόριθμος του Chazelle χρειάζεται πολύ κοντά σε γραμμικό χρόνο.

Ποιος είναι ο ταχύτερος δυνατός αλγόριθμος για το πρόβλημα αυτό; Αυτό είναι ένα από τα παλαιότερα ανοικτά ερωτήματα στην επιστήμη των υπολογιστών. Υπάρχει σαφώς ένα γραμμικό κατώτερο όριο, αφού πρέπει τουλάχιστον να εξετάσουμε όλα τα βάρη. Εάν τα βάρη των ακμών είναι ακέραιοι αριθμοί με περιορισμένο μήκος bit, τότε είναι γνωστοί ντετερμινιστικοί αλγόριθμοι με γραμμικό χρόνο εκτέλεσης. Για γενικά βάρη, υπάρχουν τυχαιοποιημένοι αλγόριθμοι των οποίων ο αναμενόμενος χρόνος εκτέλεσης είναι γραμμικός.

Το πρόβλημα μπορεί επίσης να προσεγγιστεί με κατανεμημένο τρόπο. Αν κάθε κόμβος θεωρείται υπολογιστής και κανένας κόμβος δεν γνωρίζει τίποτα άλλο εκτός από τους δικούς του συνδεδεμένους συνδέσμους, μπορεί κανείς να υπολογίσει το κατανεμημένο ελάχιστο δένδρο.