Quali problemi può essere risolto o affrontato più facilmente, utilizzando grafici e gli alberi?[chiuso]

Question

Quali sono i problemi più comuni che possono essere risolti con entrambe queste strutture di dati?

Sarebbe bello per me avere anche consigli su libri che:

• Implementare le strutture
• Implementare e spiegare il ragionamento degli algoritmi che li utilizzano

Answer 1

La prima cosa che ho pensato quando ho letto questa domanda è: quali tipi di cose utilizzare grafici/alberi? e poi penso all'indietro come ho potuto utilizzare.

Per esempio, prendere due usi comuni di un albero:

• DOM
• I sistemi di File

Il DOM, XML e per quella materia, simili a strutture ad albero.

Ha senso, troppo. Ha senso a causa di come questo tipo di dati deve essere organizzato.Un file di sistema, troppo.Su un sistema UNIX c'è un nodo radice, e la ramificazione in basso.Quando si monta un nuovo dispositivo, che si sta applicando su un albero.

Si dovrebbe, inoltre, essere se stessi chiedendo:i dati di cadere in questo tipo di struttura?Creare strutture di dati che senso il problema e il resto seguirà.

Per quanto sia più facile, penso che è relativo.Sei bravo con le funzioni ricorsive per attraversare un albero o di un grafico?Se hai bisogno di bilanciare l'albero?

Pensa ad un programma che risolve un puzzle di ricerca di parola.Si potrebbe mappa di tutte le lettere della parola ricerca in un grafico e controllare circostante nodi per vedere se la stringa è in corrispondenza di una qualsiasi delle parole.Ma non è che puoi solo fare lo stesso con un singolo array?Tutti si ha realmente bisogno di fare è spostare un indice per verificare le lettere a destra e a sinistra, e dalla larghezza di controllo al di sopra e al di sotto di lettere.La soluzione di questo problema con un grafico, non è difficile, ma può creare un sacco di lavoro extra e di difficoltà se non stai bene con il loro utilizzo, naturalmente, che non dovrebbe scoraggiare da fare, soprattutto se si sta imparando su di loro.

Spero che aiuta pensate di queste strutture.Come per un libro raccomandazione, mi piacerebbe andare con Introduzione agli Algoritmi.

Answer 2

Diagrammi di circuito.

La compilazione (Directed Acyclic grafici)

Mappe.Molto compatto sotto forma di grafici.

Di rete, problemi di flusso.

Decisione alberi per sistemi esperti (sic)

Diagrammi a lisca di pesce per la ricerca di guasti, il processo di miglioramento, analisi di sicurezza.Per i punti bonus, implementare il recupero di errore codice di oggetti che sono il diagramma a lisca di pesce.

Answer 3

Appena circa ogni problema può essere riscritta in termini di teoria dei grafi.Non sto scherzando, guardate qualsiasi libro sui problemi NP-completi, ci sono alcune belle wacky problemi che si trasformò in teoria dei grafi, perché abbiamo buoni strumenti per lavorare con i grafici...

Answer 4

L'Algoritmo Manuale Di Progettazione contiene alcuni interessanti casi di studio, con un uso creativo dei grafici.Nonostante il suo nome, il libro è molto leggibile e anche divertente, a volte.

Answer 5

C'è un corso per queste cose della mia università: CSE 326.Io non credo che il libro era troppo utile, ma i progetti sono divertenti e insegnare un bel po ' circa l'attuazione di alcune delle strutture più semplici.

Come per esempio, uno dei problemi più comuni (per numero di persone che la usano) che ha risolto con gli alberi è che del telefono delle cellule di immissione testo.È possibile utilizzare alberi, non necessariamente binario, per rappresentare lo spazio delle possibili parole che vengono fuori da qualsiasi elenco di numeri che un utente di pugni molto velocemente.

Answer 6

Algoritmi per Java:Parte 5 da Robert Sedgewick è tutto su algoritmi di grafico e datastructures.Questo sarebbe un buon primo libro di lavorare attraverso se si desidera implementare alcuni algoritmi di grafico.

Answer 7

Scena grafici per il disegno grafica in giochi e applicazioni multimediali ampio uso di alberi e grafi.I nodi rappresenta oggetti per il rendering, le trasformazioni, i controlli, gruppi, ...

Scena grafici di solito hanno diversi livelli e gli attributi che significa che è possibile disegnare solo alcuni dei nodi di un grafo (attributi) in un ordine specifico (livelli).A seconda del tipo di scena grafico che si hanno si possono avere due parallelo strutture:le dichiarazioni e la creazione di istanze.Th

Answer 8

@DavidJoiner / all:

FWIW:Una nuova versione del Progettazione Di Algoritmi Manuale è a causa di qualsiasi giorno ora.

L'intero corso che egli Prof Skiena sviluppato questo libro è disponibile anche sul web:

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

Answer 9

Gli alberi sono utilizzati molto di più in linguaggi di programmazione funzionale, a causa della loro natura ricorsiva.

Inoltre, i grafici e gli alberi sono un buon modo per modello molto AI problemi.

Answer 10

Spesso i giochi utilizzo di grafici per facilitare la ricerca di percorsi in tutto il mondo di gioco.Il grafico di rappresentazione del mondo può avere algoritmi come ricerca breadth-first o Un* al fine di trovare un percorso attraverso di esso.

Essi hanno inoltre spesso utilizzare gli alberi per rappresentare le entità all'interno del mondo.Se si dispone di migliaia di soggetti e la necessità di trovare uno in una determinata posizione e poi scorrere linearmente attraverso un elenco può essere inefficiente, soprattutto se avete bisogno di farlo spesso.Pertanto, l'area può essere suddivisa in un albero per consentire di essere cercati più rapidamente.Solo come uno spazio lineare può essere efficiente per la ricerca di un binario di ricerca (e quindi diviso in un albero binario), 2D spazio può essere suddiviso in un quadtree e 3D nello spazio in un octree.