THMMY.gr

Συζήτηση και απορίες για την έκτη εργασία

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

Ένας αλγόριθμος που θα έδινε μια σχετικά καλή λύση, όχι τη βέλτιστη, επιλέγει την ακμή με το μικρότερο βάρος και καταχωρεί τη μια από τις κορυφές που συνδέει στην ομάδα Α και την άλλη στην Β. Στη συνέχεια διαγράφει από το γράφημα τις κορυφές αυτές και επαναλαμβάνει την διαδικασία με τις υπόλοιπες κορυφές. Οι διαδικασία σταματά όταν όλες οι κορυφές του γραφήματος καταχωρηθούν σε κάποια από τις δύο ομάδες.

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

Σημείωση

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

Για τους πίνακες connection και weight κοιτάξτε το παράδειγμα της άσκησης C.

Ο αλγόριθμος να ελέγχει μόνο ζεύγη κορυφών που συνδέονται μεταξύ τους. Να αγνοεί ζεύγη που δε συνδέονται αν και αυτά θα μπορούσαν να δώσουν καλύτερη λύση.

 

  

Επαναλαμβάνω:

Tι να πρωτοκαταλαβεις...;

Ας ξεκινησουμε με τα βασικα. Το βαρος των ακμων ειναι το μηκος τους ;

Βάρος της κάθε ακμής (που συνδέει την κορυφή i με την κορυφή j) είναι ο αριθμός που καταγράφεται στον πίνακα weight[j], που είναι ίδιος με τον weight[j]...

Αν κατάλαβα καλά ψάχνουμε την ράβδο με το μικρότερο βάρος και βαζουμε την μια κορυφη στην ομάδα Α και την άλλη στην ομάδα Β.Δεν καταλαβα αυτο που λεει με την ελαχιστη τομή.
Εχει καταλάβει κανείς για να βοηθήσει;

Θα βρίσκει την ακμή με το μικρότερο βάρος,το βάρος αυτό θα το προσθέτεις σε μια μεταβλητή (πχ sum) και μετά θα βάζεις τις 2 κορυφές της ακμής αυτής στους πίνακες Α κ Β.Μετά θα διαγράφεις τις 2 κορυφές και την ακμή.Στη συνέχεια βρίσκει από αυτά που έχουν μείνει την επόμενη ακμή με το μικρότερο βάρος και πάλι προσθέτει το νέο min  βάρος στο sum κ συνεχίζει.

Την μία την βάζουμε στην Α ομάδα και την άλλη στην Β τυχαία η όχι?

Ε ναι τυχαία.

τους πινακες  connection-weight θα τους βαζει τιμες ο χρηστης?

Ναι,ειναι οι ιδιοι ακριβως πινακες απτην ασκηση C.Αποθηκευουν τα ιδια δεδομενα που αποθηκευαν κ στην C.Μπερδεμενη εκφωνηση οπως παντα,αλλα αμα το καταλαβεις τι πρεπει να γινει,η ασκηση ειναι αρκετα ευκολη(χωρια που μπορεις να κανεις copy-paste καποια κομματια απο την ασκηση C [οπως πχ. το τμημα του κωδικα π ειχες γραψει για να γεμισεις τους πινακες weight κ connection]).

Αυτο για το οποιο ομως δεν ειμαι σιγουρος,ειναι αν θα αντιστοιχιζουμε τις κορυφες απτις ομαδες Α <------> Β ως μια προς μια.

δλδ σκεφτομαι οτι η ομαδα Α και η ομαδα Β ειναι μονοδιαστατοι πινακες (τους φανταζομαι σαν 2 στηλες). Η κορυφη στο Α [1] συνδεεται με την κορυφη στο Β [1] με βαρος πχ 3 .Αλλα επισης η κορυφη Α [1] μπορει να συνδεεται κ με την κορυφη που βρισκεται στο Β [4] με βαρος πχ. 5 .Θα παρουμε σαν βαρος μονο το 3,ή θα πρεπει να μετρησουμε και το 5?

Ξερω πως τα λεω λιγο μπερδεμενα,παντως αν κανεις καταλαβαινει τι εννοω,ας πει την αποψη του!

