Εργασία βέλτιστης διαδρομής.Περιβάλλον Matlab.

[petkon93]

Καλησπέρα σε όλους και ευχαριστώ απ'την αρχή για την όποια βοήθεια μπορείτε να μου δώσετε... Αρχικά να σας αναφέρω οτι πρώτη φορά θα πρέπει να φτιάξω κάτι τόσο πολύπλοκο σε ένα περιβάλλον όπως το Matlab.

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

Η εκφώνηση του προβλήματος:

Υποθέτουμε οτι έχουμε ένα δίκτυο λιμένων (πλήθος Ν) και ένα πλοίο μπορεί να κινείται μόνο μεταξύ λιμένων του δικτύου για τους οποίους υπάρχει δυνατή διαδρομή. Να φτιάξετε σε Matlab πρόγραμμα που να βρίσκει την οικονομικότερη διαδρομή ανάμεσα σε ένα λιμάνι αφετηρία και ένα λιμάνι προορισμό που έχουμε ορίσει στο δίκτυο με βάση τα κόστη μετάβασης στους λιμένες του δικτύου.Χωρίς βλάβη της γενικότητας θεωρούμε ότι το λιμάνι-αφετηρία είναι το πρώτο στην αλληλουχία των κόμβων και το λ.π το τελευταίο.

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

Ν(διαστάσεις 1*1) Αριθμός λιμένων.Και να δώσουμε τιμή ίση με το δεκαπλάσιο του αθρόισματος του αριθμού μητρώου ...

Β(διαστάσεις Ν*Ν) πίνακας συνδέσεων του κόστους μετάβασης κόμβων.Για 2 τυχαίους κόμβους i,jπου ισχύει i<j το στοιχείο Β(i,j) θα έχει ένα τυχαίο κόστος μετάβασης με τιμή που ανήκει στο διάστημα (1,1000) ενώ αν i>=j η τιμή θα ισούται με το 0 που σημαίνει ότι δεν υπάρχει τρόπος μετάβασης απ'το i στο j.Τέλος το στοιχείο Β(1,Ν) θα έχει τιμή κόστος πάντα ίση με 1000.

Παρατήρηση: Η τιμή στο Β(i,j) σχετίζεται με την διαδρομή απ'το i στο j ενώ το Β(j,i) απ το j στο i

Παρατήρηση: Για τη δημιουργία των τυχαίων αριθμών χρησιμοποιήστε την εντολή randi με κατάλληλα ορίσματα.(Εντολή που δεν έχω ιδέα τι κάνει,αλλά αυτό είναι το εύκολο σημείο.)Πριν την κλήση της πρέπει να έχει δωθεί η εντολή rand('seed',AM) όπου ΑΜ αριθμός μητρώου...

Στη συνέχεια καλούμε μια function με όνομα best_path και κατάλληλα ορίσματα εισόδου και εξόδου για τον υπολογισμό της οικονομικότερης διαδρομής. Η function εκτός από το κόστος της οικ. διαδρομής θα πρέπει να επιστρέφει και τους δείκτες των ενδιάμεσων λιμανιών του δικτύου που θα πρέπει να περάσει το πλοίο.(πιστεύω ότι αυτό είναι το δύσκολο σημείο...)

Κάποιες συμβουλές για το πώς θα πρέπει να είναι σύμφωνα πάντα με την εκφώνηση της άσκησης (Το σημείο που μπερδεύτηκα εντελώς)

Έστω ότι διαθέτουμε ένα δίκτυο Ν κόμβων τέτοιο ώστε ο κόμβος i να συνδέεται με τους (i+1.i+2,...,N).Δηλ. ο πίνακας Β να είναι άνω τριγωνικός,όπου όλα τα στοιχεία πάνω απ'την κύρια διαγώνιο να είναι θετικοί ακέραιοι στο διάστημα (1,1000) και τα υπόλοιπα 0. Για λόγους απλότητας θεωρούμε ότι ο κόμβος 1 είναι η αφετηρία και Ν ο προορισμός.

Πρέπει να φτιάξω:

1.πίνακα Q(1*N) που να περιέχει τους δείκτες όλων των κόμβων

2.πίνακα D(!*N) που να περιέχει το κόστος μετάβασης από τον κόμβο 1 και να θέσω αρχικά όλα τα κόστη ίσε με το άπειρο εκτός από το D(1) όπου θα έχει τιμή 0.

