αλγόριθμο Δυναμικού Προγραμματισμού

Ξεκινώντας από έναν αριθμό n, μπορούμε να καταλήξουμε στον αριθμό 1 εκτελώντας μία ακολουθία από τις παρακάτω πράξεις: αφαίρεση του 1, διαίρεση με το 2,  διαίρεση με το 3, διαίρεση με το 5, διαίρεση με το 7. Μία διαίρεση μπορεί να γίνει μόνο αν είναι τέλεια.

A) Σχεδιάστε & αναλύστε αλγόριθμο Δυναμικού Προγραμματισμού ο οποίος με είσοδο έναν αριθμό n θα υπολογίζει το μήκος της ελάχιστης ακολουθίας επιτρεπτών πράξεων που απαιτούνται για να μετατραπεί σε 1 με τη διαδικασία που περιγράφεται παραπάνω.

B) Τρέξτε τον αλγόριθμο για n= 11.

Γ) Πόσες είναι οι επαναλήψεις του αλγορίθμου με είσοδο n;

Δ) Ο αλγόριθμος που κάθε φορά, επιλέγει την πράξη που δίνει το μικρότερο αποτέλεσμα, δίνει πάντα τη βέλτιστη λύση; Αιτιολογήστε.
-----------------------------------------------------

 <Α.>

 Θα προσπαθήσουμε να δώσουμε ένα αλγόριθμο Με την βοήθεια του δυναμικού προγραμματισμού θα υπολογίσουμε την βέλτιστη λύση. ΘΑ χωρίσουμε το πρόβλημα σε υποπροβληματα και η βέλτιστη λύση για ένα υποπρόβλημα να προκύπτει από την λύση των αλλων  υποπροβληματων.  Ένα σημαντικό σημείο είναι ο χωρισμός του προβλήματος σε υποπροβληματα. Το πρόβλημα που εχουμε να επιλύσουμε είναι οι ελάχιστες πράξεις που θα εφαρμόσω σε έναν αριθμό n ώστε να γίνει ισος με την μονάδα με τις  οι επιτρεπτές πράξεις που μπορώ να εφαρμόσω  να είναι η  διαίρεση με το 7,η διαίρεση με το 5 , η διαίρεση με το 3, η  διαίρεση με το 2 και αφαίρεση με το 1. Έστω n o ο αριθμός προς έλεγχο τότε  ο παρακάτω πίνακας θα είναι τα αποτελέσματα που θα μας επιστρέψει  ο Αλγόριθμος που πρέπει να σχεδιάσουμε

N αριθμος	Πράξεις
0	0
1	0
2	1πράξη  |2:2=1
3	1πράξη  |3:3=1
4	πράξεις |4:2=2|  2:2=1
5	1πράξη  |5:5=1
6	πράξεις  |6:3=2 |  2:2=1
7	1πράξη  |7:7=1
8	2πράξεις  |8-1=7 | 7:7=1
…	…

Ενδεικτικά παραπάνω αναφέραμε τα αποτελέσματα που θα πάρουμε από τον αλγόριθμο.

Παρατηρούμε ότι ο αλγόριθμος D(n) που θα σχεδιάσουμε έχει επικαλυπτόμενα επιμέρους προβλήματα και αναγκαζόμαστε να λύσουμε τα ιδιά προβλήματα

Αλγόριθμος D(n)	Αποτέλεσμα
D(0)	0
D(1)	0
D(2)	1
D(3)	1
D(4)	1+D(2)
D(5)	1
D(6)	1+D(2)
D(7)	1
D(8)	1+D(7)
D(9)	1+D(3)
D(10)	1+D(5)
D(11)	1+D(10)
D(12)	1+D(4)
…	…..

Στο παραπάνω πίνακα εχουμε τον αλγόριθμο D(n) όπου n o αριθμός  προς έλεγχο και το αποτέλεσμα είναι το ο συνολικός  αριθμός πράξεων που προκύπτει.

Παρατηρούμε ότι για να υπολογίσουμε το D(4) αρχικά κάνουμε μια πράξη (διαίρεση με 2 ) έπειτα  το αποτέλεσμα που θα προκύψει είναι το 2 που όμως το έχουμε  υπολογίσει προηγούμενος , D(2).

