Anubis13 Δημοσ. 29 Μαΐου 2010 Δημοσ. 29 Μαΐου 2010 Εψαξα και διαβασα οτι βρισκει τα συντομοτερα μονοπάτια για κατευθυνομενους γραφους με μη αρνητικα βαρη. Τι σημαινει μη αρνητικα βάρη και δεύτερη απορία? Πότε δεν μπορεί ο αλγόριθμος να βρει τα συντομότερα μονοπάτια?
eliascm21 Δημοσ. 29 Μαΐου 2010 Δημοσ. 29 Μαΐου 2010 Εψαξα και διαβασα οτι βρισκει τα συντομοτερα μονοπάτια για κατευθυνομενους γραφους με μη αρνητικα βαρη. Τι σημαινει μη αρνητικα βάρη και δεύτερη απορία? Πότε δεν μπορεί ο αλγόριθμος να βρει τα συντομότερα μονοπάτια? Συντομότερο μονοπάτι σημαίνει ότι πρέπει να βρεις την διαδρομή από έναν κόμβο σε έναν άλλο έτσι ώστε να ελαχιστοποιούνται τα βάρη των ακμών από τις οποίες περνάει. Αν τα βάρη αυτά είναι αρνητικά, τότε ο αλγόριθμος δεν δουλεύει. Δες και εδώ http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Anubis13 Δημοσ. 29 Μαΐου 2010 Μέλος Δημοσ. 29 Μαΐου 2010 Την κοιταξα την wikipedia ακομα δεν το ποιανω..Μαλλον θα πρεπει να βρω κανα χειροπιαστο παραδειγμα.
V.I.Smirnov Δημοσ. 29 Μαΐου 2010 Δημοσ. 29 Μαΐου 2010 Tι δεν πιάνεις, απλούστατο είναι. Mη αρνητικά βάρη σημαίνει ότι το μέγεθος που αντιπροσωπεύουν οι ακμές των κόμβων και που χρησιμοποιείται στις πράξεις για να βρεθεί η συντομότερη διαδρομή, είναι θετικό ή μηδέν. Το παρακάτω είναι ένα χειροπιαστό παράδειγμα που το έλυσα κάποτε με τον αλγόριθμο Dijkstra για να τον μάθω. Έστω ότι θέλεις να βρεις την συντομότερη διαδρομή μεταξύ κάποιων πόλεων. Φτιάχνεις ένα γράφημα όπου σε κάθε κόμβο αντιστοιχεί μια πόλη. Οι ακμές που συνδέουν τους κόμβους θα αντιστοιχούν στις συνδέσεις-δρόμους μεταξύ των πόλεων. Ως βάρος κάθε ακμής θα τεθεί η απόσταση των δύο πόλεων που βρίσκονται στους δυο κόμβους της ακμής. Ο αλγόριθμος Dijkstra θα βρει την συντομότερη διαδρομή από κάποιον επιλεγμένο κόμβο-αφετηρία (πόλη) προς όλους τους άλλους κόμβους-πόλεις. Θεμελιωδώς, ο αλγόριθμος αυτός εξετάζει τις διαδρομές θεωρώντας ότι όταν προστίθεται μιαν ακμή, το συνολικό μήκος της διαδρομής από την αφετηρία αυξάνεται πάντοτε. Συνεπώς για να δουλέψει πρέπει οι "αποστάσεις" (βάρη) να είναι θετικές. Σε προβλήματα όπου το βάρος κάθε ακμής μπορεί να είναι αρνητικό, αυτό δεν ισχύει διότι αν προστεθεί αρνητική τιμή το συνολικό μήκος της διαδρομής θα μειωθεί αντί να αυξηθεί όπως προϋποθέτει ο αλγόριθμος. Ουσιαστικά, στην περίπτωση όπου τα βάρη είναι μη αρνητικά, αναζητώνται οι συντομότερες μεταβάσεις μεταξύ των κόμβων. Στην δεύτερη όπου επιτρέπονται και αρνητικές τιμές, αναζητείται η διαδρομή που έχει τις περισσότερες αρνητικές τιμές διότι όσοι πιο πολλοί αρνητικοί αριθμοί προστίθενται τόσο η συνολική τιμή μικραίνει. Τέτοιοι αλγόριθμοι είναι του Floyd, Jonson, Bellman-Ford κ.α. Θα μπορούσε να κάποιος να σκεφτεί να προσθέσει μια κατάλληλη θετική σταθερά σε όλες τις ακμές για μετατρέψει ένα γράφημα με αρνητικά βάρη σε ένα που έχει μόνον θετικά. Έτσι στο νέο γράφημα μπορεί να εφορμοστεί ο αλγόριθμος Dijkstra. Ωστόσο το αποτέλεσμα θα είναι λάθος !!! Για πιο πολλές λεπτομέρειες πρέπει να διαβάσεις....
Προτεινόμενες αναρτήσεις
Αρχειοθετημένο
Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.