Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Δημοσίευσηαπό pefraimi » 14 Δεκ 2019, 08:08

Εδώ μπορείτε να υποβάλετε ερωτήσεις, απορίες ή παρατηρήσεις σχετικές με την 3η εργασία.

Σημείωση: Η προγραμματισμένη Εργασία 2 - FacilityGame δεν θα γίνει φέτος. Επομένως
η εργασία αυτή (GraphSearch) είναι ουσιαστικά η δεύτερη εργασία για το τρέχον
ακαδημαϊκό έτος. Απλά για τεχνικούς λόγους κρατήσαμε το όνομα Εργασία 3.
pefraimi
Sr. Member
 
Δημοσιεύσεις: 333
Εγγραφή: 01 Νοέμ 2008, 14:59

Re: Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Δημοσίευσηαπό Fokikara » 27 Δεκ 2019, 14:47

Καλησπέρα και Χρόνια Πολλά,

Στο αρχείο Tools.java εμφανίζει στην εντολή: " import javax.xml.bind.DatatypeConverter; "
το εξής error: "The import javax.xml.bind cannot be resolved" .

Επηρεάζει αυτό καθόλου την εκτέλεση του προγράμματος ?
Fokikara
Newbie
 
Δημοσιεύσεις: 1
Εγγραφή: 17 Ιαν 2015, 16:31

Re: Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Δημοσίευσηαπό pefraimi » 28 Δεκ 2019, 16:38

Στην κλάση Tool υλοποιούνται κάποιες βοηθητικές συναρτήσεις.
Μπορείς αν θέλεις να αφαιρέσεις (ή να βάλεις σε σχόλια) τις
παρακάτω γραμμές

Κώδικας: Επιλογή όλων
import javax.xml.bind.DatatypeConverter;


και

Κώδικας: Επιλογή όλων
public static String SHAsum(byte[] convertme) throws NoSuchAlgorithmException{
  MessageDigest md = MessageDigest.getInstance("SHA-1");

  return DatatypeConverter.printHexBinary(md.digest(convertme));
}


και να προσθέσεις αυτή την υλοποίηση

Κώδικας: Επιλογή όλων
public static String SHAsum(byte[] convertme) throws NoSuchAlgorithmException{
  MessageDigest md = MessageDigest.getInstance("SHA-1");
  return byteArray2Hex(md.digest(convertme));
}


που δεν χρησιμοποιεί την κλάση "javax.xml.bind.DatatypeConverter".
Αυτή η υλοποίηση είναι από εδώ:
https://stackoverflow.com/questions/1515489/compute-sha-1-of-byte-array
pefraimi
Sr. Member
 
Δημοσιεύσεις: 333
Εγγραφή: 01 Νοέμ 2008, 14:59

Re: Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Δημοσίευσηαπό pefraimi » 31 Δεκ 2019, 18:50

... Δεν μπορώ να βρω στην σελίδα υποβολής της 2ης εργασίας την φόρμα υποβολής της 2ης εργασίας. Δεν είναι κάτω από τα αποδεικτικά όπως λένε οι οδηγίες στο e class. ...


Όταν φτάσεις στη διεύθυνση https://euclid.ee.duth.gr:5000/
θα πρέπει στο μενού που υπάρχει στο πάνω μέρος της σελίδας να επιλέξεις
"Other Pages" -> "Graph Search Submission" και να δώσεις τα στοιχεία σου.
Συνημμένα
Υποβολή Εργασίας GraphSearch - Screenshot.jpg
pefraimi
Sr. Member
 
Δημοσιεύσεις: 333
Εγγραφή: 01 Νοέμ 2008, 14:59

Re: Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Δημοσίευσηαπό pefraimi » 02 Ιαν 2020, 07:37

Στην εργασία τι ακριβώς ζητάει οταν λέει bfs sequence και στο bfs tree;

Έτσι όπως το καταλαβάινω στο bfs_sequence βαζω σε σειρα/ακολουθια τους κόμβους τους οποίους ελέγχω, κάνω print αυτούς τους κόμβους και με το χέρι βγάζω σωστά αποτελέσματα ενώ το test μου βγάζει error στο position 2.


Το bfs sequence είναι η σειρά των κόμβων που επισκέπτεται ο αλγόριθμος bfs
και το bfs tree είναι το δέντρο (ουσιαστικά οι ακμες του δέντρου) που δημιουργεί
ο αλγόριθμος bfs. Τα αποτελέσματα απλά καταχωρούνται στο αντικείμενο "Result"
και αοο εκεί υποβάλλονται και ελέγχονται αυτομάτως.
Όπως τα συζητήσαμε στο μάθημα.