Ακόμα παρατηρούμε πως το D(8) αφαιρέσαμε με το 1 για να προκύψει το D(7) και το D(7) το είχαμε υπολογίσει νωρίτερα.

Τα παραπάνω τα εφαρμόσαμε για να μας βοηθήσουν να υπολογίσουμε  την αναδρομική σχέση η οποία με την σειρά της θα  μας βοηθήσει στην συγγραφή του δυναμικού προγραμματισμού. Με την αναδρομική σχέση θα υπολογίσουμε και θα καταχωρήσουμε στον πίνακα ΤD, διαστάσεων n , τις τιμές του αλγορίθμου D(n) ώστε για τιμές που θα χρειαζόμαστε και τις εχουμε υπολογίσει   να τις παίρνουμε από τον πίνακα ΤD για να μην υπολογίζουμε τα αποτελέσματα που ήδη έχουμε  υπολογίσει.

Αναδρομική σχέση

Οι  πράξεις που έχουμε στην διάθεση μας είναι 4 διαιρέσεις με τους αριθμούς 7,5,3,2 και μια αφαίρεση με το 1. Όλες θα εφαρμοστούν στο αριθμό n. Αρχικά σκεπτόμαστε ότι εάν ελενξουμε το υπόλοιπο τις διαίρεσης με το 7,5,3,2 θα πρέπει να είναι 0  για να διερειται τελειά ο αριθμός. Ο έλεγχος που θα εφαρμόσουμε θα είναι από το μεγαλύτερο προς το μικρότερο . Έτσι εάν ένας αριθμός διαιρείται με το 7 τότε θα γίνει αρκετά μάκρος και  συγκρίνοντας θα είναι  μικρότερος  με την διαίρεση αυτή παρά  εάν ο ίδιος αριθμός διαιρεθεί  με το 3. Παράδειγμα το 21 διαιτάται και με το 7 και με το  3, όμως ως βέλτιστη λύση είναι να διαιρεθεί πρώτα με το μεγαλύτερο και έπειτα  με το μικρότερο. Ακόμα  παρατηρούμε για D(8) οι λιγότερες πράξεις που θα εφαρμόσουμε για να γίνει το 8  μονάδα χρειάζεται να αφαιρέσουμε με 1 και έπειτα   να υπολογίσουμε το D(7).Παρατηρούμε ότι η βέλτιστη λύση για κάθε n αρχικά να ελέγχουμε εάν αφαιρεθεί με το 1 και μετα  στο αποτέλεσμα μου  κανω τις διαιρέσεις με τους αριθμούς 7,5,3,2 να μετράω τον αριθμό πράξεων και να τις αποθηκεύω  σε μια μεταβλητή tmp έπειτα να συγκρίνω αυτή την  μεταβλητή  με τις τον αριθμό πράξεων που χρειάζεται το n να γίνει μονάδα με τις διαιρέσεις 7,5,3,2 δηλαδή αρχικά  ελέγχω το D(n-1) το συνολικό αριθμό πράξεων με τις διαιρέσεις 7,5,3,2 και έπειτα ελέγχω  τον αριθμό D(n) με τις επιτρεπτές διαιρέσεις 7,5,3,2 και επιλέγω το μικρότερο αριθμό

Δηλαδή η αναδρομική σχέση είναι

   

Δηλαδή για τον υπολογισμό D(n) υπολογίζουμε  τιμή  D(n-1)  +1 και την συγκρίνω με την επιτρεπτή της τέλειας διαίρεσης    προσθέτοντας και την μια πράξη της διαίρεσης.

Τώρα εχωντας την αναδρομική σχέση μπορούμε να γράψουμε τον αλγόριθμο μας

Procedure MinNumOperation(n)

Tmp=0; DivCalc=0;counter

If (n≤1)

    then return 0;

Else

  TD[0]=0  -- για οποιαδήποτε περίπτωση που 2 ζητήσει τιμή εάν και δεν θα την χρειαστούμε διότι υπάρχει  στο if

  TD[1]=0

For i = 2 to n

{   TD[n]=∞ – αρχικοποίηση πίνακα

         i++

  }

 For k= 2 to n  --γεμίζουμε τον πίνακα [2,n] με τιμές N-2 επαναληωεις

