[Δομημένος Προγραμματισμός] Άσκηση C (Hμ/νία λήξης δηλώσεων: 04/05/2014)

[Thmmy.gr portal]

  Thmmy.gr portal
   Forum
   Downloads
   Ενεργ. Λογαριασμού
   Επικοινωνία
  
  Χρήσιμα links
   Σελίδα τμήματος
   Βιβλιοθήκη Τμήματος
   Elearning
   Φοιτητικά fora
   Πρόγραμμα Λέσχης
   Πρακτική Άσκηση
   Ηλεκτρονική Εξυπηρέτηση Φοιτητών
   Διανομή Συγγραμμάτων
   Ψηφιακό Καταθετήριο Διπλωματικών
   Πληροφορίες Καθηγητών
   Instagram @thmmy.gr
   mTHMMY
  
  Φοιτητικές Ομάδες
   ACM
   Aristurtle
   ART
   ASAT
   BEAM
   BEST Thessaloniki
   EESTEC LC Thessaloniki
   EΜΒ Auth
   IAESTE Thessaloniki
   IEEE φοιτητικό παράρτημα ΑΠΘ
   SpaceDot
   VROOM
   Panther
  

THMMY.gr Web

Helios_MultiScribbles2SMF Default ThemeSMFone_Blue

[Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads]

Είσαι πρωτοετής;... Καλώς ήρθες! Μπορείς να βρεις πληροφορίες εδώ. Βοήθεια για τους καινούργιους μέσω χάρτη.

Κατεβάστε εδώ το Android Application για εύκολη πρόσβαση στο forum.

Ανεβάζετε τα θέματα των εξετάσεων στον τομέα Downloads με προσοχή στα ονόματα των αρχείων!

[RFed the King]

Άσκηση C

Σε ένα πλήρες γράφημα με N κορυφές η κάθε κορυφή του συνδέεται με όλες τις άλλες με ακμές  η κάθε μια από τις οποίες έχει ένα ορισμένο βάρος. Στο γράφημα αυτό ζητείται να βρεθεί η διαδρομή η οποία περνά, μια φορά, από όλες τις κορυφές του γραφήματος και το άθροισμα των βαρών των ακμών από τις οποίες περνά να είναι ελάχιστο (Πρόβλημα του περιοδεύοντας εμπόρου).

Για να βρεθεί μια τέτοια διαδρομή που να δίνει μια καλή λύση (όχι τη βέλτιστη) ακολουθείται ο εξής αλγόριθμος. Επιλέγεται μια κορυφή ως αρχική κορυφή εκκίνησης. Ως επόμενη κορυφή επιλέγεται αυτή που συνδέεται με την κορυφή εκκίνησης με το μικρότερο βάρος. Η κορυφή εκκίνησης διαγράφεται από το γράφημα και η διαδικασία επαναλαμβάνεται θέτοντας ως κορυφή εκκίνησης την επόμενη κορυφή. Η διαδικασία συνεχίζεται μέχρι να καλυφθούν όλες οι κορυφές του γραφήματος. Επειδή με την πιο πάνω διαδικασία η επιλογή της αρχικής κορυφής εκκίνησης επηρεάζει το τελικό αποτέλεσμα η διαδικασία εφαρμόζεται διαδοχικά χρησιμοποιώντας μια προς μία όλες τις κορυφές του γραφήματος ως αρχικές κορυφές εκκίνησης.

Να γραφεί το πρόγραμμα που υλοποιεί τον πιο πάνω αλγόριθμό.

 

Βοηθητικές παρατηρήσεις
     Για την καταχώρηση των βαρών των ακμών του γραφήματος να ορίσετε τον πίνακας dis τύπου ΝxΝ ο οποίος, ως τιμή για το στοιχείο dis[j], να έχει το βάρος της ακμής που συνδέει την κορυφή i με την κορυφή j.

 

[sg31a]

τον αριθμο των κορυφών τον δίνει ο χρήστης, οπότε την μνήμη για τους πινακες την δεσμευουμε με malloc, or not?

[jin]

Δε να εχει πει malloc ακομα.Οποτε μαλλον κανε το οριζοντας ως max ενα αυθαιρετο αριθμο...

[jordan_S]

ιδεα μου ειναι η ειναι ιδια με την περσινη την τριτη ? 

[KGA]

Γεια σου τζορνταν!!

[xionanthropos]

έχει κανείς καμιά ιδέα για το πως να κάνεις exclude τις προηγούμενες κορυφές που έχεις χρησιμοποιήσει στην παρούσα διαδρομή;