Εργασία 2 - Moodle [2013-14]

[pefraimi]

Εδώ μπορούν να υποβληθούν απορίες και παρατηρήσεις για την εργασία 2 (Moodle) των Δομών Δεδομένων 2013-14,

Παύλος.-

[alex4]

Για το graph search με bfs:
-πως θα καθορίζουμε το σύνολο των κόμβων στην δήλωση του πίνακα;
-σε τι αντιστοιχιζεται η boolean discovered που έχει το βιβλίο στο project;
-ποιο είναι το όρισμα και ποια η έξοδος του bfsTravelsarIDs; δηλαδή πως θα τον ορίσουμε και μετα θα τον επεξεργαστούμε;

[pefraimi]

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

Για το graph search με bfs:
-πως θα καθορίζουμε το σύνολο των κόμβων στην δήλωση του πίνακα;

Μια λύση είναι να χρησιμοποιήσετε κάποια δυναμική δομή δεδομένων (πχ. LinkedList) και στο τέλος
προτού τερματίσει η μέθοδος να μετατρέψετε τη δομή αυτή σε int[] κατάλληλου μεγέθους.

-σε τι αντιστοιχίζεται η boolean discovered που έχει το βιβλίο στο project;

Το συζητήσαμε αρκετά στο μάθημα αυτό. Οι αλγόριθμοι αναζήτησης πρέπει να καταγράφουν
ποιος κόμβους έχουν συναντήσει ή επεξεργαστεί. Θα πρέπει να χρησιμοποιήσετε κάποια κατάλληλη
δομή της επιλογής σας (σκεφτείτε εάν σας βολεύει πίνακας boolean ή κάτι πιο σύνθετο).
Θα πρέπει να προσέξετε ότι στη BFS το βιβλίο το ονομάζει "Discovered" ενώ στη DFS "Explored".
Δεν είναι τυχαίο αυτό.

-ποιο είναι το όρισμα και ποια η έξοδος του bfsTravelsarIDs; δηλαδή πως θα τον ορίσουμε και μετα θα τον επεξεργαστούμε;

Το λέει η εκφώνηση αυτό. Η είσοδος στις bfsTraversal/dfsTraversal είναι το αντικείμενο Node του κόμβου εκκίνησης και η έξοδος
ένα array int[] με τα ID των κόμβων όπως τα απαριθμεί η κάθε μέθοδος αναζήτησης.
Εδώ, σε αντίθεση με την εργασία GraphSearch οι κόμβοι έχουν ID's από 0 μέχρι n-1.
Επιπλέον εδώ και πάλι σε αντίθεση με την εργασία GraphSearch είναι σημαντικό να υλοποιηθούν
αυστηρά οι DFS και BFS ώστε η σειρά επεξεργασίας των κόμβων να είναι ακριβώς αυτή που
προβλέπει η κάθε μέθοδος. Αντίθετα στην εργασία GraphSearch αρκεί να εξερευνήσετε όλο
το γράφημα χωρίς να είναι τόσο κρίσιμη η σειρά επεξεργασίας των κόμβων.

Παύλος.-

[pefraimi]

Ερωτήσεις - Απαντήσεις (FAQ) για την εργασία 2

Στα έγγραφα στο eClass και στην ιστοσελίδα του μαθήματος έχει αναρτηθεί ένα κείμενο με ερωτήσεις και απαντήσεις σε ζητήματα που αφορούν την εργασία 2,

Παύλος.-

[paradrag]

Τεστάρω τον κώδικά μου ,και μου εμφανίζει αποτελέσματα μόνο για την dfs μεθοδο. Πώς μπορώ να δω τα αντίστοιχα της bfs? εχω γραψει και τις δυο μεθόδους και επιστρέφω πίνακα και απο τις δυο.

[akoutsia]

Τεστάρω τον κώδικά μου ,και μου εμφανίζει αποτελέσματα μόνο για την dfs μεθοδο. Πώς μπορώ να δω τα αντίστοιχα της bfs? εχω γραψει και τις δυο μεθόδους και επιστρέφω πίνακα και απο τις δυο.

Στην περίτωση της εργασίας με την διάτρεξη γραφημάτων, εντός του test για κάθε γράφημα, γίνεται πρώτα δοκιμή της bfsTraversal και αν αυτή λειτουργεί σωστά, τότε δοκιμάζεται, πάνω στο ίδιο γράφημα, και η dfsTraversal. Όταν για ένα test όλα λειτουργούν σωστά δεν εμφανίζεται τίποτα. Άρα για να σου εμφανίζει μηνύματα για την dfsTraversal και όχι για την bfsTraversal σημαίνει ότι έχεις υλοποιήσει σωστά την bfsTraveral (και άρα δεν εμφανίζονται μηνύματα γι' αυτήν) και λανθασμένα την dfsTraveral.

[paradrag]

Ωραία! Ευχαριστώ

[lef]

Για την graph traversal, θα πρέπει να την λύσουμε με τον τρόπο που προτείνεται στην 3η εργασία, δηλαδή με χρήση των stack και queue?

Επίσης έχουμε σαν είσοδο το startNode. Με ποιόν τρόπο βρίσκουμε το ID του?

[paradrag]

Για την graph traversal, θα πρέπει να την λύσουμε με τον τρόπο που προτείνεται στην 3η εργασία, δηλαδή με χρήση των stack και queue?

Ναι...queue για την bfs και stack για την dfs.

Επίσης έχουμε σαν είσοδο το startNode. Με ποιόν τρόπο βρίσκουμε το ID του?

με την getId()

[giorgos_iraklio]

Το moodle δεν λειτουργεί ώστε να τρέξω τους κωδικές μου!Εμφανίζει errors πριν καν αρχίσει η διάτρεξη

[pefraimi]

Έχει ενημερωθεί ο υπεύθυνος του συστήματος και το κοιτάει. Μάλλον πρέπει να είναι εντάξει τώρα,
Παύλος.-