Java Trees Θελω να φτιαξω ενα DFS tree,(αλλα χωρις αναδρομη)

Spy · Post by **Spy** » Wed Nov 28, 2007 6:14 pm

Ρε παιδια επειδη μου εχει βγαλει τον ερωτα η Java με τα δεντρα της.... και επειδη με αναδρομη μου μπερδευεται η Java με = και τα new... μηπως ξερει κανενας πως να κανω με DFS δεντρο με 5 κλαδια σε καθε κομβο;

Με loop! Οχι αναδρομικα!

elsupreme · Post by **elsupreme** » Wed Nov 28, 2007 7:35 pm

Χρησιμοποίησε queue και bfs algorithm. Θα προσθέσεις 5 κόμβους στη ρίζα και μετά, επαναληπτικά, θα "ανοίγεις" κάθε παιδί, θα προσθέτεις τα 5 παιδιά του σε αυτό και θα προσθέτεις κάθε παιδί σε μια queue(ουρά) με τη σειρά. Αφού τελειώσεις με κάθε παιδί, θα αρχίσεις να βγάζεις από την ουρά τα παιδιά(των παιδιών) και θα επαναλάβεις το παραπάνω.
Άρα :
1.Προσθέτω ρίζα στην ουρά.
2.Βγάζω έναν κόμβο από την ουρά.
3.Για κάθε παιδί του κόμβου:
3α.Ο κόμβος δείχνει στο παιδί
3β.Το παιδί προστίθεται στο τέλος της ουράς.
4.Επιστρέφω στο 2, μέχρι να αδειάσει η ουρά.

Ελπίζω να το έπιασες. Κάνε και ένα search στην wikipedia για bfs algorithm και queue.

Spy · Post by **Spy** » Wed Nov 28, 2007 7:44 pm

Ok αρχηγε! Χρησιμοποιω ουρα για τα παιδια! Το προβλημα μου ηταν πως θα δημιουργησω το δεντρο με loop και οχι ανδραμικα! Παντως σε ευχαριστω

Post by **Zifnab** » Wed Nov 28, 2007 7:45 pm

Spy μήπως αυτό που ζητάς σχετίζεται με την τεχνητή νοημοσήνη εργασία 1?

Spy · Post by **Spy** » Wed Nov 28, 2007 9:14 pm

Zifnab wrote:Spy μήπως αυτό που ζητάς σχετίζεται με την τεχνητή νοημοσήνη εργασία 1?

Ναι, αλλα το λεω με πλαγιο λογο...
Αντι για πεντε κλαδια ειναι ολες οι δυνατες καταστασεις του παιχνιδιου και παει λεγωντας....
Τελος παντων... θα το κανω με αναδρομη.....

cactus · Post by **cactus** » Wed Nov 28, 2007 11:12 pm

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

Post by **The Punisher** » Thu Nov 29, 2007 12:15 am

χμ, με ουρά δε θα κάνεις BFS ?

cactus · Post by **cactus** » Thu Nov 29, 2007 12:56 am

Ναι.
Ο BFS δεν είναι αναδρομικός, αν δεν απατώμαι, όμως.
(αν το είπες για αυτό)

Post by **The Punisher** » Thu Nov 29, 2007 1:18 am

ο άνθρωπος ζήτησε DFS στον τίτλο του topic

cactus · Post by **cactus** » Thu Nov 29, 2007 1:20 am

The Punisher wrote:ο άνθρωπος ζήτησε DFS στον τίτλο του topic

Ναι, εγώ για DFS είπα...
εσυ είπες για BFS...

μπλεχτήκαμε ρε Χάρη

Spy · Post by **Spy** » Thu Nov 29, 2007 1:59 am

Οκ παιδια απλα ηθελα να δοκιμασω να το κανω με επαναληψη.
Ρε παιδια το StackOverFlow Exception, στην Java τι ειναι; Μου εχει σπασει τα νευρα αυτη η μαλ***α!
Και απο οτι διαβαζω στο forum της sun καποιοι αναφερουν οτι υπαρχει προβλημα με την γλωσσα!

Post by **The Punisher** » Thu Nov 29, 2007 2:24 am

Χρησιμοποίησε queue και bfs algorithm

εδώ αναφερόμουν

Το stackOverflow σημαίνει ότι ξεμένεις από μνήμη. Μπορείς να πειράξεις το μέγεθος της Stack που προσφέρει το jVM με κάποιο ειδικό flag (google it)

Spy · Post by **Spy** » Thu Nov 29, 2007 2:50 am

The Punisher wrote:
Χρησιμοποίησε queue και bfs algorithm
εδώ αναφερόμουν

Το stackOverflow σημαίνει ότι ξεμένεις από μνήμη. Μπορείς να πειράξεις το μέγεθος της Stack που προσφέρει το jVM με κάποιο ειδικό flag (google it)

Συμβαινει κατι πολυ παραξενο... και αναφερομαι στην εργασια της Τεχνιτης Νοημοσυνης (αν θελει καποιος mod να μεταφερει το thread ας το κανει).

Στην αρχη εκανα την εργασια με παραγωμενο δεντρο με αναδρομη... και εβλεπα οτι σε καθε κομβο που εκανα ενα νεο αντικειμενο της σκακιερας, new, μου πετουσε την παραπανω Exception! και συγκεκριμενα στο σημειο που διαγραφω τις παλιες κινησεις και περναω νεες... Η δομες ολες ειναι δικες μου!Καμια δεν ειναι ετοιμη

Post by **The Punisher** » Thu Nov 29, 2007 2:57 am

Ναι. Εγώ μιλάω για το Stack του jVM, που βάζει τα όρια για το πόσα αντικείμενα (σκακιέρες) θα έχεις ταυτόχρονα στη μνήμη σου