3.πίνακα P(1*N) που αρχικά θα έχει όλα τα στοιχεία ίσα με μηδέν.

4.μετά με την εφαρμογή της επαναληπτικής διαδικασίας όσο ο πίνακας Q(1*N)παραμένει μη κενός να βρω τα στοιχεία του Q τον δείκτη του κόμβου με το μικρότερο κόστος μετάβασης και να τον αποθηκεύσω στη μεταβλητή u,ακόμα αν το u=Ν να τερματίζει η διαδικασία όπως και να αφαιρέσω απ'το u τον πίνακα Q.Και για κάθε κόμβο v που συνδέεται με τον u

i.να κάνω τον υπολογισμό του κόστους μετάβασης Sv=D(u)+B(u,v) και

ii.εάν Sv<D(v) τότε D(v)=Sv και P(v)=u.

Το συνολικό κόστος θα προκύπτει από το στοιχείο D(N) και η διαδρομή προκύπτει από τον Ρ από:1. Έστω κενός πίνακας path(1*N)

2. u=N

3. Όσο το Ρ(u) είναι διάφορο του 0

i. αποθήκευσε το u στην αρχή του path

ii. u=P(u)

4. Αντέστρεψε τα στοιχεία του πίνακα path χρησιμοποιώντας την εντολή fliplr().

 

Μοιάζει πάρα πολύ με τον αλγόριθμο της βέλτιστης διαδρομής αλλά βρίσκω τον κώδικα τον οποίο πρέπει να φτιάξω αρκετά δύσκολο για το επίπεδό μου,παρότι μας έχει δοθεί ένας τύπος αλγορίθμου με ελεύθερο κείμενο, γι'αυτό και απευθύνομαι εδώ.Σας ευχαριστώ όλους και πάλι για τον χρόνο που σπαταλήσατε για να διαβάσετε αυτό το Post και ζητώ συγγνώμι για τα ορθογραφικά λάθη μου.

Δεν ζητώ να μου δώσετε έτοιμο τον κώδικα αλλά κάποιες ιδέες θα ήταν πολύ χρήσιμες,αν φυσικά κάποιος διαθέτει τον κώδικα ακόμα και σε κάποια άλλη γλώσσα προγραμματισμού ή ακόμα και σε notepad είναι καλοδεχούμενος. Σας ευχαριστώ και πάλι για τον πολύτιμο χρόνο σας.Αν κάποιος θέλει τα θέματα ακριβώς όπως έχουν δοθεί ας μου πει. Ευχαριστώ και πάλι.

[V.I.Smirnov]

Μακροσκοπικά κοιτώντας, πρόκειται για το πρόβλημα του περιπλανώμενου πωλητή αλλά

εδώ η απόσταση των πόλεων είναι το κόστος μετάβασης μεταξύ των λιμανιών.

Αν θεωρήσεις ότι το κόστος είναι η απόσταση, πρόκειται για το πράγμα.

 

Το σημείο που γράφεις ότι σε μπερδεύει δεν έχει καμιά δυσκολία.

Για κάθε πόλη πρέπει να είναι γνωστή η απόστασή της από όλες τις άλλες.

Στον εν λόγω πίνακα αποθηκεύονται αυτές οι αποστάσεις :

οριζοντίως η πόλη-προορισμός και καθέτως η πόλη-αφετηρία (ή αντιστρόφως, ανάλογα πώς το θεωρείς).

Αν για μια πόλη Χ καταχωρηθεί η απόστασή της από την Υ,

δεν χρειάζεται να καταχωρηθεί και η απόσταση της Υ από την Χ επειδή προφανώς είναι ίδια.

Γι' αυτό προκύπτει άνω (ή κάτω) τριγωνικός ο πίνακας : δεν χρειάζεται να συμπληρωθεί ολόκληρος.

Στην περίπτωσή σου, αντί για πόλεις έχεις λιμάνια και αντί για απόσταση το κόστος μετάβασης

