Μετάβαση στο περιεχόμενο

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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Διαιρώντας το πρόβλημα σε υποπροβλήματα

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