Η βιομηχανία του θεάματος, το Χόλιγουντ, αρκετές φορές ασχολήθηκε με τα μαθηματικά , ποιος δεν θυμάται το "π", "ο ξεχωριστός Γουίλ Χάντινγκ" ,"ένας υπέροχος άνθρωπος" ακόμα και ο"Κωδικός Αίνιγμα" και πολλές-πολλές άλλες ταινίες. Σε λίγες εβδομάδες λοιπόν βγαίνει στην μεγάλη οθόνη μια νέα ταινία που έχει ως κύριο θέμα το πολύ γνωστό " πρόβλημα του περιοδεύοντος πωλητή" .
Το πρόβλημα έχει ως εξής:
Έστω ότι ένας έμπορος πρέπει να επισκεφτεί οδικώς ν πόλεις .Προφανώς πρέπει το δρομολόγιο του να ακολουθεί ορισμένους κανόνες : έτσι, θα φροντίσει η διαδρομή να μην περνάει δυο φορές από την ίδια πόλη και η κατανάλωση καυσίμου να είναι η ελάχιστη, άρα να είναι ελάχιστο και το συνολικό μήκος της διαδρομής. Φανταστείτε ότι έχουμε 5 πόλεις Αθήνα, Αλεξανδρούπολη, Θεσσαλονίκη, Κιλκίς , Λαμία τότε οι αποστάσεις των πόλεων μπορούν να παρασταθούν με ένα γράφημα.
%20(210%20%C3%97%20140%20mm)%20(1).jpg)
Αν θέλει να αποφασίσει ποιο δρομολόγιο είναι το καλύτερο είναι αναγκασμένος να βρει όλες τις δυνατές διαδρομές και να αθροίσει τις αποστάσεις .Το μόνο που έχει να κάνει είναι να σχεδιάσει 4!/2 διαδρομές ( 4!=1x2x3x4) και να υπολογίσει 12 αθροίσματα. Το ελάχιστο άθροισμα αποτελεί και την καλύτερη διαδρομή. Δυστυχώς, αν το πλήθος των πόλεων αυξηθεί τότε η κατάσταση για τον πωλητή δυσκολεύει δραματικά . Αν οι πόλεις που έπρεπε να επισκεφτεί ήταν 30 τότε θα απαιτούνταν να υπολογίσει 4420880996869850977271808000000 διαφορετικά αθροίσματα. Για ν πόλεις το πλήθος των αθροισμάτων είναι (ν-1)!/2 (οπού ν!=1x2x3x..x(ν-1)xv και ν! διαβάζετε ν παραγοντικό).
Αυτό είναι το πρόβλημα του περιοδεύοντος εμπόρου ή πωλητή, το οποίο διατυπώθηκε αρχικά το 19ο αιώνα. Το πρόβλημα είναι ανοικτό παρόλο που υπάρχει ένας αλγόριθμος για την λύση του: Υπολογίζουμε όλα τα δυνατά αθροίσματα διαδρομών και επιλέγουμε το ελάχιστο , πρακτικά βεβαία είναι ανεφάρμοστος για μεγάλο αριθμό πόλεων ακόμα και με την χρήση υπολογιστών .Το ερώτημα είναι ,υπάρχει αλγόριθμος να επιλύει το πρόβλημα σε πολυωνιμικο χρόνο , σε χρόνο δηλαδή που να κάνει την εφαρμογή του αλγορίθμου εκτελέσιμη και όχι να απαιτούνται εκατοντάδες χρόνια. Το πρόβλημα μέχρι σήμερα θεωρείται ότι ανήκε στην κατηγορία NP (Δείτε σχετική παλιότερη ανάρτηση ) δηλαδή πρόβλημα μεγάλης υπολογιστικής πολυπλοκότητας. Λύσεις για μεμονωμένα προβλήματα περιοδεύοντος πωλητή έχουν βρεθεί με χαρακτηριστικότερο αυτό του David Applegate για την Σουηδία το 2004, όπου αυτός και η ομάδα του έλυσαν το πρόβλημα για 24978 σουηδικές πόλεις οι οποίες συνδέονταν με ένα δαιδαλώδες γράφημα και μια διαδρομή συνολικού μήκους 72500 χλμ.(Δείτε στον σύνδεσμο και την παρακάτω εικόνα)
Δείτε και το τρέιλερ της ταινίας:
Μια ενδιαφέρουσα μεταπτυχιακή διπλωματική.
http://nemertes.lis.upatras.gr/jspui/bitstream/10889/6347/1/diplomatiki_Nikolas_Stylianou.pdf
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου