Διαίρει και βασίλευε (υπολογιστές)
Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Στην επιστήμη των υπολογιστών, διαίρει και βασίλευε (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
