forum.math.uoa.gr
http://forum.math.uoa.gr/

chinese postman problem
http://forum.math.uoa.gr/viewtopic.php?f=38&t=18451
Σελίδα 1 από 1

Συγγραφέας:  yann1990 [ 17 Ιούλ 2016, 19:04 ]
Θέμα δημοσίευσης:  chinese postman problem

Αστερια του Μαθηματικου Αθηνών καλως σας βρηκα! Είμαι πρώην συμφοιτητής σας που τα παράτησα και βρέθηκα σε οικονομικό τμήμα της Γερμανίας. Εχει ενσκηψει ενα προβλημα με εναν αλγόριθμο στην σχολή μου και έχω απελπιστεί. Είμαι ευγνώμων για κάθε βοήθεια! Eλπίζω να ποστάρω στο σωστό λινκ! Ίσως να είναι και τοπολογία, δεν ξερω...
Εχουμε Δίκτυο 8 επί 8 μίας σκακιέρας. Τα 81 σημεία τομής παριστάνουν διασταυρώσεις στον δρόμο. Οι διασταυρώσεις είναι συνδεδεμένες μέσω γραμμών μήκους 1 μέτρου με τις οριζόντιες και κάθετες γειτονικές διασταυρώσεις.(δηλαδή κάθε γραμμούλα στην σκακιέρα παριστάνει δρόμο). Οι οριζόντιες διαδρομές μπορουν να διασχισθούν και από τις δύο κατευθύνσεις οι 1,3,5,7,9 κάθετες διαδρομές από πάνω προς τα κάτω και οι 2,3,6,8 από κάτω προς τα πάνω. Στο μέχρι τώρα ορισμένο γράφημα μπορούν να γυρίσουν κατα ενενηντα μοιρες με την φορά του ρολογιού μόνο τα 4 τετράγωνα στο κέντρο της σκακιέρας συμπεριλαμβανομένης της κατεύθυνσής τους (ό,τι κι αν σημαίνει αυτό!). Ποιος ειναι ο μίνιμουμ αριθμος γραμμών που επισκεφθήκαμε για την βέλτιστη λύση του γραφήματος αυτού του chinese postman problem?
22; 23; 24;

Σελίδα 1 από 1 Όλοι οι χρόνοι είναι UTC + 2 ώρες [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/