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

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

Δημοσίευσηαπό James » 18 Δεκ 2016, 14:30

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

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

Δημοσίευσηαπό Oblimo » 09 Ιαν 2017, 16:44

Για τον αλγόριθμο Dijkstra:
Ο κωδίκας που έχω γράψει, βγάζει failure σε 16 τεστ ενώ σε όλα τα άλλα δεν ύπαρχει πρόβλημα. π.χ στο τεστ 4
Κώδικας: Επιλογή όλων
java.lang.AssertionError: Invalid distance(s) (error margin of 1.0E-4) from start node 2 in graph:|V| = 5, |E| = 9, E = {
0->2=5.0,
0->4=3.0,
1->3=3.0,
2->3=1.0,
2->4=4.0,
3->1=2.0,
3->4=2.0,
4->1=1.0,
4->3=5.0,
}
 expected :<[Infinity, 3.0, 0.0, 1.0, 3.0]> but was:<[9999.0, 3.0, 0.0, 1.0, 3.0]>
   at org.junit.Assert.fail(Assert.java:88)
   at gr.duth.ee.euclid.datastructures.testing_framework.common.Helpers.forceFailEquals(Helpers.java:130)
   at gr.duth.ee.euclid.datastructures.testing_framework.common.Helpers.doubleArrayEquals(Helpers.java:89)
   at gr.duth.ee.euclid.datastructures.testing_framework.project_specific.TestCaseTester.test(TestCaseTester.java:45)
   at gr.duth.ee.euclid.datastructures.testing_framework.common.ParametrizedTest.test(ParametrizedTest.java:67)
   at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
   at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
   at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
   at java.lang.reflect.Method.invoke(Method.java:498)
   at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:47)
   at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
   at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:44)
   at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
   at org.junit.internal.runners.statements.FailOnTimeout$StatementThread.run(FailOnTimeout.java:74)




Από ότι φαίνεται ο πίνακας που επιστρέφω είναι σώστος. Που μπόρει να οφείλεται το failure;
Oblimo
Newbie
 
Δημοσιεύσεις: 3
Εγγραφή: 06 Ιαν 2015, 22:07

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

Δημοσίευσηαπό mpampis » 09 Ιαν 2017, 17:02

Το startNode του αλγοριθμου ποιο θα θεωρειται?
mpampis
Newbie
 
Δημοσιεύσεις: 6
Εγγραφή: 18 Ιαν 2015, 11:24

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

Δημοσίευσηαπό James » 09 Ιαν 2017, 17:32

Oblimo έγραψε:Για τον αλγόριθμο Dijkstra:
Ο κωδίκας που έχω γράψει, βγάζει failure σε 16 τεστ ενώ σε όλα τα άλλα δεν ύπαρχει πρόβλημα. π.χ στο τεστ 4
Κώδικας: Επιλογή όλων
java.lang.AssertionError: Invalid distance(s) (error margin of 1.0E-4) from start node 2 in graph:|V| = 5, |E| = 9, E = {
0->2=5.0,
0->4=3.0,
1->3=3.0,
2->3=1.0,
2->4=4.0,
3->1=2.0,
3->4=2.0,
4->1=1.0,
4->3=5.0,
}
 expected :<[Infinity, 3.0, 0.0, 1.0, 3.0]> but was:<[9999.0, 3.0, 0.0, 1.0, 3.0]>
   at org.junit.Assert.fail(Assert.java:88)
   at gr.duth.ee.euclid.datastructures.testing_framework.common.Helpers.forceFailEquals(Helpers.java:130)
   at gr.duth.ee.euclid.datastructures.testing_framework.common.Helpers.doubleArrayEquals(Helpers.java:89)
   at gr.duth.ee.euclid.datastructures.testing_framework.project_specific.TestCaseTester.test(TestCaseTester.java:45)
   at gr.duth.ee.euclid.datastructures.testing_framework.common.ParametrizedTest.test(ParametrizedTest.java:67)
   at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
   at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
   at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
   at java.lang.reflect.Method.invoke(Method.java:498)
   at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:47)
   at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
   at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:44)
   at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
   at org.junit.internal.runners.statements.FailOnTimeout$StatementThread.run(FailOnTimeout.java:74)




Από ότι φαίνεται ο πίνακας που επιστρέφω είναι σώστος. Που μπόρει να οφείλεται το failure;

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

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

Δημοσίευσηαπό James » 09 Ιαν 2017, 17:34

mpampis έγραψε:Το startNode του αλγοριθμου ποιο θα θεωρειται?

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

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

Δημοσίευσηαπό mpampis » 09 Ιαν 2017, 19:00

Δοκιμαστικα πως μπορουμε να τρεξουμε τον αλγοριθμο μας ?
mpampis
Newbie
 
Δημοσιεύσεις: 6
Εγγραφή: 18 Ιαν 2015, 11:24

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

Δημοσίευσηαπό Oblimo » 09 Ιαν 2017, 19:05

