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