Hanoi Towers...

Διατύπωση του προβλήματος αναζήτησης
http://www.dynamicdrive.com/dynamicindex12/towerhanoi.htm
o Αρχική κατάσταση: 3 δίσκοι είναι τοποθετημένοι σ΄ένα στύλο αφετηρίας (tower1) από το μεγαλύτερο προς το μικρότερο (από τη βάση προς τη κορυφή)
o Ενέργειες: Μετακίνησε τους 3 δίσκους από το στύλο αφετηρίας (tower1) στο στύλο προορισμού(tower3) με τέτοιο τρόπο ώστε ένας δίσκος να μην είναι ποτέ τοποθετημένος επάνω σ΄ ένα μικρότερο δίσκο.
Για να μεταφερθούν n=3 δίσκοι από το στύλο αφετηρίας στο στύλο προορισμού πρέπει
 Να μεταφερθεί ένας δίσκος από το πύργο αφετηρίας στο πύργο προορισμού
 Να μεταφερθεί ένας δίσκος από το πύργο αφετηρίας στο ενδιάμεσο πύργο
 Να μεταφερθεί ένας δίσκος από το πύργο προορισμού στον ενδιάμεσο πύργο
 Να μεταφερθεί ένας δίσκος από το πύργο αφετηρίας στον πύργο προορισμού
 Να μεταφερθεί ένας δίσκος από τον ενδιάμεσο πύργο στο πύργο αφετηρίας
 Να μεταφερθεί ένας δίσκος από τον ενδιάμεσο πύργο στον πύργο προορισμού
 Να μεταφερθεί ένας δίσκος από το πύργο αφετηρίας στον πύργο προορισμού
o Κόστος κίνησης : Οι αριθμοί στις παρενθέσεις δηλώνουν τους κόμβους ενώ ο αριθμός δίπλα με το πορτοκαλί χρώμα είναι το κόστος. Στους κόμβους που δεν οδηγούν στη βέλτιστη λύση το κόστος χ δεν είναι το μικρότερο από τους κόμβους του συνόρου στο οποίο ανήκουν.


o Για να βρούμε πόσες κινήσεις είναι απαραίτητες για να λυθεί το πρόβλημα (καλύτερη λύση) (Hanoi Towers για n δίσκους σκεφτόμαστε ως εξής:
Αφού για n=3 απαιτούνται 7 κινήσεις
για n=4 απαιτούνται 15 κινήσεις
για n=5 απαιτούνται 31 κινήσεις
για n=6 απαιτούνται 63 κινήσεις
κλπ

O ελάχιστος αριθμός κινήσεων (καλύτερη λύση) που απαιτούνται:

ο αριθμός των κινήσεων Κ3 που απαιτούνται για n=3 δίσκους είναι Κ3 = 2*n+1
ο αριθμός των κινήσεων Κ4 που απαιτούνται για n=4 δίσκους είναι Κ4 = 2* Κ3+1
.
.
.
ο αριθμός των κινήσεων Κn που απαιτούνται για n δίσκους είναι Κn = 2* Κ(n-1)+1
δηλαδή οι καλύτερες λύσεις Kn για n=4,5,6,…. είναι μια ακολουθία αριθμών που ο επόμενος προκύπτει από τον προηγούμενο από τη σχέση: Κn = 2* Κ(n-1)+1

Αν ο παίχτης ακολουθήσει άλλη πορεία δηλαδή οδηγηθεί στη κατάσταση που περιγράφει ο κόμβος (3) ή κάποια που περιγράφεται από τους κόμβους (τελίτσες) θα χρειαστεί περισσότερα βήματα για να φτάσει στη λύση.



o Κατάσταση στόχου: 3 δίσκοι είναι τοποθετημένοι σ΄ένα στύλο προορισμού (tower3) από το μεγαλύτερο προς το μικρότερο (από τη βάση προς τη κορυφή)
Μπορούμε να παραστήσουμε το πρόβλημα με ένα γράφο(πληροφορία από: http://en.wikipedia.org/wiki/Tower_of_Hanoi)
όπου οι κόμβοι αντιπροσωπεύουν τις καταστάσεις που βρίσκονται οι δίσκοι και οι ακμές αντιπροσωπεύουν τις κινήσεις. Για n=3
Συμβολισμοί: a=T1
b=T2
c=T3
aaa = και οι τρεις δίσκοι βρίσκονται στο στύλο Τ1 (αρχική κατάσταση)
ccc= και οι τρεις δίσκοι βρίσκονται στο στύλο Τ3 (κατάσταση προορισμού)

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


O αλγόριθμος που θα χρησιμοποιήσω είναι ο UCS (αναζήτηση ομοιόμορφου κόστους ) ο οποίος επεκτείνει τον κόμβο του συνόρου που έχει το χαμηλότερο κόστος.
Για n αριθμό κόμβων
Καθώς προστίθενται περισσότεροι δίσκοι στη γραφική απεικόνιση του παιχνιδιού θα μοιάζει με fractal σχήμα. Αντίστοιχα όπως παραπάνω (για n δίσκους) κάθε τρίγωνο αντιστοιχεί στις κινήσεις του αντίστοιχου μεγέθους δίσκου


Κατασκευάζω το δέντρο που αντιστοιχεί στο παραπάνω γράφο για n=3.

Οι κόμβοι σ΄ ένα δέντρο αναζήτησης μπορούν να παρασταθούν με μια δομή με πέντε στοιχεία:
o State: Αρχική κατάσταση στην οποία αντιστοιχεί ο κόμβος
o parentNode: Ο κόμβος του δένδρου αναζήτησης από τον οποίο προήλθε ο τρέχων κόμβος.
o Action: Η ενέργεια που πραγματοποιήθηκε για να παραχθεί ο τρέχων κόμβος.
o pathCost: Το κόστος του μονοπατιού από την αρχική κατάσταση μέχρι τον τρέχοντα κόμβο.
o Depth: Το πλήθος των κόμβων στο μονοπάτι από την ρίζα του δέντρου μέχρι τον τρέχοντα κόμβο.
Κατασκευάζω το δέντρο που αντιστοιχεί στο παραπάνω γράφο για n=3.



O παράγοντας διακλάδωσης b=2
Το μέγεθος χώρου καταστάσεων O(b1+[c*/e )
Το C* = Κn Και το ε=1