Διαίρει και βασίλευε (υπολογιστές)
 |
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
|
Το λήμμα παραθέτει τις πηγές του αόριστα, χωρίς παραπομπές. |
Στην επιστήμη των υπολογιστών, διαίρει και βασίλευε (divide and conquer, D&C) είναι μέθοδος επίλυσης προβλημάτων. Το πρόβλημα διαιρείται σε μικρότερα υποπροβλήματα και στη συνέχεια οι λύσεις τους συνδυάζονται για να προκύψει η λύση του αρχικού προβλήματος. Η μέθοδος αποτελεί τη βάση πολλών αλγορίθμων, π.χ. στους αλγόριθμους ταξινόμησης merge-sort και Quicksort.
Το όνομά της προέρχεται από τη γνωστή ρήση του Καίσαρα, divide ut regnes (λατινικά).
Μέθοδος
[Επεξεργασία | επεξεργασία κώδικα]Η μέθοδος χρησιμοποιεί τρία στάδια για την επίλυση ενός προβλήματος. Συγκεκριμένα:
- Το πρόβλημα διαιρείται σε ένα αριθμό υποπροβλημάτων. ("Διαίρει")
- Ακολουθεί αναδρομική επίλυση των προβλημάτων. Ωστόσο, εάν το μέγεθος των υποπροβλημάτων είναι αρκετά μικρό η επίλυση τους γίνεται κατευθείαν. ("Βασίλευε")
- Τέλος οι λύσεις των υποπροβλημάτων συνδυάζονται σε μία ενιαία λύση στο αρχικό πρόβλημα.
Πλεονεκτήματα
[Επεξεργασία | επεξεργασία κώδικα]Δύσκολα προβλήματα
[Επεξεργασία | επεξεργασία κώδικα]Η μέθοδος είναι ιδιαίτερα αποτελεσματική στην επίλυση δύσκολων προβλημάτων, καθώς στηρίζεται στην επίλυση μικρότερων, ευκολότερων προβλημάτων. Παράδειγμα αποτελεί το παιχνίδι των Πύργων του Ανόι.
Παράλληλη Επεξεργασία
[Επεξεργασία | επεξεργασία κώδικα]Οι αλγόριθμοι διαίρει και βασίλευε είναι προσαρμοσμένοι για εκτέλεση παράλληλα, ιδιαίτερα σε συστήματα με κοινή μνήμη, όπου τα δεδομένα δε χρειάζεται να μοιράζονται μεταξύ των επεξεργαστών, καθώς διαφορετικά υποπροβλήματα μπορούν να εκτελεστούν σε διαφορετικούς επεξεργαστές ξεχωριστά.
Μειονεκτήματα
[Επεξεργασία | επεξεργασία κώδικα]Πολυπλοκότητα
[Επεξεργασία | επεξεργασία κώδικα]Η αντιμετώπιση ορισμένων απλών, μικρών προβλημάτων με το συγκεκριμένο τρόπο (αναδρομικό - recursive) είναι δυνατόν να είναι πιο περίπλοκη και δυσνόητη από αντίστοιχη επίλυση βασιζόμενη σε απλή επανάληψη (iterative).
Εφαρμογές
[Επεξεργασία | επεξεργασία κώδικα]Αλγόριθμοι ταξινόμησης
[Επεξεργασία | επεξεργασία κώδικα]Πολλοί γρήγοροι αλγόριθμοι ταξινόμησης στηρίζονται στην μέθοδο του διαίρει και βασίλευε.
Για παράδειγμα, η ταξινόμηση με συγχώνευση χωρίζει αναδρομικά τον πίνακα σε δύο μέρη (διαίρει), έπειτα ταξινομεί κάθε ένα από αυτά ξεχωριστά (βασίλευε) και τέλος συνδυάζει τα δύο ταξινομημένα μέρη σε ένα διατρέχοντας συγχρόνως τα δύο ταξινομημένα μέρη. Η συνολική πολυπλοκότητα είναι όπου είναι το πλήθος των στοιχείων του πίνακα.
Ένας άλλος αλγόριθμος είναι η γρήγορη ταξινόμηση, η οποία διαλέγει τυχαία ένα στοιχείο του πίνακα και χωρίζει τα στοιχεία σε μικρότερα, ίσα ή μεγαλύτερα (διαίρει). Έπειτα, αναδρομικά ταξινομεί κάθε ένα από αυτά (βασίλευε). Τέλος, ο αρχικός πίνακας είναι ταξινομημένος. Αποδεικνύεται ότι με μεγάλη πιθανότητα αυτός ο αλγόριθμος χρειάζεται βήματα για να τερματίσει. Επίσης έχει το επιπλέον πλεονέκτημα ότι δεν χρειάζεται έξτρα μνήμη για την υλοποίησή του.
Υπολογισμός τιμής πολυωνύμου
[Επεξεργασία | επεξεργασία κώδικα]Για τον υπολογισμό της τιμής ενός πολυωνύμου συνήθως χρησιμοποιείται ένα . Αν αυτό θέλουμε να γίνει παράλληλα, τότε το σχήμα Estrin αναδρομικά σπάει τον υπολογισμό της τιμής στους πρώτους και στους τελευταίους όρους (διαίρει), τους υπολογίζει αναδρομικά (βασίλευε) και έπειτα τους προσθέτει. Αυτό χρειάζεται παράλληλα βήματα αν υπάρχουν διαθέσιμος μηχανές.
Ένας άλλος αλγόριθμος διαίρει και βασίλευε χρησιμοποιείται για τον υπολογισμό τιμών του ίδιου πολυωνύμου σε χρόνο αντί για τον , που προκύπτει από υπολογισμούς.
Δείτε επίσης
[Επεξεργασία | επεξεργασία κώδικα]Βιβλιογραφία
[Επεξεργασία | επεξεργασία κώδικα]- T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, The MIT Press, 2nd Edition.
Εξωτερικοί σύνδεσμοι
[Επεξεργασία | επεξεργασία κώδικα]
Πολυμέσα σχετικά με το θέμα Διαίρει και βασίλευε (υπολογιστές) στο Wikimedia Commons
