Δομές Δεδομένων - Εργασία 3 [2017-18]

Re: Δομές Δεδομένων - Εργασία 3 [2017-18]

Δημοσίευσηαπό James » 19 Ιαν 2018, 17:53

Xristos97 έγραψε:Στον ελεγχο εμφανιζεται λαθος για τον πινακα through για ενα στοιχειο παρολο που αυτο το στοιχειο οντως προκυπτει απο αυτο που περιεχεται στον through. Αν ενα στοιχειο προκυπτει απο διαφορους κομβους δεν μετραει η σειρα με την οποια εγινε η προσπελαση; Πρεπει ο through να περιεχει τον κομβο απο οπου προεκυψε το εκαστοτε στοιχειο και αυτος ο κομβος να ειναι ο μικροτερος ακομα και αν φτασαμε στο στοιχειο πρωτα απο αλλο κομβο ;

Σε ποιον αλγόριθμο αναφέρεσαι; Γράψε εδώ ποιο είναι το test case στο οποίο αναφέρεσαι, δηλαδή κάνε αντιγραφή το γράφημα και τον source κόμβο για να το καταλάβω λίγο καλύτερα τι εννοείς.
(Μόνο) James
Άβαταρ μέλους
James
Διαχειριστής
 
Δημοσιεύσεις: 1740
Εγγραφή: 08 Ιαν 2008, 22:29
Φοιτητής ΗΜΜΥ: Όχι

Re: Δομές Δεδομένων - Εργασία 3 [2017-18]

Δημοσίευσηαπό Xristos97 » 19 Ιαν 2018, 18:44

bfs

test case :52 source :11 failure :"wrong through to 4 for case source 11 , expected <13> but was <16> ,graph :

0->16
0->8
0->10
0->12
1->16
1->16
1->3
1->8
1->13
1->14
2->17
2->10
2->11
3->0
3->4
3->10
3->12
3->15
4->2
4->3
4->6
4->10
5->0
5->16
5->12
5->13
6->3
6->5
6->8
6-> 12
7->0
7->17
7-> 2
8->9
8->14
8->15
9->17
9->16
9->11
9->14
9->15
10->1
10->4
10->6
10->8
11->5
11->6
11->9
12->6
12->8
12->10
13->17
13->4
13->7
13->8
14->11
15->1
15->5
16->4
16->11
16->13
17->0
17->2
17->15
Xristos97
Newbie
 
Δημοσιεύσεις: 13
Εγγραφή: 05 Ιαν 2016, 02:43

Re: Δομές Δεδομένων - Εργασία 3 [2017-18]

Δημοσίευσηαπό James » 19 Ιαν 2018, 19:02

Για το παραπάνω γράφημα ο αλγόριθμος ξεκινάει από τον 11 οπότε το queue είναι στην κατάσταση

11

Οι γείτονες του 11 είναι οι 5, 6, 9 οπότε το queue γίνεται

5, 6, 9

Οι γείτονες των κόμβων αυτών με τη σειρά είναι (0, 12, 13, 16), (3, 5, 8, 12) και (11, 14, 15, 16, 17). Οι κόμβοι είναι αριθμητικά ταξινομημένοι μέσα στην παρένθεση. Οπότε το queue γίνεται

0, 12, 13, 16, 3, 5, 8, 12, 11, 14, 15, 16, 17

Οι υπογραμμισμένοι κόμβοι δε θα μπουν στο queue γιατί είναι ήδη visited από παλιότερα.

Ο πρώτος κόμβος εντός του queue που έχει ακμή προς τον 4 είναι ο 13 επειδή ο 0 και ο 12 δεν έχουν, άρα through[4] = 13 και distances[4] = 3 (επειδή έχουμε κάνει 3 βήματα μέχρι τώρα).

Θα παρατηρήσεις ότι ο 16 που επιστρέφεις είναι λίγο πιο μετά στο queue από τον 13. Ο 13 έχει προτεραιότητα.

Είναι κατανοητό αυτό; Υπάρχει ακόμη απορία;
(Μόνο) James
Άβαταρ μέλους
James
Διαχειριστής
 
Δημοσιεύσεις: 1740
Εγγραφή: 08 Ιαν 2008, 22:29
Φοιτητής ΗΜΜΥ: Όχι

Re: Δομές Δεδομένων - Εργασία 3 [2017-18]

