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