Αν κατάλαβα αυτό που εννοείς, οι πίνακες Α και Β θα γεμίζουν καθώς ο αλγόριθμος κάνει την διαδικασία που λέει η εκφώνηση. Η κορυφή Α(i) αντιστοιχεί στην κορυφή B(i), διότι διαγράφηκαν μαζί (λόγω της κοινής τους ακμής) μέσω του αλγορίθμου. Στο αρχικό σχήμα μπορεί όντως η κορυφή Α(i) να συνδεόταν και με άλλες κορυφές, οι οποίες αργότερα θα καταχωρηθούν σε άλλη θέση A(j) μαζί με μια άλλη κορυφή B(j). Βάρος, όμως, της ακμής που συνδέει την κορυφή Α(i) είναι η τιμή της ακμής, την οποία διάλεξε ο αλγόριθμος κατά την εκτέλεση του, και η οποία συνδέει το Α(i) με το B(i)...

Sorry αν σε μπέρδεψα παραπάνω...

Βασικα θα γινει μονο 1 προς 1 αντιστοιχιση,γιατι η εκφωνηση λεει πως θα διαγραφουν οι ακμες που συνδεουν τις κορυφες της μιας ομαδας με την αλλη,και ζηταει το αθροισμα των βαρων των ακμων που θα διαγραφουν μονο.Καταλαβαινω τι λες,δεν με  μπερδεψες.Επισης ημουν σιγουρος πως εσυ θα απαντουσες ,αρα κερδισα το στοιχημα.  8))

Μη ξεχνάς βέβαια, ότι ο αλγόριθμος μπορεί να μη χωρίσει όλες τις κορυφές σε ακριβώς δύο ομάδες. Δηλαδή μπορεί κάποιες να μείνουν "ξέμπαρκες"...

:P

Ουσιαστικα δηλαδη, χτιζω το δικτυωμα μου με την διαδικασια που ακολουθει στην C και κατοπιν εργαζομαι για τον διαχωρισμο σε Α και Β;

Ουσιαστικά, διαγράφεις μία μία τις ακμές του δικτυώματος (μαζί με τις δύο κορυφές που ενώνεται) ξεκινώντας από αυτήν με το μικρότερο βάρος. Την μία από τις δύο κορυφές που συνδεόταν η ακμή την βάζεις στην Ομάδα Α, και την άλλη στην Ομάδα Β...

Ευχαριστώ που μου το ξεκαθάρισες αυτό. Αυτό που δεν ξεκαθάρισα ακόμα είναι, πριν αρχίσω να διαγράφω, το αν πρέπει ή όχι να δημιουργήσω το δικτύωμα, με τη διαδικασία που ακολουθήσαμε και στη C.

Το δικτύωμα θα το "δημιουργήσεις" διαβάζοντας την τοπολογία του από τον χρήστη, όπως ακριβώς και στην Εργασία C, αν κατάλαβα καλά την απορία σου...

Κατάλαβες, και σ'ευχαριστω πολύ :)

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

θέλει malloc

θέλει malloc
[/quote]
ντανκε  :D

Με ποιο τρόπο θα διαγράφονται οι κορυφές? Βάζοντας στν αντιστιχο πίνακα connection καποια τιμή π.χ -1; :D

Παιδια δεν την έχω καταλάβει ακόμα.π.χ.Βρίσκω την κορυφη με το ελάχιστο βάρος και βάζω την μια απο τις δύο στην ομάδα Α και την άλλη στην ομάδα Β.Όμως με αυτές τις 2 κορυφές μπορεί να συνδεονται κι αλλες κορυφες.Τις ράβδους που ενώνουν την μια απ τις κορυφές που εχω βαλει στις ομάδες με κάποια αλλη πρεπει να τις διαγράψω κι αυτες?Δεν ξερω αν καταλαβατε...

Έχω δυο απορίες. Οι πίνακες  connection kai weight θα πρέπει να τους κάνουμε με την malloc να μην είναι τετραγωνικοί(πχ ν*ν), έτσι ώστε να έχουν το ελάχιστο απαιτούμενο μέγεθος,δεν είναι;δηλαδή κάθε γραμμή των πινάκων πρέπει να έχει μήκος ανάλογα με τον αριθμό των κορυφών με τις οποίες συνδέεται μια κορυφή. Και κάτι ακόμα , πώς θα κάνω το πρόγραμμα να διαγράφει από το γράφημα τις κορυφές αφότου τοποθετηθούν στους πίνακες Α και Β; γιατί και στην εργασία C, σε αυτό το σημείο είχα ένα κόλλημα. Α, και κάτι τελευταίο τι εννοεί στις σημειώσεις στο τέλος λέγοντας "Ο αλγόριθμος να ελέγχει μόνο ζεύγη κορυφών που συνδέονται μεταξύ τους. Να αγνοεί ζεύγη που δε συνδέονται αν και αυτά θα μπορούσαν να δώσουν καλύτερη λύση." ;