Επισυνάπτω παραδείγματα εκτέλεσης του GraphSearch μαζί με τις σωστές απαντήσεις.

Εκτέλεση με παραμέτρους:
GraphSearchClient 0.98
Execution Mode: 0
Number of Nodes: 10
Seed: 123
Επισυνάπτεται και μια απεικόνιση ολόκληρου του γράφου.

Εκτέλεση με παραμέτρους:
GraphSearchClient 0.98
Execution Mode: 0
Number of Nodes: 10
Seed: 345
Συνημμένα
GraphSearch-0-10-345.txt
(2.03 KiB) Έχει μεταφορτωθεί 361 φορές
GraphSearch-0-10-123 graph.jpg
GraphSearch-0-10-123 graph.jpg (49.52 KiB) 7036 προβολές
GraphSearch-0-10-123.txt
(2.01 KiB) Έχει μεταφορτωθεί 400 φορές
pefraimi
Sr. Member
 
Δημοσιεύσεις: 333
Εγγραφή: 01 Νοέμ 2008, 14:59

Πρόβλημα bfsNodeSequence

Δημοσίευσηαπό TheWasteOfLife » 02 Ιαν 2020, 22:30

Καλησπέρα και Καλή Χρονιά.

Έχω ένα πρόβλημα που αφορά το bfsNodeSequence. Ας πούμε για το
παράδειγμα 0-10-123 παίρνω:

Κώδικας: Επιλογή όλων
7881330081594434580
356680113560091765
4330916032953772575
2088700237454711300
7869681676196028646
6730862846203828765
1785698371378776366
4846513878386249461
3960368575220640710
6058682250869941328


Που μου φαίνεται μεν σωστό αλλά δεν συμβαδίζει με το txt. Νομίζω το πρόβλημα
βρίσκεται στο γεγονός ότι η xgraph.getNeighborsOf(firstNode) επιστρέφει:

Κώδικας: Επιλογή όλων
356680113560091765
4330916032953772575
2088700237454711300


Σε αντίθεση με το txt:

Κώδικας: Επιλογή όλων
356680113560091765
2088700237454711300
4330916032953772575


Υπάρχει κάποιος συγκεκριμένος τρόπος με τον οποίο η xgraph.getNeighborsOf() εμφανίζει τους γειτονικούς
κόμβους?

Ευχαριστώ εκ των προτέρων
TheWasteOfLife
Newbie
 
Δημοσιεύσεις: 2
Εγγραφή: 07 Δεκ 2016, 16:18

Re: Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Δημοσίευσηαπό pefraimi » 02 Ιαν 2020, 23:40

Η xgraph.getNeighborsOf() επιστρέφει τους γείτονες με αυθαίρετη σειρά. Θα πρέπει να τους ταξινομήσετε σε αύξουσα ή φθίνουσα σειρά, ανάλογα με τον αλγόριθμο.
pefraimi
Sr. Member
 
Δημοσιεύσεις: 333
Εγγραφή: 01 Νοέμ 2008, 14:59

Re: Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Δημοσίευσηαπό ΑΡΑΠΑΚΗΣ ΠΑΝΑΓΙΩΤΗΣ » 04 Ιαν 2020, 22:15

Καλησπέρα
input:Execution Mode: 0
Number of Nodes: 10
Seed: 123
Με print της εντολής res.getDfsTree παίρνω output:

DGraph. Nodes: 356680113560091765, 1785698371378776366, 2088700237454711300, 3960368575220640710, 4330916032953772575, 4846513878386249461, 6058682250869941328, 6730862846203828765, 7869681676196028646, 7881330081594434580,

