Διαίρει και Βασίλευε - Εισαγωγή
Η τεχνική Διαίρει και Βασίλευε είναι μια τεχνική σχεδίασης αλγορίθμων περιλαμβάνει:
- τη διάσπαση (Διαίρει) ενός μεγαλύτερου προβλήματος σε μικρότερα υποπροβλήματα,
- την ανεξάρτητη επίλυσή (Βασίλευε)τους και στη συνέχεια
- τον συνδυασμό των λύσεών τους για την επίλυση του αρχικού προβλήματος.
Η βασική ιδέα είναι να διαιρείται το πρόβλημα σε μικρότερα υποπροβλήματα και αυτά σε ακόμη μικρότερα μέχρις ότου να γίνουν αρκετά απλά για να επιλυθούν άμεσα. Ο συνδυασμός των επιμέρους λύσεων οδηγεί στην συνολική λύση.
Ένα παράδειγμα (από την καθημερινή ζωή) της προσέγγισης “διαίρει και βασίλευε” είναι αυτή της οργάνωσης μιας μεγάλης εκδήλωσης όπως π.χ. ένας γάμος. Το όλο εγχείρημα απαιτεί τα ακόλουθα:
- Διάσπαση/ Διαίρεση: Η εκδήλωση πρέπει να διασπαστεί σε μικρότερες εργασίες όπως η επιλογή του χώρου, η τροφοδοσία, οι προσκλήσεις, η διακόσμηση και η ψυχαγωγία.
- Βασίλευε: Κάθε εργασία ανατίθεται σε διαφορετικά άτομα ή ομάδες που μπορούν να τις χειριστούν ανεξάρτητα.
- Συνδυασμός: Μόλις κάθε ομάδα ολοκληρώσει την εργασία της, γίνεται σύνθεση της δουλειάς όσων εμπλέκονται και καταλήγουμε σε μια επιτυχημένη εκδήλωση!
Η μέθοδος σχεδίασης αλγορίθμων «Διαίρει και Βασίλευε» μπορεί να αποδοθεί με τα επόμενα βήματα:
- Δίνεται για επίλυση ένα στιγμιότυπο ενός προβλήματος.
- Το στιγμιότυπο του προβλήματος υποδιαιρείται σε υπο-στιγμιότυπα του ίδιου προβλήματος.
- Δίνεται ανεξάρτητη λύση σε κάθε ένα υπο-στιγμιότυπο.
- Συνδυάζονται όλες οι μερικές λύσεις που βρέθηκαν για τα υπο-στιγμιότυπα, έτσι ώστε να δοθεί
η συνολική λύση του προβλήματος.
Ορισμός
Η «Διαίρει και Βασίλευε» (divide and conquer) αποτελεί μια μέθοδο σχεδίασης αλγορίθμων στην οποία εντάσσονται οι τεχνικές που υποδιαιρούν ένα πρόβλημα σε μικρότερα υποπροβλήματα, που έχουν την ίδια τυποποίηση με το αρχικό πρόβλημα, αλλά είναι μικρότερα σε μέγεθος. Με όμοιο τρόπο, τα υποπροβλήματα αυτά μπορούν να διαιρεθούν σε ακόμη μικρότερα υποπροβλήματα κ.ο.κ. Έτσι η επίλυση ενός προβλήματος έγκειται στη σταδιακή επίλυση των όσο το δυνατόν μικρότερων υποπροβλημάτων, ώστε τελικά να προκύψει η συνολική λύση του αρχικού ευρύτερου προβλήματος.
Η προσέγγιση αυτή ονομάζεται «από πάνω προς τα κάτω» (top-down).
Ερωτήσεις ανάπτυξης απο Πανελλαδικές εξετάσεις
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx