Χαρακτικά της μιας γραμμής,ένα τοπολογικό θεώρημα και η τέχνη του πλανόδιου πωλητή (TSP art)

«…Οι βασικές ιδέες των σχεδίων μου συχνά μαρτυρούν την κατάπληξη και την απορία μου ενώπιον των νόμων της φύσης οι οποίοι λειτουργούν στον κόσμο που μας περιβάλλει.Αυτός που θαυμάζει,ανακαλύπτει ότι αυτό από μόνο του αποτελεί ένα θαύμα.

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

                                                                                                                          M.C.Escher

   Η ζωγραφική έχει άμεση σχέση με τα μαθηματικά και αυτό δεν αποτελεί είδηση. Ο Κλωντ Μελάν (1598 –1688) ένας Γάλλος χαράκτης και ζωγράφος που έζησε τον 17^ο  αιώνα  έγινε γνωστός για τα χαρακτικά προσωπογραφιών που δημιούργησε με μια ιδιαίτερη τεχνική. Οι προσωπογραφίες του αποτελούνταν από μια μόνο συνεχή σπειροειδή γραμμή που δεν τέμνει τον εαυτό της.

                                

 Το πιο γνωστό από τα έργα του ήταν το:  Η κεφαλή του Χριστού στο σουδάριο (Head of Christ on the Sudarium). Σουδάριο ήταν το πλατύ άσπρο κομμάτι υφάσματος με το οποίο τυλίγεται το κεφάλι του νεκρού.

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

  Μία συνεχής γραμμή στο επίπεδο που δεν τέμνει τον εαυτό της και τα δυο άκρα της συμπίπτουν ονομάζεται κλειστή καμπύλη Jordan.Σύμφωνα με το θεώρημα της κλειστής καμπύλης του Γάλλου μαθηματικού Camille Jordan  κάθε καμπύλη της παραπάνω μορφής  χωρίζει το επίπεδο σε δυο τομείς.Αποτελεί σύνορο για δυο χωρία. Για παράδειγμα, η παρακάτω καμπύλη Λ, διαιρεί το επίπεδο σε δυο τομείς τον Α και τον Β . Ο Α μπορούμε να που ότι είναι ο εξωτερικός τομέας Α και Β ο εσωτερικός τομέας.Επίσης αν μας δοθεί ένα σημείο Χ είναι πολύ εύκολο να δούμε αν ανήκει τον εσωτερικό ή στον εξωτερικό τομέα.

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

                         

 Το σημεια Χ και Y βρίσκονται στον  ίδιο τομέα; Υπάρχει τρόπος να το ελέγξουμε χωρίς να διατρέξουμε όλη την καμπύλη.

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

 Τα μάτια και το στόμα του προσώπου  βρίσκονται στον ίδιο τομέα; (Η λύση στα σχόλια )

 Το παραπάνω πρόσωπο, το σχεδίασα με την παλέτα σχεδίου του επεξεργαστή κειμένου της Microsoft και μου πήρε πάνω από μισή ώρα. Τι θα λεγάτε αν σας έλεγα ότι κάθε εικόνα μπορεί να σχεδιαστεί με απλή κλειστή καμπύλη που δεν τέμνει τον εαυτό της  με την χρήση ενός υπολογιστή  αν την θεωρήσουμε ως ένα χάρτη. Είναι η λεγόμενη TSP art ( Travelling Salesman Problem art σε ελεύθερη απόδοση  Η τέχνη του προβλήματος του πλανόδιου πωλητή).

  Έστω ότι ένας έμπορος πρέπει να επισκεφτεί οδικώς ν πόλεις.Προφανώς πρέπει το δρομολόγιο του,να ακολουθεί  ορισμένους κανόνες: έτσι, θα φροντίσει η διαδρομή να μην περνάει  δυο φορές από την ίδια πόλη και η κατανάλωση καυσίμου να είναι η ελάχιστη, άρα να είναι ελάχιστο και το συνολικό μήκος της διαδρομής. Φανταστείτε ότι έχουμε 5 πόλεις: Αθήνα, Αλεξανδρούπολη, Θεσσαλονίκη, Κιλκίς ,Λαμία τότε οι αποστάσεις των πόλεων μπορούν να παρασταθούν με ένα γράφημα.

   Αν θέλει να αποφασίσει ποιο δρομολόγιο είναι το καλύτερο, είναι αναγκασμένος να βρει όλες τις δυνατές διαδρομές και να αθροίσει τις αποστάσεις. Για να μεταβεί από την πρώτη πόλη στην δεύτερη έχει 4 επιλογές ,από την δεύτερη στην τρίτη 3 επιλογές από την τρίτη στην δεύτερη 2 επιλογές κ.ο.κ. Όμως κάθε διαδρομή έχει μετρηθεί δυο φορές οπότε το συνολικό πλήθος των διαδρομών είναι 4!/2  διαδρομές (4!=1x2x3x4) και να υπολογίσει 12 αθροίσματα. Το ελάχιστο άθροισμα αποτελεί και την καλύτερη διαδρομή. Δυστυχώς,αν το πλήθος των πόλεων αυξηθεί τότε η κατάσταση  για τον άτυχο πωλητή μας δυσκολεύει δραματικά. Αν οι πόλεις που έπρεπε  να επισκεφτεί ήταν  30 τότε  θα απαιτούνταν να υπολογίσει 4420880996869850977271808000000 διαφορετικά αθροίσματα. Για ν πόλεις  το πλήθος των αθροισμάτων είναι (ν-1)!/2  (όπου ν!=1x2x3x..x(ν-1)xv και διαβάζεται ν παραγοντικό) .

   Αυτό είναι το πρόβλημα του περιοδεύοντος εμπόρου ή πωλητή, το οποίο διατυπώθηκε αρχικά το 19^ο αιώνα. Το πρόβλημα είναι ανοικτό παρόλο που υπάρχει αλγόριθμος για την λύση του: Υπολογίζουμε όλα τα δυνατά αθροίσματα διαδρομών και επιλέγουμε το ελάχιστο,πρακτικά βέβαια είναι ανεφάρμοστος για μεγάλο αριθμό πόλεων ακόμα και με την χρήση υπολογιστών. Το ερώτημα είναι,υπάρχει αλγόριθμος να επιλύει το πρόβλημα σε πολυωνυμικό χρόνο ,σε χρόνο δηλαδή που να  κάνει την εφαρμογή του αλγορίθμου εκτελέσιμη και όχι να απαιτούνται εκατοντάδες χρόνια. Το πρόβλημα μέχρι σήμερα θεωρείται ότι ανήκε στην κατηγορία NP  δηλαδή πρόβλημα μεγάλης υπολογιστικής πολυπλοκότητας. Λύσεις για μεμονωμένα προβλήματα περιοδεύοντος πωλητή έχουν βρεθεί με χαρακτηριστικότερο  αυτό του David Applegate για την Σουηδία το 2004 ,όπου αυτός και η ομάδα του  έλυσαν το πρόβλημα για 24978 σουηδικές πόλεις οι οποίες  συνδέονταν με ένα δαιδαλώδες γράφημα και μια διαδρομή  συνολικού μήκους 72500 χλμ.

      

  Που κολλάει τώρα η TSP art; Τι ακριβώς είναι;  Επιλέγουμε  μια εικόνα,μια φωτογραφία,για παράδειγμα η φωτογραφία του θρυλικού μαθηματικού Πωλ Έρντος.Θεωρούμε  ν σημεία πάνω στην φωτογραφία. Τα ορίζουμε σαν πόλεις σε ένα χάρτη,τώρα με την βοήθεια λογισμικού σχεδιάζουμε την βέλτιστη διαδρομή του πωλητή η οποία σημειωτέον θα είναι μια κλειστή καμπύλη που δεν θα τέμνει τον εαυτό της. Τελικά θα προκύψει η εικόνα του παρακάτω σχήματος .  

 Στο διαδίκτυο υπάρχει πληθώρα λογισμικών ελευθέρου κώδικα που δημιουργεί εικόνες με την τεχνοτροπία TSP.

Κατάλληλο λογισμικό για να ξεδιπλώσετε τις καλλιτεχνικές ανησυχίες σας και να κάνετε μόνοι σας TSP art διατίθεται δωρεάν στο διαδίκτυο στον ιστότοπο:

 http://www.makerbot.com/blog/tag/tsp-line-art/