Τι προβλήματα μπορούν να λυθούν ή να αντιμετωπιστούν πιο εύκολα, χρησιμοποιώντας γραφικές παραστάσεις και τα δέντρα;

ψήφοι
10

Ποια είναι τα πιο κοινά προβλήματα που μπορούν να λυθούν με τις δύο αυτές δομές δεδομένων;

Θα ήταν καλό για μένα να έχουν, επίσης, προτάσεις για βιβλία που:

  • Εφαρμογή των δομών
  • Εφαρμογή και να εξηγήσει το σκεπτικό των αλγορίθμων που τα χρησιμοποιούν
Δημοσιεύθηκε 06/08/2008 στις 01:56
πηγή χρήστη
Σε άλλες γλώσσες...                            


10 απαντήσεις

ψήφοι
16

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

Για παράδειγμα, πάρτε δύο κοινές χρήσεις ενός δέντρου:

  • το DOM
  • συστήματα αρχείων

Το DOM, και XML για το θέμα αυτό, μοιάζουν με τις δομές δέντρο.
alt κείμενο

Είναι λογικό, πάρα πολύ. Είναι λογικό, διότι για το πώς πρέπει να οργανωθούν αυτά τα δεδομένα . Ένα σύστημα αρχείων, πάρα πολύ. Σε ένα σύστημα UNIX υπάρχει ένας κόμβος ρίζα, και διακλαδώσεις κάτω από. Όταν τοποθετείτε μια νέα συσκευή, είστε το επισυνάπτοντας πάνω στο δέντρο.

Θα πρέπει επίσης να αναρωτιέστε: δεν τα στοιχεία που εμπίπτουν σε αυτό το είδος της δομής; Δημιουργία δομών δεδομένων που έχουν νόημα για το πρόβλημα και θα ακολουθήσουν οι υπόλοιποι.

Σε ό, τι είναι πιο εύκολο, νομίζω thats που συγγενή. Είστε καλοί με αναδρομικές συναρτήσεις για να διασχίσει ένα δέντρο / γράφημα; Τι γίνεται αν χρειαστεί να εξισορροπήσει το δέντρο;

Σκεφτείτε για ένα πρόγραμμα που λύνει ένα παζλ αναζήτηση λέξης. Θα μπορούσατε να χαρτογραφήσει όλα τα γράμματα της λέξης αναζήτησης σε ένα γράφημα και να ελέγξετε γύρω κόμβους για να δούμε αν αυτή η συμβολοσειρά που ταιριάζουν οποιαδήποτε από τις λέξεις. Αλλά δεν θα μπορούσε να κάνει ακριβώς το ίδιο με μια ενιαία σειρά; Το μόνο που πραγματικά χρειάζεται να κάνετε είναι να μετακινήσετε ένα δείκτη για να ελέγξετε επιστολές προς τα αριστερά και δεξιά, και από το πλάτος για να ελέγξετε πάνω και κάτω γράμματα. Η επίλυση αυτού του προβλήματος με ένα γράφημα δεν είναι δύσκολο, αλλά μπορεί να δημιουργήσει πολλά επιπλέον εργασία και δυσκολία αν δεν είστε εξοικειωμένοι με τη χρήση τους - φυσικά που δεν πρέπει να σας αποθαρρύνει από το να κάνει αυτό, ειδικά αν μαθαίνετε για τους.

Ελπίζω ότι σας βοηθά να σκεφτούμε αυτές τις δομές. Όσο για σύσταση βιβλίο, θα πρέπει να πάει με Εισαγωγή στην Αλγόριθμοι .

Απαντήθηκε 06/08/2008 στις 02:28
πηγή χρήστη

ψήφοι
4

διαγράμματα κυκλωμάτων.

Συγκέντρωση (κατευθυνόμενος άκυκλος γράφος)

Χάρτες. Πολύ συμπαγής και γραφήματα.

προβλήματα ροής δικτύου.

Απόφαση δέντρα για τα έμπειρα συστήματα (sic)

Ψαροκόκαλο διαγράμματα για την εύρεση βλαβών, διαδικασία improvment, ανάλυση ασφάλειας. Για τα σημεία μπόνους, να εφαρμόσουν τον κωδικό ανάκτησης σφάλματος σας αντικείμενα που είναι το διάγραμμα ψαροκόκαλο.

Απαντήθηκε 28/08/2008 στις 04:29
πηγή χρήστη

ψήφοι
3

