Διαίρει και βασίλευε (υπολογιστές)

Στην επιστήμη των υπολογιστών, διαίρει και βασίλευε (divide and conquer, D&C) είναι μέθοδος επίλυσης προβλημάτων. Το πρόβλημα διαιρείται σε μικρότερα υποπροβλήματα και στη συνέχεια οι λύσεις τους συνδυάζονται για να προκύψει η λύση του αρχικού προβλήματος. Η μέθοδος αποτελεί τη βάση πολλών αλγορίθμων, π.χ. στους αλγόριθμους ταξινόμησης merge-sort και Quicksort.

Το όνομά της προέρχεται από τη γνωστή ρήση του Καίσαρα, divide ut regnes (λατινικά).

 Μέθοδος 

Η μέθοδος χρησιμοποιεί τρία στάδια για την επίλυση ενός προβλήματος. Συγκεκριμένα:
 Το πρόβλημα διαιρείται σε ένα αριθμό υποπροβλημάτων. ("Διαίρει")
 Ακολουθεί αναδρομική επίλυση των προβλημάτων. Ωστόσο, εάν το μέγεθος των υποπροβλημάτων είναι αρκετά μικρό η επίλυση τους γίνεται κατευθείαν. ("Βασίλευε")
 Τέλος οι λύσεις των υποπροβλημάτων συνδυάζονται σε μία ενιαία λύση στο αρχικό πρόβλημα.

 Πλεονεκτήματα 

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

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

 Μειονεκτήματα 

 Πολυπλοκότητα 
Η αντιμετώπιση ορισμένων απλών, μικρών προβλημάτων με το συγκεκριμένο τρόπο (αναδρομικό - recursive) είναι δυνατόν να είναι πιο περίπλοκη και δυσνόητη από αντίστοιχη επίλυση βασιζόμενη σε απλή επανάληψη (iterative).

 Δείτε Επίσης 
 Αλγόριθμος
 Αναδρομή
 Quicksort (Γρήγορη ταξινόμηση)
 Merge-sort
 Πύργοι του Ανόι

 Βιβλιογραφία 
 T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, The MIT Press, 2nd Edition.

Κατηγορία:Αλγόριθμοι

Κατηγορία:Επιχειρησιακή έρευνα
Κατηγορία:Αλγόριθμοι και μέθοδοι βελτιστοποίησης