DEdges: 356680113560091765, 7881330081594434580, 1785698371378776366, 4330916032953772575, 2088700237454711300, 3960368575220640710, 3960368575220640710, 6058682250869941328, 4330916032953772575, 356680113560091765, 4846513878386249461, 1785698371378776366, 6058682250869941328, 4846513878386249461, 6730862846203828765, 1785698371378776366, 7869681676196028646, 4330916032953772575,
Tα Edges(Νode IDs ανά δύο) αντιστοιχούν στα edges που ανεβάσατε στο παράδειγμα(txt) όμως κατά την εκτέλεση παίρνω :
Bonus: NO
Additional Information from GraphSearch server:
[dfsTree: #Edges missing: 9. #Edges wrong: 9. ]
Δεν είναι σωστά αυτά τα edges ;
ΑΡΑΠΑΚΗΣ ΠΑΝΑΓΙΩΤΗΣ
Newbie
 
Δημοσιεύσεις: 2
Εγγραφή: 10 Ιαν 2019, 21:04

Re: Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Δημοσίευσηαπό pefraimi » 05 Ιαν 2020, 11:39

Υπενθυμίζω ότι:
Σε κάθε ακμή (ζεύγος κορυφών) η σειρά των κόμβων είναι σημαντική.

Κάνε έναν έλεγχο στις ακμές που καταχωρείς, για το εάν έχουν τη σωστή κατεύθυνση
(η πρώτη κορυφή είναι η αφετηρία της ακμής και η δεύτερη ο τερματισμός).
pefraimi
Sr. Member
 
Δημοσιεύσεις: 333
Εγγραφή: 01 Νοέμ 2008, 14:59

Re: Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Δημοσίευσηαπό ΑΡΑΠΑΚΗΣ ΠΑΝΑΓΙΩΤΗΣ » 05 Ιαν 2020, 13:23

pefraimi έγραψε:Υπενθυμίζω ότι:
Σε κάθε ακμή (ζεύγος κορυφών) η σειρά των κόμβων είναι σημαντική.

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

Ανεβάζω μέρος του κώδικα.
<Μην ανεβάζετε κώδικα της λύσης στο forum>


Εδώ το τχτ που ανεβάσατε:
//dfsTree:
Οι παρακάτω κατευθυνόμενες ακμές.
Σε κάθε ακμή (ζεύγος κορυφών) η σειρά των κόμβων είναι σημαντική.
Η σειρά των ακμών δεν παίζει ρόλο.
(356680113560091765, 7881330081594434580)
(1785698371378776366, 4330916032953772575)
(2088700237454711300, 3960368575220640710)
(3960368575220640710, 6058682250869941328)
(4330916032953772575, 356680113560091765)
(4846513878386249461, 1785698371378776366)
(6058682250869941328, 4846513878386249461)
(6730862846203828765, 1785698371378776366)
(7869681676196028646, 4330916032953772575)//
ΑΡΑΠΑΚΗΣ ΠΑΝΑΓΙΩΤΗΣ
Newbie
 
Δημοσιεύσεις: 2
Εγγραφή: 10 Ιαν 2019, 21:04

Re: Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Δημοσίευσηαπό Σωκράτης » 05 Ιαν 2020, 19:23

Δοκιμάζω τον κώδικά μου στο παραδειγματικό πρόβλημα με 10 κόμβους και seed 123 και κατι δεν βγαζει καθολου νοημα. Αφού ο γράφος έχει 16 ακμές, γιατί στο δέντρο bfs αναγράφονται μόνο 9 ζευγάρια; Επίσης, αφού ο γράφος δεν είναι κατευθυνόμενος σύμφωνα με την εκφώνηση της άσκησης, γιατί έχει σημασία η σειρά των κόμβων μέσα στα ζεύγη που σχηματίζουν τις ακμές; Τέλος, τι είδους είναι η σχέση μεταξύ κόμβου αρχής και κόμβου τέλους μίας ακμής; Είναι η θέση τους στο BfsNodeSequence, είναι το μέγεθός τους σαν αριθμοί long ή κάτι άλλο;
Σωκράτης
Newbie
 
Δημοσιεύσεις: 1
Εγγραφή: 05 Ιαν 2020, 19:15

Re: Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Δημοσίευσηαπό pefraimi » 05 Ιαν 2020, 20:15

Ανεβάζω μέρος του κώδικα.

Μην ανεβάζετε κώδικα της λύσης στο forum.

Δοκιμάζω τον κώδικά μου στο παραδειγματικό πρόβλημα με 10 κόμβους και seed 123 και κατι δεν βγαζει καθολου νοημα. Αφού ο γράφος έχει 16 ακμές, γιατί στο δέντρο bfs αναγράφονται μόνο 9 ζευγάρια;

Το bfsTree δεν περιλαμβάνει όλες τις ακμές του γράφου αλλά μόνο όσες απαιτούνται
για τη δημιουργία του δέντρου.
Γενικά ένα δέντρο με n κόμβους έχει υποχρεωτικά n-1 ακμές.
Τα έχουμε πει στο μάθημα αυτά. Δες τις σημειώσεις και ειδικά την Ενότητα 3.2 του βιβλίου.

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

Στν περίπτωση αυτή οι ακμές των bfsTree/dfsTree δεν είναι οι ακμές του αρχικού γράφου
αλλά οι κινήσεις των αλγορίθμων bfs/dfs για να μετακινηθούν σε κάθε κορυφή.
Εδώ η διάταξη των κόμβων είναι σημαντική και προκύπτει από την εκτέλεση των
αλγορίθμων.

Τέλος, τι είδους είναι η σχέση μεταξύ κόμβου αρχής και κόμβου τέλους μίας ακμής; Είναι η θέση τους στο BfsNodeSequence, είναι το μέγεθός τους σαν αριθμοί long ή κάτι άλλο;

Σε κάθε ακμή των bfsTree/dfsTree, ο κόμβος αρχή είναι ο κόμβος του αρχικού γράφου
από τον οποίο ο αλγόριθμος επισκέφθηκε τον κόμβο τερματισμό της ακμής.
pefraimi
Sr. Member
 
Δημοσιεύσεις: 333
Εγγραφή: 01 Νοέμ 2008, 14:59

Re: Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Δημοσίευσηαπό The Core » 06 Ιαν 2020, 20:27

Καλησπερα,
Για seed 123 και 10 nodes,
Oταν κανω πριντ το bfsTree, βγαζει:
DGraph. Nodes: 356680113560091765, 1785698371378776366, 2088700237454711300, 3960368575220640710, 4330916032953772575, 4846513878386249461, 6058682250869941328, 6730862846203828765, 7869681676196028646, 7881330081594434580,

DEdges: 356680113560091765, 6730862846203828765,
356680113560091765, 7869681676196028646,
2088700237454711300, 3960368575220640710,
3960368575220640710, 6058682250869941328,
4330916032953772575, 1785698371378776366,
4330916032953772575, 4846513878386249461,
7881330081594434580, 356680113560091765,
7881330081594434580, 2088700237454711300,
7881330081594434580, 4330916032953772575,

Οπως βλεπετε το bfs Tree μου βγαινει ακριβως οπως στο λυμενο παραδειγμα.
Αλλα το προγραμμα λεει:

XGraphServer response: Execution failed!

Failure description: GraphSearch: Incorrect answer to compulsory question(s) (abcdefg:111000000000000)
Additional Information from GraphSearch server:
[bfsTree: , dfs sequence: The sequence is shorter than expected: 10, 0, dfsTree: #Nodes missing: 10. #Edges missing: 9. ]

(Τα dfs χτυπανε λαθος γιατι δεν τα εχω γραψει ακομα)

Αρα το προγραμμα μου βγαζει οτι το bfsTree ειναι λαθος χωρίς να δωσει λογο, ενω ξερω οτι το tree εχει την μορφη που εχει υποδειχθει.
Τι συμβαινει λαθος εδω;
The Core
Newbie
 
Δημοσιεύσεις: 2
Εγγραφή: 30 Ιαν 2019, 13:50

Re: Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Δημοσίευσηαπό pefraimi » 06 Ιαν 2020, 23:45

Δοκίμασε τώρα να το τρέξεις ξανά.
pefraimi
Sr. Member
 
Δημοσιεύσεις: 333
Εγγραφή: 01 Νοέμ 2008, 14:59

Re: Αλγόριθμοι & Δομές Δεδομένων - Εργασία 3 [2019-20]

Δημοσίευσηαπό The Core » 08 Ιαν 2020, 20:17

Καλησπερα
Για seed 123 nodes 10
Οταν τρεχω τον DFS αλγοριθμο μου για να βρω την σειρα των nodes παιρνω αυτο:

[7881330081594434580, 4330916032953772575, 7869681676196028646, 356680113560091765, 6730862846203828765, 1785698371378776366, 4846513878386249461, 6058682250869941328, 3960368575220640710, 2088700237454711300]

Γιατι καθε φορα που εμφανιζονται τα neighbors τα κανω sort και επιλεγω το μεγαλυτερο, οπως επρεπε στο bfs node sequence.

Αλλα συμφωνα με την λυμενη ασκηση, τα nodes δεν φαινεται να επιλεγονται με αυτον τον τροπο. Πως ξερω ποιο neighbor να ακολουθησω;
The Core
Newbie
 
Δημοσιεύσεις: 2
Εγγραφή: 30 Ιαν 2019, 13:50

Επόμενο

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

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