Δημοσίευσηαπό Xristos97 » 19 Ιαν 2018, 19:06

Ναι ευχαριστω!
Xristos97
Newbie
 
Δημοσιεύσεις: 13
Εγγραφή: 05 Ιαν 2016, 02:43

Re: Δομές Δεδομένων - Εργασία 3 [2017-18]

Δημοσίευσηαπό petrgrig » 19 Ιαν 2018, 20:38

Καλησπέρα σας,

Σχετικα με το import της εργασιας, στο εργαστηριο μας ειχατε αναφερει οτι δεν θα την κανουμε import απο το general αλλα απο το maven αν θυμαμαι καλα. Προσπαθησα αλλα δεν με αφηνει να την ολοκληρωσω.
petrgrig
Newbie
 
Δημοσιεύσεις: 5
Εγγραφή: 04 Δεκ 2015, 16:10

Re: Δομές Δεδομένων - Εργασία 3 [2017-18]

Δημοσίευσηαπό James » 19 Ιαν 2018, 21:14

petrgrig έγραψε:Καλησπέρα σας,

Σχετικα με το import της εργασιας, στο εργαστηριο μας ειχατε αναφερει οτι δεν θα την κανουμε import απο το general αλλα απο το maven αν θυμαμαι καλα. Προσπαθησα αλλα δεν με αφηνει να την ολοκληρωσω.

Όντως, για τα πρώτα αρχεία που σας είχαμε δώσει έπρεπε να γίνει η διαδικασία αυτή που λες, μέσω maven. Αυτό ήταν μια προσωρινή κατάσταση μέχρι να έβγαινε η επίσημη εκφώνηση της εργασίας. Τώρα μπορείτε να κάνετε import κανονικά, όπως στην πρώτη εργασία, σαν existing (general) project.
(Μόνο) James
Άβαταρ μέλους
James
Διαχειριστής
 
Δημοσιεύσεις: 1740
Εγγραφή: 08 Ιαν 2008, 22:29
Φοιτητής ΗΜΜΥ: Όχι

Re: Δομές Δεδομένων - Εργασία 3 [2017-18]

Δημοσίευσηαπό petrgrig » 19 Ιαν 2018, 21:40

Ωραια, θα ξανα προσπαθησω τοτε με general.

Σας ευχαριστω πολυ!
petrgrig
Newbie
 
Δημοσιεύσεις: 5
Εγγραφή: 04 Δεκ 2015, 16:10

Απλούστευση άσκησης DFS

Δημοσίευσηαπό James » 20 Ιαν 2018, 12:03

Η άσκηση του DFS για την τρίτη εργασία έχει υποστεί μικρές τροποποιήσεις.

Με βάση τις αλλαγές που έγιναν, ζητείται να υπολογίσετε και να αποθηκεύσετε σε λίστα τη σειρά με την οποία επισκέπτονται οι κόμβοι. Δεν ζητείται πλέον να υπολογίσετε τους πίνακες through και distances. Περισσότερες πληροφορίες θα βρείτε στην περιγραφή της άσκησης.

Δεν έχουν γίνει αλλαγές στις υπόλοιπες ασκήσεις.

Στα έγγραφα του μαθήματος στο eClass θα βρείτε νεότερη έκδοση των projects.

Προώθηση ανακοίνωσης από eClass
(Μόνο) James
Άβαταρ μέλους
James
Διαχειριστής
 
Δημοσιεύσεις: 1740
Εγγραφή: 08 Ιαν 2008, 22:29
Φοιτητής ΗΜΜΥ: Όχι

Παράδειγμα DFS

Δημοσίευσηαπό James » 20 Ιαν 2018, 12:06

Έστω το γράφημα

Κώδικας: Επιλογή όλων
0 -> 1
0 -> 2
1 -> 2
4 -> 1
2 -> 3
2 -> 5


με source τον κόμβο 0.

Η σειρά των κόμβων που επισκέπτονται με DFS είναι

0, 1, 2, 3, 5

και άρα η λίστα order θα πρέπει να περιέχει αυτούς τους κόμβους και με αυτή τη σειρά.
(Μόνο) James
Άβαταρ μέλους
James
Διαχειριστής
 
Δημοσιεύσεις: 1740
Εγγραφή: 08 Ιαν 2008, 22:29
Φοιτητής ΗΜΜΥ: Όχι

