Γιατί λειτουργεί ο αλγόριθμος του Prim;
Γιατί λειτουργεί ο αλγόριθμος του Prim;

Βίντεο: Γιατί λειτουργεί ο αλγόριθμος του Prim;

Βίντεο: Γιατί λειτουργεί ο αλγόριθμος του Prim;
Βίντεο: Η Μέρα που Αντιγράψαμε την Εξέλιξη - Γενετικοί Αλγόριθμοι [Μάθε πως Μαθαίνουν] 2024, Μάρτιος
Anonim

Στην επιστήμη των υπολογιστών, Prim's (γνωστό και ως Jarník's) αλγόριθμος είναι άπληστος αλγόριθμος που βρίσκει ένα ελάχιστο εκτεινόμενο δέντρο για ένα σταθμισμένο μη κατευθυνόμενο γράφημα. Αυτό σημαίνει ότι βρίσκει ένα υποσύνολο των άκρων που σχηματίζει ένα δέντρο που περιλαμβάνει κάθε κορυφή, όπου το συνολικό βάρος όλων των άκρων στο δέντρο ελαχιστοποιείται.

Από αυτή την άποψη, γιατί το Prims είναι καλύτερο από το Kruskal;

του Kruskal Αλγόριθμος: εκτελεί καλύτερα σε τυπικές καταστάσεις (αραιά γραφήματα) επειδή χρησιμοποιεί απλούστερες δομές δεδομένων. Prim's Αλγόριθμος: είναι σημαντικά πιο γρήγορος στο όριο όταν έχετε ένα πραγματικά πυκνό γράφημα με πολλές περισσότερες ακμές από κορυφές.

είναι ο αλγόριθμος του Prim βέλτιστος; Ο αλγόριθμος του Prim είναι άπληστος αλγόριθμος για την εύρεση ενός ελάχιστου εκτεινόμενου δέντρου σε ένα σταθμισμένο μη κατευθυνόμενο γράφημα χρησιμοποιώντας μια άπληστη προσέγγιση. Σε περίπτωση που Ο αλγόριθμος του Prim , επιλέγουμε επανειλημμένα την κορυφή της οποίας η απόσταση από την κορυφή της πηγής ελαχιστοποιείται, δηλ. το ρεύμα τοπικά άριστος επιλογή.

Έχοντας αυτό υπόψη, μπορεί ο αλγόριθμος του Prim να έχει κύκλους;

Αλγόριθμος Prim . Ο αλγόριθμος του Prim δημιουργεί σαφώς ένα εκτεινόμενο δέντρο, γιατί όχι κύκλος μπορεί εισάγονται προσθέτοντας άκρες μεταξύ κορυφών δένδρων και μη δένδρων.

Ποιος αλγόριθμος είναι πιο αποτελεσματικός στην κατασκευή του ελάχιστης έκτασης δέντρου ενός δεδομένου γραφήματος Ο αλγόριθμος του Prim ή του αλγόριθμου του Kruskal και γιατί;

Αλγόριθμος Kruskal αναπτύσσει μια λύση από τη φθηνότερη άκρη προσθέτοντας την επόμενη φθηνότερη άκρη στην υπάρχουσα δέντρο / δάσος. Αλγόριθμος Prim είναι πιο γρήγορο για πυκνό γραφικές παραστάσεις . Αλγόριθμος Kruskal είναι πιο γρήγορο για αραιά γραφικές παραστάσεις.

Συνιστάται: