[Δομημένος Πρ.]Εργασία Ε

[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 με προσοχή στα ονόματα των αρχείων!

[Αντιστοίχηση Μαθημάτων ΝΠΣ με ΠΠΣ]

Επίσημη ενημέρωση για Αντιστοίχηση Μαθημάτων ΝΠΣ με ΠΠΣ και η συζήτηση στο forum.

[AckermanMik]

Άσκηση  Ε Λήξη:19/5

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

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

Για την εισαγωγή ενός γραφήματος, που αποτελείται από Ν κορυφές, να αριθμούνται οι κορυφές από το 0 έως το Ν-1. Στη συνέχεια να ορίζεται o πίνακας connection, δύο διαστάσεων, σε κάθε γραμμή του οποίου να αντιστοιχεί και μια κορυφή του γραφήματος. Κάθε γραμμή του πίνακα να έχει τόσες θέσεις όσες είναι και οι κορυφές του γραφήματος που συνδέονται με την κορυφή στην οποία αντιστοιχεί η γραμμή (βαθμός της κορυφής). Στις θέσεις αυτές να καταχωρούνται οι αύξοντες αριθμοί των κορυφών που συνδέονται με την κορυφή που αντιστοιχεί στη γραμμή. Για την καταχώρηση των βαρών των ακμών που συνδέουν τις κορυφές να ορίζεται o πίνακας  weights, όμοιος με τον πίνακα connection, στον οποίο, σε κάθε γραμμή, να αντιστοιχεί επίσης μια κορυφή. Στον πίνακα αυτόν να έχουν αντικατασταθεί οι αύξοντες αριθμοί των κορυφών που αναγράφονται στον πίνακα connection με τα βάρη των ακμών που τις συνδέουν με την κορυφή στην οποία αντιστοιχεί η γραμμή στην οποία βρίσκονται.

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

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

[TechSupport]

Ο βαθμός κάθε κορυφής είναι ο αριθμός των κορυφών που μπορεί να συνδεθεί η κάθε κορυφή;  
Ουπς,το γράφει πιο πάνω! 

[PureForm]

αν εχω ηδη καταχωρησει οτι μια κορυφη α συνδεεται με μια αλλη κορυφη β πωσ θα τοποθετω αυτοματα,χωρισ να χρειαστει να ξαναδιαβασω, οτι η κορυφη β οτι συνδεεται με την α,αφου τωρα ο πιανακασ μασ δεν εχει συγκεκριμενο μεγεθοσ?
η απλα θα διαβαζω τισ τιμεσ και παντα ο χρηστησ θα πρεπει να δινει τιμη που σχετιζεται με την προηγουμενη?

[Αλντεμπαράν]

Η υλοποίηση της διαγραφής της κορυφής που μόλις προσπεράστηκε μπορεί να γίνει χωρίς την τροποποίηση των πινάκων connection και weight??Αν πάλι είναι αναγκαστικός αυτός ο τρόπος τότε πως στην ευχή θα χειριστούμε τα ορίσματα της συνάρτησης που θα'ναι τριπλοί pointers ??? 

[PureForm]

τι εννοει με αυτο που λεει να διαβαζει τον αυξοντα αριθμο τησ κορυφησ εκκινησησ?
το αυξοντασ που κολλαει αφου οπωσ βλεπω στο παραδειγμα διαβαζει μια κορυφη εκκινησησ και δεν υπαρχει κατι αυξων μετα
και κατι ακομα πω γινεται σε μια συναρτηση void να κανουμε αναδρομη,αμα ηταν συναρτηση int  θα μπορουσα να κανω  με return αλλα τωρα στην void δεν γινεται να χρησιμοποιησω το return next_vertex()

ps:γιατι τοσο μικρη συμμετοχη σε αυτη την ασκση ?

[TechSupport]

αν εχω ηδη καταχωρησει οτι μια κορυφη α συνδεεται με μια αλλη κορυφη β πωσ θα τοποθετω αυτοματα,χωρισ να χρειαστει να ξαναδιαβασω, οτι η κορυφη β οτι συνδεεται με την α,αφου τωρα ο πιανακασ μασ δεν εχει συγκεκριμενο μεγεθοσ?
η απλα θα διαβαζω τισ τιμεσ και παντα ο χρηστησ θα πρεπει να δινει τιμη που σχετιζεται με την προηγουμενη?

μήπως πρέπει να κάνουμε ένα είδος αναζήτησης σύμφωνα με την οποία αν π.χ. είμαστε στην κορυφή με αριθμό 4,να κάνουμε μια αναζήτηση από 0-3 και αν τη βρίσκουμε σε κάποια κορυφή από αυτές να τις βάζουμε στη γραμμή της  4.Αν δούμε πως οι στήλες έχουν συμπληρωθεί να πηγαίνουμε στην επόμενη, αλλιώς να διαβάζουμε κορυφές που να είναι μεγαλύτερες του 4 και μικρότερες από το Ν-1.επισης,τις κορυφες που διαβαζουμε  πρεπει να τις κανουμε και ταξινομηση;

[PureForm]

επισης,τις κορυφες που διαβαζουμε  πρεπει να τις κανουμε και ταξινομηση;

αυτο εγω το εχω κανει
τωρα οσα αναφορα το αλλο θεμα,με συζητησεισ με αλλα παιδια απο την σχολη καταλαβα οτι δεν χρειαζεται να δωσουμε βαση τοσο σε αυτο δηδλαδη υποτιθεται οτι μασ δινει σςστεσ τιμεσ ο χρηστησ και οχι οτι νανε
οτι γινετε γινετε παντωσ

[George_RT]

τι εννοει με αυτο που λεει να διαβαζει τον αυξοντα αριθμο τησ κορυφησ εκκινησησ?
το αυξοντασ που κολλαει αφου οπωσ βλεπω στο παραδειγμα διαβαζει μια κορυφη εκκινησησ και δεν υπαρχει κατι αυξων μετα
και κατι ακομα πω γινεται σε μια συναρτηση void να κανουμε αναδρομη,αμα ηταν συναρτηση int  θα μπορουσα να κανω  με return αλλα τωρα στην void δεν γινεται να χρησιμοποιησω το return next_vertex()

ps:γιατι τοσο μικρη συμμετοχη σε αυτη την ασκση ?

Για να επιστρέψεις τιμές από μια συνάρτηση void χρησιμοποιείς τους pointers (πάνω σε αυτό ήταν και η προηγούμενη άσκηση που κάναμε)
return σε void συνάρτηση δεν μπορείς να χρησιμοποιήσεις

αν εχω ηδη καταχωρησει οτι μια κορυφη α συνδεεται με μια αλλη κορυφη β πωσ θα τοποθετω αυτοματα,χωρισ να χρειαστει να ξαναδιαβασω, οτι η κορυφη β οτι συνδεεται με την α,αφου τωρα ο πιανακασ μασ δεν εχει συγκεκριμενο μεγεθοσ?
η απλα θα διαβαζω τισ τιμεσ και παντα ο χρηστησ θα πρεπει να δινει τιμη που σχετιζεται με την προηγουμενη?

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

[jordan_S]

Η free αποδεσμεύει ολόκληρους πίνακες ή και στοιχεία πινάκων?Εκεί που λέει δηλαδή να αφαιρείται η κορυφή εκκίνησης γίνεται με free ή με άλλο τρόπο ?

[George_RT]

Η free αποδεσμεύει ολόκληρους πίνακες ή και στοιχεία πινάκων?Εκεί που λέει δηλαδή να αφαιρείται η κορυφή εκκίνησης γίνεται με free ή με άλλο τρόπο ?

Η free απελευθερώνει χώρο που δεσμευτικέ δυναμικά δεν μπορείς να διαγράψεις της κορυφές με αυτόν τον τρόπο

[jordan_S]

Η free αποδεσμεύει ολόκληρους πίνακες ή και στοιχεία πινάκων?Εκεί που λέει δηλαδή να αφαιρείται η κορυφή εκκίνησης γίνεται με free ή με άλλο τρόπο ?

Η free απελευθερώνει χώρο που δεσμευτικέ δυναμικά δεν μπορείς να διαγράψεις της κορυφές με αυτόν τον τρόπο

ευχαριστω.και πως γινεται τελικα η διαγραφη των κορυφων?

[reservoir dog]

δηλαδη και το κοστος που θα πρεπει να τυπωσουμε ειναι και αυτο Pointer αφου η συναρτηση δεν μπορει να επιστρεψει τιμες?

[Μουργόλυκος]

δηλαδη και το κοστος που θα πρεπει να τυπωσουμε ειναι και αυτο Pointer αφου η συναρτηση δεν μπορει να επιστρεψει τιμες?

Ναι. Βασικά η εργασία αυτή είναι ένα όργιο από pointers και από pointers σε pointers...

[reservoir dog]

Αυτο δεν είναι πρόγραμμα, ξαστεριά τον Αύγουστο είναι.

[reservoir dog]

και δηλαδη πως διαγραφουμε την κορυφη απο την οποια περασαμε ηδη?  μηπως απλα ελεγχουμε και προσπερναμε?