Η αναδρομή είναι μια ισχυρή αλγοριθμική μέθοδος, πιο αισθητική (όσο αφορά στο μέγεθος των αλγορίθμων και κατά συνέπεια των προγραμμάτων που γράφουμε), πιο φυσική (αφού συμβαδίζει με την διαίσθησή μας) και πιο ισχυρή (μιας και μας δίδει την δυνατότητα να περιγράψουμε με εύκολο και εύληπτο τρόπο δύσκολα προβλήματα).
Για την επίλυση ενός δεδομένου προβλήματος ένας αναδρομικός αλγόριθμος καλεί τον εαυτό του αναδρομικά μία ή περισσότερες φορές επιλύοντας λύνοντας ένα ή περισσότερα στιγμιότυπα- υποπρόβλημα του ίδιου προβλήματος. Με τον όρο υποπρόβλημα εννοούμε ένα πρόβλημα της ίδιας φύσης με το αρχικό, αλλά μικρότερου μεγέθους.
΄Ενας αλγόριθμος τέτοιου είδους τυπικά ακολουθεί μια διαίρει και βασίλευε (divide and conquer) προσέγγιση, κατά την οποία το αρχικό πρόβλημα διασπάται σε μια σειρά από υποπροβλήματα τα οποία επιλύονται ένα προς ένα αναδρομικά και έπειτα συνδυάζονται οι λύσεις αυτών για να δημιουργηθεί η λύση του αρχικού προβλήματος.
Σε κάθε αναδρομικό επίπεδο, η τεχνική divide and conquer περιλαμβάνει τρία βήματα:
Divide: Διαίρεση του προβλήματος σε μικρότερα προβλήματα (υποπροβλήματα).
Conquer: Επίλυση των μικρότερων προβλημάτων (είτε αναδρομικά, είτε με άμεσο
τρόπο εάν έχουν ικανοποιητικά μικρό μέγεθος).
Combine: Συνδυασμός των λύσεων για την εύρεση της αρχικής λύσης.
Μια σχηματική αναπαράσταση θα ήταν η παρακάτω
΄Ενα κλασσικό παράδειγμα divide and conquer αλγορίθμου, είναι ο αλγόριθμος ταξινόμησης
Merge-Sort ο αλγόριθμος εξελίσσεται ως εξής:
Divide: Διαίρεση του πίνακα n στοιχείων σε δύο υποπίνακες n/2 στοιχείων ο καθένας.
Conquer: Αναδρομική ταξινόμηση των δύο υποπινάκων με χρήση της MergeSort.
Combine: Συγχώνευση των δύο ταξινομημένων υποπινάκων.
Ο αλγόριθμος Merge ξεκινάει συγκρίνοντας το πρώτο στοιχείο του πίνακα a με το πρώτο στοιχείο του πίνακα b και επιλέγει το μικρότερο από τα δύο για να το τοποθετήσει πρώτο στον ταξινομημένο πίνακα c ο οποίος τελικά θα περιέχει τα στοιχεία και των δύο πινάκων. Εν συνεχεία ο μετρητής του πίνακα από τον οποίο επελέγει το πρώτο στοιχείο αυξάνεται κατά ένα και η διαδικασία σύγκρισης συνεχίζεται έτσι ώστε τελικά όλα τα στοιχεία των πινάκων a και b να τοποθετηθούν ταξινομημένα στον πίνακα c.
Merge (a, b, c)
1. i = 1
2. j = 1
3. for k = 1 to m + n do
4. if ai ≤ bj then
5. ck = ai
6. i = i + 1
7. else
8. ck = bj
9. j = j + 1
10. end if
11. end for
Αναδρομική εκτέλεση του Mergre
MergeSort (A, l, r)
1. if l < r then
2. q ← ⌊(l + r)/2⌋
3. MergeSort(A, l, q)
4. MergeSort(A, q + 1, r)
5. Merge (Α, 1, q, r)/* Ενοποίησε τους δύο υποπίνακες */
6. end if
Η διαδικασία ενοποίηση (Merge) περιγράφετε παρακάτω:
1: Διαδικασία Merge(πίνακας Α, ακέραιος p, ακέραιος q, ακέραιος r)
2: Αρχή
3: Πίνακας ακεραίων Βr-p
4: Ακέραιοι: i, j, k
5: i <-- p
6: k <-- p
7: j <-- q+1
8: Εφόσον (i ≤ q KAI j ≤ r)
9: Εάν (Ai ≤ Aj) Τότε
10: Βk <-- Ai
11: k <-- k+1
12: i <-- i+1
13: Αλλιώς
14: Βk <-- Aj
15: k <-- k+1
16: j <-- j+1
17: Τέλος Εάν
18: Τέλος Εφόσον
19: Εφόσον (i ≤ q )
20: Βk <--Ai
21: k <-- k+1
22: i <-- i+1
23: Τέλος Εφόσον
24: Εφόσον (j ≤ r)
25: Βk <-- Aj
26: k <-- k+1
27: j <-- j+1
28: Τέλος Εφόσον
29: Για i=1 μέχρι r
30: Ai <-- Bi
31: Τέλος Για (i)
32: Τέλος Διαδικασίας «Merge»
Ενώ σε πρόγραμμα η διαδικασία Merge έχει ως εξής:
void merge(A[], int p, int q, int r) {
int B[r-p];
int i=k=p;
int j=q+1;
while (i <= q && j <= r)
if (A[i] <= A[j])
B[k++] = A[i++];
else
B[k++] = A[j++];
while (i <= q) B[k++] = A[i++];
while (j <= r) B[k++] = A[j++];
for (i=0; i < r; i++)
A[i] = B[i];
}
΄Ενα άλλο κλασσικό μαθηματικό πρόβλημα το οποίο εμπεριέχει την έννοια της
αναδρομής είναι η ακολουθία Fibonacci.
Πρακτικά κάθε αριθμός της ακολουθίας Fibonacci προκύπτει ως το άθροισμα των
προηγουμένων δύο αριθμών της ακολουθίας. Για παράδειγμα οι 13 πρώτοι αριθμοί της ακολουθίας είναι: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233. ΄Ενας επαναληπτικός αλγόριθμος ο οποίος μπορεί να χρησιμοποιηθεί για την εύρεση του n−οστού αριθμού της ακολουθίας είναι ο εξής:
Fibonacci (n)
1. f0 = 1
2. f1 = 1
3. for i = 3 to n do
4. temp = f0 + f1
5. f0 = f1
6. f1 = temp
7. end for
8. return f
Ο παρακάτω αλγόριθμος βασίζεται στον αναδρομικό ορισμό της ακολουθίας.
Ο αλγόριθμος αυτός έχει ως εξής
Fibonacci (n)
1. u = 1
2. f = 1
3. if n ≤ 1 then
4. return 1
5. else
6. return Fibonacci(n − 1) + Fibonacci(n − 2)
7. end if
Άλλα τέτοια παραδείγματα αναδρομικού ορισμού αλγορίθμων θα δούμε συνοπτικά παρακάτω.
O αλγόριθμος Min-Max είναι το πρόβλημα της εύρεσης του μέγιστου και του ελάχιστου στοιχείου ενός πίνακα A με n στοιχεία.
MinMax (A, i, j, min, max)
1. if i ≥ j − 1 then
2. if ai < aj then
3. max = aj
4. min = ai
5. else
6. max = ai
7. min = aj
8. end if
9. else
10. m = ⌊(i + j)/2⌋
11. MinMax(A, i, m, min1, max1)
12. MinMax(A, m, j, min2, max2)
13. min = fmin(min1, min2)
14. max = fmax(max1, max2)
15. end if
O αλγόριθμος QuickSort.
QuickSort (A, p, r)
1. if p < r then
2. q =Partition(A, p, r)
3. QuickSort (A, p, q − 1)
4. QuickSort (A, q + 1, r)
5. end if
Το κλειδί του αλγορίθμου είναι η διαδικασία της διαμέρισης (Partition) η οποία επανατοποθετεί τα στοιχεία του πίνακα σύμφωνα με το στοιχείο περιστροφής (pivot) που έχει επιλεγεί: Τα μεγαλύτερα από αυτό μπαίνουν στα δεξιά του και τα μικρότερα στα αριστερά του. Η διαδικασία αυτή περιγράφεται παρακάτω.
Partition (A, p, r)
1. x = A[r]
2. i = p − 1
3. for j = p to r − 1 do
4. if A[j] ≤ x
5. i = i + 1
6. swap(A[i], A[j])
7. end if
8. end for
9. swap(A[i + 1], A[r])
10. return i + 1
Ελπίζω να βρείτε χρήσιμα όλα αυτά τα στοιχεία και να βοηθήσουν στην περαιτέρω μελέτη σας.
Δημοσίευση σχολίου