(σκέψου τα κατ' αντιστοιχία με τις πόλεις).

 

 

Eίχα λύσει το πρόβλημα αυτό όταν ήμουν γ' έτος, έτσι από προσωπικό ενδιαφέρον.

Όταν είχα ξεκινήσει να μαθαίνω C++ ήταν από τα πρώτα που έλυσα.

Την ιδέα για την λύση την είχα διαβάσει από το Νumerical Recipes.

Aργότερα το μετέγραψα σε Fοrtran.

Μάλιστα είχα γράψει και ένα σύντομο κείμενο στο οποίο εξηγούσα συνοπτικά την ιδέα με

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

Τα έχω αναρτήσει σε παλαιότερο thread αλλά να, ας τα ξαναβάλω κι εδώ.

Το κείμενο μπορεί να σου δώσει κάποιες ιδέες.

 

Δεδομένου ότι η Fortran μοιάζει πολύ με το matlab στον χειρισμό πινάκων,

η μετατροπή σε matlab είναι εύκολη και θα μπορούσα να δώσω τον πηγαίο κώδικα αλλά

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

και την τεχνική metropolis που μπορεί να σε μπερδέψει.

Ο κώδικας στην Fortran (το source του exe παρακάτω) είναι λιγότερο από 500 γραμμές (μαζί με τα γραφικά).

Σε matlab μπορεί να είναι ακόμη λιγότερο.

 

 

Αυτός ο τρόπος λύσης λέγεται simulated annealing και όπως φαίνεται από το κείμενο που παραθέτω

είναι πολύ αποτελεσματικός : επιτυγχάνει μείωση της αρχικής τυχαίας απόστασης εως και 80%

(και φτάνει και το 90% αν εφαρμοστεί βοηθητικά η τεχνική metropolis).

 

-

travelling sallesman problem.zip

το πρόβλημα του περιπλανώμενου πωλητή.pdf

Επεξ/σία 15 Ιανουαρίου 2012 από V.I.Smirnov

[petkon93]

Ευχαριστώ πάρα πολύ. Ελπίζω με τις σημειώσεις σου να καταφέρω και εγώ κάτι. Γνωρίζω ότι είναι ένα πολύ κοινό πρόβλημα απλά ο τρόπος με τον οποίο έχει δοθεί η άσκηση είναι που χειροτερεύει την κατάσταση.

[V.I.Smirnov]

Kοίταξε, αγνόησε αυτά που γράφω για την τεχνική metropolis, εσύ δεν τη χρησιμοποιείς.

Tα υπόλοιπα είναι ίδια.

 

Επίσης, εφόσον η διαδρομή δεν είναι κλειστή,

δεν χρειάζεται να εξεταστεί η περίπτωση όπου δοκιμάζεται η εναλλαγή πρώτης και τελευταίας πόλης.

 

Τέλος, θα μπορούσα να σου υποδείξω ακριβώς το βιβλίο απ΄ όπου διάβασα κάποτε την ιδέα

αλλά θα δυσκολευτείς να παρακολουθήσεις το κείμενο.

Αν νομίζεις ότι θα μπορέσεις να βγάλεις άκρη κοιτώντας τον κώδικά μου,

στείλε μου pm να σου τον δώσω...

 

-

[petkon93]

Άμα δεν σου είναι δύσκολο πιστεύω ότι θα βοηθούσε το βιβλίο σίγουρα θα είναι καλύτερο απ'όλα όσα έχω διαβάσει για το συγκεκριμένο κώδικα τις τελευταίες βδομάδες.

[V.I.Smirnov]

Το βιβλίο γράφει και κάνει ότι κι εγώ αλλά οι εξηγήσεις και ο κώδικας που δίνει

είναι πολύ πιο δύσκολο να τα παρακολουθήσεις.

Εν πάση περιπτώση, θα σου πω σε pm...

 

-

[strat92man]

Ασχετο: για προπτυχιακό μάθημα είναι η εργασία ; και αν ΝΑΙ για ποιο αν επιτρέπεται ;

[V.I.Smirnov]

Εγώ πάντως την είχα κάνει για μένα.

 

Όταν σε κάποιο μάθημα ανέφερα στον καθηγητή ότι το είχα ασχοληθεί,

μου είπε "εσύ δεν θα πάρεις την εργασία των άλλων, θα φέρεις αυτό".

Γι αυτό έφτιαξα και τα διαγράμματα στο κείμενο - αλλιώς εμένα μου αρκούσε το πρόγραμμα...

 

Παρεμπιπτόντως, αργότερα το έλυσα και με νευρωνικά δίκτυα στην C++ αλλά

η παραπάνω μέθοδος μου άρεσε περισσότερο και την θυμάμαι απο τότε.

 

-

[petkon93]

Είναι εργασία για το μάθημα του προγραμματισμού στο Τ.Ε.Ι Αθήνας.