{

               DivCalc =0 – αρχικοποίηση το μετρητη μας για κάθε αριθμο  

            k=b –θα υπολογίσω τις κ πράξεις  ώστε το κα να γίνει 1

    While b<1 span="" style="color: #76923c; font-size: 9.0pt; line-height: 120%; mso-bidi-font-family: Arial; mso-bidi-font-size: 12.0pt;">ώσπου το

b να γίνει 1 επανάλαβε τις διαιρέσεις C Θ(1) πράξεις

     {

                                If b mod 7=0 then b/7; DivCalc++ αύξησε το μετρητή κατά 1

If b mod 5=0 then b/5 DivCalc++ αύξησε το μετρητή κατά 1

If b mod 3=0 thenb/3 DivCalc++ αύξησε το μετρητή κατά 1

If b mod 2=0 then b/2 DivCalc++ αύξησε το μετρητή κατά 1

Else If Tmp  =b-1; DivCalc++

      } – μετρήσαμε τις πράξεις στην μεταβλητή DivCalc

    If TD[n-1]<DivCalc—DivCalc συγκρινω  το απότελεσμα που βρηκαμε με το προηγουμενο TD

       Then TD[k]= TD[n-1]

   Else TD[k]=DivCalc

End While

k++

return ΤD[n]

<Β.>

 Θα Για D(11) Εχουμε τρεξει τον αλγοριθμο παραπανω είναι ο παρακατ πινακας.

Αλγόριθμος D(n)	Αποτέλεσμα
D(0)	0
D(1)	0
D(2)	1
D(3)	1
D(4)	1+D(2)
D(5)	1
D(6)	1+D(2)
D(7)	1
D(8)	1+D(7)
D(9)	1+D(3)
D(10)	1+D(5)
D(11)	1+D(10)
…	…..

Για  το D(11)

1.      Υπολογίζουμε D(10) ,από τον πίνακα που είναι αποθηκεμένος  και είναι  3 πράξεις  ακόμα θα  προσθέσουμε την μια πράξη η οποία  μας βοήθησε να φθάσουμε στο D11  παρατηρούμε ότι το 11 δεν διαιρείται τέλεια με τους αριθμούς προς που εχουμε στην διάθεση μας  – επιτρεπτές πράξεις. Επομένως δεχόμαστε την  ότι D(11)=D(10)+1=4 Πράξεις

D(10)=D(5)+1

D(5)=D(1)+1

Τερματισμός

<Γ.>

Οι  επαναλήψεις με είσοδο n είναι Θ(n), είναι γραμμικής πολυπλοκότητα  διότι υπολογίζω μια φορά τον πίνακα TD[n-2]  που είναι οι ελάχιστες πράξεις για κάθε D(n) αριθμό. Έπειτα ο αλγόριθμος μας είχε Θ(1)*Θ(n-2) πράξεις,( καταχωρήσεις συγκρίσεις.Δηλαδη είναι  Θ(n) πολυπλοκοτητας.

<Δ.>

Για την βέλτιστη λύση εξαρτάται πάντα ο ορισμός το τι είναι βέλτιστο, στην περίπτωση μας ως βέλτιστο εχουμε τις λιγότερες πράξεις που θα πραγματοποιήσουμε  σε έναν αριθμό ώστε αυτος να γίνει μονάδα. Για παράδειγμα D(8) εάν εφαρμόσουμε τον αλγόριθμο που θα δίνει το μικρότερο αποτέλεσμα τότε οι πράξεις που θα χρειαστούμε είναι 3

1.    8/2 =4

2.    4/2=2

3.    2/2 2

Ενώ στην περίπτωση μας με το δυναμικό προγραμματισμό είναι 2

1.    8-1=7

2.    7/7=1

Αυτό ωφηλεται στο ότι η τέλεια διαίρεση με το 7 μειώνει αρκετά τον αριθμό  που χρηστικέ να το μειώσουμε κατά ένα για να διαιρεθεί τέλεια με το 7.

Συμπεραίνουμε πως η πράξη που δίνει το μικρότερο αποτέλεσμα δεν είναι και η βέλτιστη.