Spy · Post by **Spy** » Thu Nov 29, 2007 3:09 am

The Punisher wrote:Ναι. Εγώ μιλάω για το Stack του jVM, που βάζει τα όρια για το πόσα αντικείμενα (σκακιέρες) θα έχεις ταυτόχρονα στη μνήμη σου

Κατσε...περιμενε. Επειδη δεν ειμαι και τοσο μπροστα οσο εσυ, για πες μου πρωτα τι ειναι το Java virtual machine....
Απο το google δεν καταλαβα και πολλα

Spy · Post by **Spy** » Thu Nov 29, 2007 3:11 am

Για κοιτα εδω και πες μου αν λες αυτο

elsupreme · Post by **elsupreme** » Thu Nov 29, 2007 6:11 am

Ρε συ σόρρυ, δεν είδα το DFS στον τίτλο και σου έδωσα το άλλο...
Λοιπον, ας τα πάρουμε από την αρχή :
1.Θα βάζεις τα παιδιά σε στοίβα αντί σε ουρά.
2.ΔΕΝ είναι αναδρομή (ούτε ήταν το 1ο που σου πρότεινα αναδρομή), επανάληψη είναι !
3.Ο αλγόριθμός σου είναι:
Α.Βάζω ρίζα στην στοίβα.
Β.Βγάζω τον κόμβο από την στοίβα
Γ.Συνδέω το δέντρο με τον κόμβο.
Δ.Βάζω με την ανάποδη σειρά(προσοχή) τα παιδιά
του κόμβου στην στοίβα. (Εναλλακτικά, βάζω το 1ο παιδί μόνο στη στοίβα μου, αλλά όταν επιστρέφω εδώ βάζω το αμέσως 2ο κλπ.)
Ε.Πάω στο "Β" αν δεν έχει αδειάσει η στοίβα μου.
4.Η στοίβα που θα χρησιμοποιήσεις (αυτή που λέει ο Punisher) είναι έτοιμη από τη Java, μην φτιάχνεις πράγματα αν δεν είσαι σίγουρος...
Η τάξη είναι : java.util.Stack
Μπες στο java api (εκείνο το html εγχειρίδιο) και ψάξε να την βρεις και να δεις ποιες μεθόδους θες να κάνεις την δουλειά σου.
Ελπίζω αυτή την φορά να κατάλαβες.

Post by **HdkiLLeR** » Thu Nov 29, 2007 12:03 pm

Spy wrote:
The Punisher wrote:Ναι. Εγώ μιλάω για το Stack του jVM, που βάζει τα όρια για το πόσα αντικείμενα (σκακιέρες) θα έχεις ταυτόχρονα στη μνήμη σου
Κατσε...περιμενε. Επειδη δεν ειμαι και τοσο μπροστα οσο εσυ, για πες μου πρωτα τι ειναι το Java virtual machine....
Απο το google δεν καταλαβα και πολλα

Η Java δεν είναι native γλώσσα, κοινώς δεν σου παράγει κάποιο executable, αλλά σου παράγει κάποια μαγικά πραγματάκια που ονομάζονται .class files. Αυτά για να εκτελεστούν στο PC σου πρέπει κάποιος να κάνει την βρωμοδουλειά ώστε να πάρει τον κώδικα που είναι μέσα σε ένα .class file και να παράγει τις αντίστοιχες εντολές σε x86 assembly*. Δηλαδή πιο απλά, ο compiler της java παράγει κώδικα για μια υποθετική μηχανή που δεν υπάρχει (για το JVM - Java Virtual Machine), ενώ εσύ θέλεις κώδικα για μια υπαρκτή μηχανή, για το pc σου που φαντάζομαι τρέχει κάποιον x86 επεξεργαστή. Ε αυτό το κάνει η java virtual machine. Πολύ απλά γι' αυτό καλείς java <progname> μετά το compilation και δεν καλείς κατευθείαν το <progname> να τρέξει.

Τώρα σχετικά με το πρόβλημα σου, η αναδρομή είναι μνημοβόρα όσον αφορά το stack. Οι παράμετροι που περνάς στις αναδρομικές συναρτήσεις σου τοποθετούνται στην στοίβα και κάνοντας συνεχώς αναδρομή η στοίβα μεγαλώνει. Οπότε κάποια στιγμή δεν έχει άλλο χώρο και σου πετάει το exception αυτό. Μπορείς να δοκιμάσεις να αυξήσεις το μέγεθος της στοίβας της JVM με την εντολή -Xss100m. Δηλαδή όταν τρέχεις το πρόγραμμα σου ή το .jar file σου θα βάζεις σαν παράμετρο στην java το παραπάνω (εάν το πρόγραμμα σου λέγεται foo

):

Code: Select all

java -Xss100m foo

Επίσης μπορείς να αυξήσεις το 100m σε κάτι παραπάνω 200m, 300m κλπ κλπ. Είναι σε ΜΒ το μέγεθος της στοίβας.

*: To απλοποίησα εδώ λίγο αλλά σε γενικές γραμμές έτσι είναι.

Spy · Post by **Spy** » Thu Nov 29, 2007 12:42 pm

Τελεια η μεταφραση των παραπανω, HdkiLLeR.
Ευχαριστω για την βοηθεια, τελικα λυθηκε το προβλημα!

elsupreme · Post by **elsupreme** » Thu Nov 29, 2007 3:12 pm

Αυτό θα πει "κλέβω την παράσταση". Έμπαινε HdkiLLer

tsilochr · Post by **tsilochr** » Thu Nov 29, 2007 3:26 pm

elsupreme wrote:Αυτό θα πει "κλέβω την παράσταση". Έμπαινε HdkiLLer

την έχει κλέψει καιρό τώρα