chinese postman problem

[yann1990]

Καλησπέρα! Σπουδάζω στην Γερμανία και έχω το παρακάτω γραφικό πρόβλημα, το λεγόμενο chinese postman problem. Μπορεί κανείς να με βοηθήσει;

Εχουμε Δίκτυο 8 επί 8 μίας σκακιέρας. Τα 81 σημεία τομής παριστάνουν διασταυρώσεις στον δρόμο. Οι διασταυρώσεις είναι συνδεδεμένες μέσω γραμμών μήκους 1 μέτρου με τις οριζόντιες και κάθετες γειτονικές διασταυρώσεις. Οι οριζόντιες διαδρομές μπορουν να διασχισθούν και από τις δύο κατευθύνσεις οι 1,3,5,7,9 κάθετες διαδρομές από πάνω προς τα κάτω και οι 2,3,6,8 από κάτω προς τα πάνω. Στο μέχρι τώρα ορισμένο γράφημα μπορούν να γυρίσουν κατα ενενηντα μοιρες με την φορά του ρολογιού μόνο τα 4 τετράγωνα στο κέντρο της σκακιέρας συμπεριλαμβανομένης της λκατεύθυνσής τους. Ποιος ειναι ο μίνιμουμ αριθμος γραμμών που επισκεφθήκαμε για την βέλτιστη λύση του γραφήματος του chinese postman problem?

22; 23; 24;