Υπάρχουν πολλοί τρόποι που μπορείς να υλοποιήσεις την διαγραφή των κορυφών. Μια ιδέα είναι ένας πίνακας deleted(N), όπου deleted(i)=0 αν η κορυφή i δεν έχει διαγραφεί και deleted(i)=1 αν η κορυφή i έχει διαγραφεί...

Ναι, λογικά θα πρέπει να διαγραφούν και αυτές... (Γιατι, λογικά, δεν γίνεται να υφίσταται ράβδος που να συνδέει μόνο ένα σημείο με το "κενό")

Οι πίνακες connection και weight, όντως, δε θα πρέπει να είναι τετράγωνοι (το μέγεθος τους θα προσδιορίζεται έτσι όπως ακριβώς το σκέφτηκες). Όσον αφορά τον τρόπο που θα διαγράφεις τις κορυφές δες λίγο πιο πάνω στο post μου. Τέλος, η σημείωση εννοεί ότι θα διαγράφονται μόνο οι κορυφές που συνδέονται με κάποια ακμή μεταξύ τους, και όχι κορυφές που δεν συνδέονται με κάποια ακμή... (Αυτό μπορεί να σου φάνηκε αυτονόητο και γι' αυτό να σε παραξένεψε η σημείωση)

Πρέπει να χρησιμοποιήσουμε realloc για τους πίνακες connection και weight αφότου διαγράφουμε στοιχεία;

Δεν χρειάζεται να διαγράψετε κάτι απο τους πίνακες. Αφότου καταχωρίσουμε κάποιες κορυφές στις ομάδες Α και Β, την επόμενη φορά αυτές δεν θα πρέπει να συμπεριληφθούν στην εύρεση της ακμής με το ελάχιστο βάρος. Εγώ το έκανα με έναν πίνακα alconn ο οποίος κρατούσε τις κορυφές που είχαν καταχωρηθεί στις ομάδες και όταν έβρισκα μια ακμή με ελάχιστο βάρος, κοιτούσα πρώτα αν οι κορυφές που δημιουργούν την ακμή βρίσκοταν στον πίνακα alconn.

Π.χ. σε ενα γραφημα με 6 κορυφες.0,1,2,3,4,5.Βρισκω οτι η ραβδος με το ελαχιστο βάρος ειναι αυτη που συνδέει την 1 με την 3.Την 1 την βαζω στην ομαδα Α και την 3 στην ομάδα Β.Μετα διαγράφω την ράβδο που ενώνει την 1 με την 3 μόνο?Δηλαδή αν υπάρχει μια ράβδος που ενώνει την 3 με την 5 την διαγράφω η όχι?

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

Κι εγω ετσι το εκανα.Πριν το ειχα γραψει εγω λαθος.Δηλαδη θα διαγραψω σε αυτην την περιπτωση την γραμμη 1 και 3 του πινακα connection και weight και μετα οπου αλλου υπαρχουν κορυφες 1 και 3

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

Ναι ελεγχω αν ειναι οι κορυφες 1 η 3 και διαγραφω τα στοιχεια των connection και weight.

Εφόσον έχουμε στη διάθεση μας του πίνακες connection και weight που αναφέρονται άμεσα σε κορυφές, τότε το λογικό είναι ότι κάνουμε να το κάνουμε σε σχέση με τις κορυφές (πχ διαγραφή). Οποιαδήποτε ενέργεια σε ακμές/ράβδους θα είναι έμμεση. Εκτώς, βέβαια, και αν κάποιος σκεφτεί κάποιον άλλο τρόπο υλοποίησης...

ο πινακς connection[j] δεν χρειαζεται στο αλγοριθμο,η κανω λαθος???

Ο πίνακας connection(i)(j) χρειάζεται στον αλγόριθμο, όπως χρειαζόταν και στην Εργασία C...

μα θα μπορουσα να παρω το weights[j]  με ελαχιστο βαρος κ να καταχωρω το κ το[j] ως κορεφες

Για να δεσμευσω μνήμη σε πίνακες πχ στον connection , αρχικα τον ορίζω σαν δείκτη  *connection [Ν][Ν-1]  στη δήλωση μεταβλητών σωστά?
Και οταν είναι να τον δεσμεύσω γράφω connection[ ][ ]=(int*)malloc(sizeof(int)*N*(N-1)) ? ι να βάλω [Ν][Ν-1] στις αγκύλες?

Οι στήλες του connection δε θα είναι ένας σταθερός αριθμός (αφού κάθε κορυφή δε συνδέεται με τον ίδιο αριθμό κορυφών). Ένας τρόπος δήλωσης (ενδεικτικός) είναι:

Exomag μπορείς να εξηγήσεις λίγο περισσότερο την έκφραση if ((connection=(int **)malloc(n*sizeof(int *)))==NULL)?
Ποιο είναι το μέγεθος του χώρου που δεσμεύει εδώ η malloc?Πόσο είναι το sizeof(int *)?

sizeof(int *) είναι όσο "ζυγίζει" ένας integer pointer στο μηχάνημα σου (συνήθως 8 byte).
Η malloc εδώ θα δεσμεύσεις n*sizeof(int *), άρα συνή8ως 8n byte.
Στην έκφραση που έγραψα αρχικά θα γίνει η εκχώρηση (connection=(int **)malloc(n*sizeof(int *))). Αν γίνει με επιτυχία τότε ως τιμή αυτής της εκχώρησης θα είναι ο pointer που θα επιστρέψει η malloc (εμάς μας νοιάζει ότι θα είναι μια οποιαδήποτε μη-μηδενική τιμή-pointer), ενώ αν δεν γίνει με επιτυχία τότε ως τιμή αυτής της εκχώρησης θα είναι ο NULL pointer. Στην πρώτη περίπτωση(=επιτυχία) η συνθήκη θα γίνει connection==NULL, που είναι ψευδής, άρα δε θα κάνει exit. Στην δεύτερη περίπτωση(=αποτυχία) η συνθήκη θα γίνει NULL==NULL, που είναι αληθής, άρα θα τερματίσει το πρόγραμμα (μέσω της συνάρτησης exit), μιας και δε μπόρεσε να δεσμευτεί ο απαιτούμενος χώρος για τον connection πίνακα (που θα έχει τις διευθύνσεις των πρώτων στοιχείων της κάθε γραμμής=κορυφής)...

Ναι αλλά εμείς για τον πίνακα connection θέλουμε να δεσμεύσουμε n*(p[0]+p[1]+...p[n-1])*sizeof(int) και όχι 8n bytes(κάθε γραμμή θα έχει p*sizeof(int))

Πρώτα ελέγχεις για τα 8*n bytes. Από εκεί και πέρα θα κάνεις ξεχωριστούς ελέγχους για κάθε malloc που χρησιμοποιείς για να κάνεις δισδιάστατο τον πίνακα.

Εδώ δεν είναι όπως στην  C , δηλαδή δεν δίνω κορυφή εκκίνησης αλλά ξεκινάω τον αλγόριθμο διαλέγοντας την ακμή με το λιγότερο βάρος και τις κορυφές που συνδέονται με αυτή ,έτσι δεν είναι ? Και τι κάνω αν προκύψουν περισσότερες από μια ακμές με το ίδιο βάρος(ελάχιστο) που συνδέονται με μια κορυφή?   

δλδ μπορούμε να γεμίσουμε τους πίνακες connection και weight οπως στην C?

Nαι απλά στην αρχή του προγράμματος θα δηλώσεις μεγέθη χρησιμοποιώντας malloc για να δεσμεύσεις την απαραίτητη μνήμη

ευχαριστω...

Όταν λέει στην εργασία "Το πρόγραμμα να εκτυπώνει, για κάθε ομάδα το άθροισμα των βαρών των ακμών που συνδέουν τις κορυφές της ομάδας Α με αυτές της ομάδας Β. " μιλάει για τις ακμές που έχουμε διαγράψει μόνο ή γενικά για όλες τις ακμές που ενώνουν ένα οποιοδήποτε στοιχέιο της ομάδας Α με ένα οποιοδήποτε στοιχείο της Β;

μπορεί και να ξαναέγινε η ερώτηση αλλά δεν πολυκατάλαβα της απάντηση...

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

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

Κατά το πώς το βλέπω εγώ πρέπει να εκτυπώνουμε τα βάρη των ακμών για κάθε κορυφή που βρίσκεται στην ομάδα Α με όλες τις κορυφές που βρίσκονται στην ομάδα Β.

Μπορεί. Αλλά για να μην πάρει διαστάσεις "Άσκηση 3 Εργασίας Πιθανοτήτων" το πράμα, ας κάνει ο καθένας ότι νομίζει and that's that...