Άνοιγμα κυρίου μενού

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

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

Πίνακας περιεχομένων

ΜέθοδοςΕπεξεργασία

Η μέθοδος χρησιμοποιεί τρία στάδια για την επίλυση ενός προβλήματος. Συγκεκριμένα:

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

ΠλεονεκτήματαΕπεξεργασία

Δύσκολα προβλήματαΕπεξεργασία

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

ΜειονεκτήματαΕπεξεργασία

ΠολυπλοκότηταΕπεξεργασία

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

Βλ. ΕπίσηςΕπεξεργασία

ΒιβλιογραφίαΕπεξεργασία

  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, The MIT Press, 2nd Edition.