THMMY.gr

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

η συναρτηση next_vertex θα ειναι περιπου σαν την ακηση C ή βγαινει
και πιο απλα, γιατι εχω μπερδευτει με τοσους pointers;

επισης εκεινη η recursion διαδικασια ειναι στην ουσια ενα loop;

και για να μην το ξεχασω πως θα καλεσει η συναρτηση τον εαυτο της;

 :( :( :(

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

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

μηπωσ δεν εχεισ δεσμευσει σωστα την μνημη?

τελικα την κορυφη απο την οποια περασαμε πως τη διαγραφουμε; :-\

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

υπάρχει λυμένη η ίδια άσκηση εκτός του να χρησιμοποιείς συνάρτηση για να κάνει την διαδικασία. Δείτε τις Εργασίες Κορτέση 2011 η άσκηση F. Προσωπικά δεν ξέρω πως να περάσω την θέση από την main στην συνάρτηση και τουμπαλιν.

+1

Μπορείς να περάσεις έναν "πίνακα 2 διαστάσεων", και να τροποποιήσεις τα περιεχόμενά του κάπως έτσι:


Εγώ θα χρησιμοποιούσα ένα πίνακα για τα weights (size NxN float), ένα πίνακα για το άμα έχουμε περάσει από το συγκεκριμένο μονοπάτι (size N*N bool) και έναν πίνακα στον οποίο θα αποθηκέυουμε την διαδρομή που επιλέγουμε (size N, int). Την μνήμη για όλους τους πίνακες θα την δέσμευα στην main.