Ακριβώς για κάθε πρόβλημα που μπορεί να ξαναγραφεί από την άποψη της θεωρίας γραφημάτων. Δεν αστειεύομαι, κοιτάξτε σε οποιοδήποτε βιβλίο για την πλήρη προβλήματα NP, υπάρχουν κάποια αρκετά εκκεντρικός προβλήματα που πάρετε μετατραπεί σε θεωρία γραφημάτων, επειδή έχουμε καλά εργαλεία για την εργασία με γραφήματα ...

Απαντήθηκε 09/03/2009 στις 14:54
πηγή χρήστη

ψήφοι
2

Το εγχειρίδιο Αλγόριθμος Σχεδιασμού περιέχει κάποιες ενδιαφέρουσες μελέτες περιπτώσεων με τη δημιουργική χρήση των γραφημάτων. Παρά το όνομά του, το βιβλίο είναι πολύ ευανάγνωστη ακόμα και διασκεδαστικό κατά καιρούς.

Απαντήθηκε 12/08/2008 στις 21:59
πηγή χρήστη

ψήφοι
1

Παιχνίδια συχνά χρησιμοποιούν διαγράμματα για να διευκολύνει την εύρεση διαδρομών σε όλο τον κόσμο του παιχνιδιού. Η γραφική απεικόνιση του κόσμου μπορεί να έχει αλγόριθμους, όπως το πλάτος, αναζήτηση πρώτα ή A * για να βρείτε μια διαδρομή σε αυτό.

Επίσης, χρησιμοποιούν συχνά τα δέντρα για να αντιπροσωπεύσει τις οντότητες μέσα στον κόσμο. Αν έχετε χιλιάδες φορείς και πρέπει να βρείτε ένα σε μια συγκεκριμένη θέση, στη συνέχεια, την επανάληψη γραμμικά σε μια λίστα μπορεί να είναι αναποτελεσματική, ειδικά αν πρέπει να το κάνουμε συχνά. Συνεπώς, η περιοχή μπορεί να υποδιαιρεθεί σε ένα δέντρο, ώστε να μπορέσει να γίνει η αναζήτηση πιο γρήγορα. Ακριβώς όπως ένας γραμμικός χώρος μπορεί να αναζητηθεί αποτελεσματικά με μια δυαδική αναζήτηση (και, επομένως, διαιρούμενο σε ένα δυαδικό δέντρο), 2D χώρο μπορεί να χωριστεί σε ένα τετραδικό δένδρο και 3D χώρο σε ένα Octree .

Απαντήθηκε 01/07/2010 στις 12:11
πηγή χρήστη

ψήφοι
1

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

Επίσης, γραφικές παραστάσεις και τα δέντρα είναι ένας καλός τρόπος για να μοντελοποιήσει πολλά προβλήματα AI.

Απαντήθηκε 09/03/2009 στις 14:25
πηγή χρήστη

ψήφοι
1

@DavidJoiner / όλα:

FWIW: Μια νέα έκδοση του εγχειριδίου Αλγόριθμος σχεδιασμού αναμένεται να κυκλοφορήσει οποιαδήποτε ημέρα τώρα.

Ολόκληρη η πορεία που ο ίδιος ο καθηγητής Skiena ανέπτυξε αυτό το βιβλίο είναι επίσης διαθέσιμη στο διαδίκτυο:

http://www.cs.sunysb.edu/~algorith/video-lectures/2007-1.html

Απαντήθηκε 27/08/2008 στις 00:56
πηγή χρήστη

ψήφοι
1

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

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

Απαντήθηκε 08/08/2008 στις 16:58
πηγή χρήστη

ψήφοι
1

Αλγόριθμοι για Java: Μέρος 5 από τον Robert Sedgewick έχει να κάνει με αλγορίθμους γραφημάτων και datastructures. Αυτό θα ήταν ένα καλό πρώτο βιβλίο και να εργαστούν με, αν θέλετε να εφαρμόσουν κάποια αλγόριθμοι γράφημα.

Απαντήθηκε 08/08/2008 στις 16:46
πηγή χρήστη

ψήφοι
1

Υπάρχει μια σειρά μαθημάτων για τέτοια πράγματα στο πανεπιστήμιο μου: ΧΑΚ 326 . Δεν πίστευα ότι το βιβλίο ήταν πάρα πολύ χρήσιμο, αλλά τα έργα είναι διασκέδαση και να σας διδάξει μια δίκαιη λίγο για την εφαρμογή μερικές από τις απλούστερες δομές.

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

Απαντήθηκε 06/08/2008 στις 02:18
πηγή χρήστη

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more