Re: Δομές Δεδομένων - Εργασία 3 [2017-18]

Δημοσίευσηαπό Xristos97 » 20 Ιαν 2018, 18:11

Δεν γινεται να παραδωσουμε τον dfs πριν γινει η αλλαγη ;
Xristos97
Newbie
 
Δημοσιεύσεις: 13
Εγγραφή: 05 Ιαν 2016, 02:43

Re: Δομές Δεδομένων - Εργασία 3 [2017-18]

Δημοσίευσηαπό James » 20 Ιαν 2018, 18:21

Xristos97 έγραψε:Δεν γινεται να παραδωσουμε τον dfs πριν γινει η αλλαγη ;

Όχι. Η αλλαγή αυτή ήταν απαραίτητη επειδή υπήρχε λάθος στα test cases. Ωστόσο αν έχεις ολοκληρώσει τον DFS με τις προηγούμενες προδιαγραφές, η αλλαγή που πρέπει να κάνεις είναι να προσθέσεις απλά μια γραμμή στο σημείο που βγαίνει ένας κόμβος από το stack.
(Μόνο) James
Άβαταρ μέλους
James
Διαχειριστής
 
Δημοσιεύσεις: 1740
Εγγραφή: 08 Ιαν 2008, 22:29
Φοιτητής ΗΜΜΥ: Όχι

Re: Δομές Δεδομένων - Εργασία 3 [2017-18]

Δημοσίευσηαπό tsakisx » 21 Ιαν 2018, 20:59

Που μπορούμε να δούμε τις μεθόδους που θα χρησιμοποιίσουμε π.χ g.getOutEdges(next) και πού ειναι η περιγραφή τους ;
tsakisx
Newbie
 
Δημοσιεύσεις: 16
Εγγραφή: 12 Ιαν 2016, 21:22

Re: Δομές Δεδομένων - Εργασία 3 [2017-18]

Δημοσίευσηαπό James » 21 Ιαν 2018, 22:01

tsakisx έγραψε:Που μπορούμε να δούμε τις μεθόδους που θα χρησιμοποιίσουμε π.χ g.getOutEdges(next) και πού ειναι η περιγραφή τους ;

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

size(): Επιστρέφει το πλήθος των κόμβων του γραφήματος.
getEdges(v): Επιστρέφει τους γείτονες κόμβους του v.

Στην περίπτωση των κατευθυνόμενων γραφημάτων η δεύτερη γίνεται getInEdges και getOutEdges ανάλογα με την κατεύθυνση των ακμών που θέλετε (κατά 99% θέλετε την getOutEdges).
(Μόνο) James
Άβαταρ μέλους
James
Διαχειριστής
 
Δημοσιεύσεις: 1740
Εγγραφή: 08 Ιαν 2008, 22:29
Φοιτητής ΗΜΜΥ: Όχι

Re: Δομές Δεδομένων - Εργασία 3 [2017-18]

Δημοσίευσηαπό Αναστάσης Τ. » 22 Ιαν 2018, 21:58

Η getEdges(v) επιστρεφει ενα πινακα με τους γειτονες του v ή κατι αλλο?
Αναστάσης Τ.
Newbie
 
Δημοσιεύσεις: 4
Εγγραφή: 05 Μάιος 2016, 11:40

Re: Δομές Δεδομένων - Εργασία 3 [2017-18]

Δημοσίευσηαπό James » 22 Ιαν 2018, 23:02

Αναστάσης Τ. έγραψε:Η getEdges(v) επιστρεφει ενα πινακα με τους γειτονες του v ή κατι αλλο?

Η getEdges(v) επιστρέφει ένα Set με τους γείτονες του v. Αυτό όμως δε σας ενδιαφέρει εσάς. Χρησιμοποιήστε τη δήλωση στα παραδείγματα για να τους διατρέξετε.

Κώδικας: Επιλογή όλων
for (int adj : g.getEdges(v)) {
  // do something with adj
}
(Μόνο) James
Άβαταρ μέλους
James
Διαχειριστής
 
Δημοσιεύσεις: 1740
Εγγραφή: 08 Ιαν 2008, 22:29
Φοιτητής ΗΜΜΥ: Όχι

ΠροηγούμενηΕπόμενο

Μέλη σε σύνδεση

Μέλη σε αυτή την Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 3 επισκέπτες