Que problemas podem ser resolvidos ou resolvidos mais facilmente, usando gráficos e árvores?

votos
10

Quais são os problemas mais comuns que podem ser resolvidos com estas duas estruturas de dados?

Seria bom para mim ter também recomendações sobre livros que:

  • Implementar as estruturas
  • Implementar e explicar o raciocínio dos algoritmos que os utilizam
Publicado 06/08/2008 em 01:56
fonte usuário
Em outras línguas...                            


10 respostas

votos
16

A primeira coisa que penso quando li esta pergunta é: que tipos de coisas usar gráficos / árvores? e então eu acho que para trás para como eu poderia usá-los.

Por exemplo, ter dois usos comuns de uma árvore:

  • o DOM
  • Os sistemas de arquivos

O DOM e XML para que o assunto, se assemelham a estruturas de árvore.
texto alternativo

Faz sentido, também. Faz sentido porque da forma como esses dados precisam ser organizados . Um sistema de arquivos também. Em um sistema UNIX há um nó raiz e ramificação abaixo. Quando você monta um novo dispositivo, você está anexando-o para a árvore.

Você também deve estar se perguntando: será que os dados se enquadram neste tipo de estrutura? Criar estruturas de dados que fazem sentido para o problema eo resto vai seguir.

Quanto a ser mais fácil, eu acho que isso é relativo. Você é bom com funções recursivas para percorrer uma árvore / gráfico? E se você precisa equilibrar a árvore?

Pense em um programa que resolve um enigma da busca da palavra. Você pode mapear todas as letras da busca da palavra em um gráfico e verificar em torno nós para ver se essa seqüência está combinando qualquer uma das palavras. Mas você não pode apenas fazer o mesmo com com uma única matriz? Tudo que você realmente precisa fazer é mover um índice para verificar cartas para a esquerda e direita, e pela largura de verificar acima e abaixo letras. Resolver este problema com um gráfico não é difícil, mas pode criar um monte de trabalho extra e dificuldade se você não está confortável com o uso deles - é claro que não deve desanimá-lo de fazê-lo, especialmente se você está aprendendo sobre eles.

Espero que ajude você pensa sobre essas estruturas. Quanto a uma recomendação do livro, eu teria que ir com Introdução aos Algoritmos .

Respondeu 06/08/2008 em 02:28
fonte usuário

votos
4

diagramas de circuitos.

Compilação (gráficos Directed acíclicos)

Mapas. Muito compacto como gráficos.

problemas de fluxo de rede.

Decisão árvores para sistemas especialistas (sic)

Diagramas espinha de peixe para encontrar falhas, improvment processo, análise de segurança. Para pontos de bônus, implementar o seu código de recuperação de erros como objetos que são o diagrama espinha de peixe.

Respondeu 28/08/2008 em 04:29
fonte usuário

votos
3

Apenas sobre cada problema pode ser re-escrita em termos da teoria dos grafos. Eu não estou brincando, olhar para qualquer livro sobre NP problemas completos, há alguns problemas muito malucos que se transformou em teoria dos grafos, porque temos boas ferramentas para trabalhar com gráficos ...

Respondeu 09/03/2009 em 14:54
fonte usuário

votos
2

O Manual Algoritmo projeto contém alguns estudos de caso interessantes com uso criativo de gráficos. Apesar do nome, o livro é muito legível e até mesmo divertido, às vezes.

Respondeu 12/08/2008 em 21:59
fonte usuário

votos
1

Jogos costumam usar gráficos para facilitar a encontrar caminhos através do mundo do jogo. A representação gráfica do mundo podem ter algoritmos como busca em largura primeiro ou A *, a fim de encontrar uma rota através dele.

Eles também costumam usar árvores para representar entidades do mundo. Se você tem milhares de entidades e precisa encontrar um em uma determinada posição, então a iteração linearmente através de uma lista pode ser ineficiente, especialmente se você precisa fazê-lo muitas vezes. Portanto, a área pode ser subdividida em uma árvore para permitir que ele seja procurado mais rapidamente. Assim como um espaço linear podem ser eficientemente procurou com uma pesquisa binária (e, portanto, dividido em uma árvore binária), espaço 2D pode ser dividido em uma quadtree e espaço 3D em uma octree .

Respondeu 01/07/2010 em 12:11
fonte usuário

votos
1

Árvores são usados ​​muito mais em linguagens de programação funcional devido à sua natureza recursiva.

Além disso, gráficos e árvores são uma boa maneira de modelar uma série de problemas de IA.

Respondeu 09/03/2009 em 14:25
fonte usuário

votos
1

@DavidJoiner / all:

FWIW: Uma nova versão do Manual de Algoritmo projeto será lançado a qualquer momento.

Todo o curso que ele Prof Skiena desenvolveu este livro para também está disponível na web:

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

Respondeu 27/08/2008 em 00:56
fonte usuário

votos
1

grafos de cena para desenhar gráficos em jogos e aplicativos de multimídia usar fortemente árvores e gráficos. Nodes representa objetos a serem prestados, transformações, controles, grupos, ...

grafos de cena geralmente têm múltiplas camadas e atributos que significa que você pode desenhar apenas alguns nó de um gráfico (atributos) em uma ordem especificada (camadas). Dependendo do tipo de grafo de cena que você tem que pode ter duas estruturas parralel: declarações e instanciação. º

Respondeu 08/08/2008 em 16:58
fonte usuário

votos
1

Algoritmos para Java: Parte 5 por Robert Sedgewick é tudo sobre algoritmos de grafos e datastructures. Este seria um bom primeiro livro para trabalhar através se você quiser implementar alguns algoritmos de grafos.

Respondeu 08/08/2008 em 16:46
fonte usuário

votos
1

Há um campo para essas coisas na minha universidade: CSE 326 . Eu não acho que o livro era muito útil, mas os projetos são divertidos e ensinar-lhe um bocado sobre a implementação de algumas das estruturas mais simples.

Como exemplos, um dos problemas mais comuns (por número de pessoas usando-o) que é resolvido com árvores é a de entrada de texto de telefone celular. Você pode usar árvores, não necessariamente binário, para representar o espaço de palavras possíveis que pode sair de qualquer lista dada de números que um usuário socos em muito rapidamente.

Respondeu 06/08/2008 em 02:18
fonte usuário

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