Ποιά είναι η τιμή του Infinity ?
Oblimo
Newbie
 
Δημοσιεύσεις: 3
Εγγραφή: 06 Ιαν 2015, 22:07

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

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

mpampis έγραψε:Δοκιμαστικα πως μπορουμε να τρεξουμε τον αλγοριθμο μας ?

Η διαδικασία εκτέλεσης των tests που δείξαμε στο φροντιστήριο αποτελεί έναν τρόπο να δοκιμάσετε την υλοποίησή σας. Αυτή η διαδικασία περιγράφεται στις σημειώσεις (scribes) της πρώτης εργασίας (Run As JUnit Test στο project-testing.jar). Δεν είμαι σίγουρος αν ρωτάς κάτι περισσότερο από αυτό.
(Μόνο) James
Άβαταρ μέλους
James
Διαχειριστής
 
Δημοσιεύσεις: 1740
Εγγραφή: 08 Ιαν 2008, 22:29
Φοιτητής ΗΜΜΥ: Όχι

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

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

Oblimo έγραψε:Ποιά είναι η τιμή του Infinity ?

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

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

Δημοσίευσηαπό mpampis » 12 Ιαν 2017, 18:43

Υπαρχει περιπτωση το graph-MST να μην ειναι μοναδικο ?
Τον αλγοριθμο Kruskal να χρησιμοποιουμε ?
mpampis
Newbie
 
Δημοσιεύσεις: 6
Εγγραφή: 18 Ιαν 2015, 11:24

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

Δημοσίευσηαπό James » 12 Ιαν 2017, 19:37

mpampis έγραψε:Υπαρχει περιπτωση το graph-MST να μην ειναι μοναδικο ?
Τον αλγοριθμο Kruskal να χρησιμοποιουμε ?

Τα γραφήματα που έχετε στη διάθεσή σας για τα test είναι έτσι φτιαγμένα που δεν υπάρχει περίπτωση να μην είναι μοναδική η απάντηση. Για κάθε γράφημα υπάρχει μόνο ένα MST. Μπορείτε να χρησιμοποιήσετε όποιον αλγόριθμο θέλετε από αυτούς που διδαχτήκατε για την υλοποίηση του MST (Prim, Kruskal, Reverse-Delete).
(Μόνο) James
Άβαταρ μέλους
James
Διαχειριστής
 
Δημοσιεύσεις: 1740
Εγγραφή: 08 Ιαν 2008, 22:29
Φοιτητής ΗΜΜΥ: Όχι

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

Δημοσίευσηαπό alliceinw0 » 13 Ιαν 2017, 17:38

Ποια είναι η σημασία του nodeThrough; Στο description toy Dijkstra γιατί το nodeThrough είναι 2 και για τον κόμβο 2 που είναι ο starting node και για τον κόμβο 3;
alliceinw0
Jr. Member
 
Δημοσιεύσεις: 54
Εγγραφή: 02 Σεπ 2014, 11:33

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

Δημοσίευσηαπό James » 13 Ιαν 2017, 23:43

alliceinw0 έγραψε:Ποια είναι η σημασία του nodeThrough; Στο description toy Dijkstra γιατί το nodeThrough είναι 2 και για τον κόμβο 2 που είναι ο starting node και για τον κόμβο 3;

Ο πίνακας nodeThrough (πρέπει να) έχει αποθηκευμένους τους κόμβους μέσω των οποίων επιτυχγάνονται οι προηγούμενες αποστάσεις.

Για τον κόμβο 3 το nodeThrough είναι 2 επειδή το συντομότερο μονοπάτι από τον 2 προς τον 3 είναι το 2 -> 3 (με βάρος 1) και ο προηγούμενος από τον 3, δηλαδή αυτός ο κόμβος μέσω του οποίου φτάνει κανείς στον 3, είναι ο 2. Επιπλέον, δες αυτή την απάντηση καθώς και το αρχείο Closeness.pdf που έχει παράδειγμα για το nodeThrough (που δείξαμε στο φροντιστήριο).

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

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

Δημοσίευσηαπό alliceinw0 » 14 Ιαν 2017, 04:31

Ευχαριστώ πολύ! Θα ήθελα να ρωτήσω και κάτι ακόμα... Μέσα στην κλάση Mst μπορούμε να υλοποιήσουμε και δικές μας επιπλέον συναρτήσεις;
alliceinw0
Jr. Member
 
Δημοσιεύσεις: 54
Εγγραφή: 02 Σεπ 2014, 11:33

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

Δημοσίευσηαπό georgev » 14 Ιαν 2017, 19:24

Η μέθοδος existsEdge(int i, int j) μας δίνει το αν η ακμή υπάρχει ή αν η ακμή υπάρχει και είναι και εξερχόμενη από τον κόμβο i;
georgev
Newbie
 
Δημοσιεύσεις: 9
Εγγραφή: 19 Ιαν 2015, 12:35

Επόμενο

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

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

cron