Que problemas podem ser resolvidos ou resolvidos mais facilmente usando gráficos e árvores?[fechado]

Question

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

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

• Implementar as estruturas
• Implementar e explicar o raciocínio dos algoritmos que os utilizam

Answer 1

A primeira coisa que penso quando leio esta pergunta é: que tipos de coisas usam gráficos/árvores? e então penso em como poderia usá-los.

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

• O DOM
• Sistemas de arquivos

O DOM e o XML se assemelham a estruturas de árvore.

Também faz sentido. Faz sentido devido à forma como esses dados precisam ser organizados.Um sistema de arquivos também.Em um sistema UNIX há um nó raiz e uma ramificação abaixo.Ao montar um novo dispositivo, você o fixa na árvore.

Você também deve estar se perguntando:os dados se enquadram nesse tipo de estrutura?Crie estruturas de dados que façam sentido para o problema e o resto virá.

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

Pense em um programa que resolve um quebra-cabeça de busca de palavras.Você pode mapear todas as letras da pesquisa de palavras em um gráfico e verificar os nós circundantes para ver se essa string corresponde a alguma das palavras.Mas você não poderia fazer o mesmo com um único array?Tudo o que você realmente precisa fazer é mover um índice para verificar as letras à esquerda e à direita, e pela largura para verificar as letras acima e abaixo.Resolver este problema com um gráfico não é difícil, mas pode criar muito trabalho extra e dificuldade se você não se sentir confortável em usá-los - é claro que isso não deve desencorajá-lo de fazê-lo, especialmente se você estiver aprendendo sobre eles.

Espero que isso ajude você a pensar sobre essas estruturas.Quanto à recomendação de um livro, eu teria que seguir Introdução aos Algoritmos.

Answer 2

Diagramas de circuito.

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

Mapas.Muito compacto como gráficos.

Problemas de fluxo de rede.

Decisão árvores para sistemas especialistas (sic)

Diagramas de espinha de peixe para detecção de falhas, melhoria de processos e análise de segurança.Para ganhar pontos extras, implemente seu código de recuperação de erros como objetos que são o diagrama de espinha de peixe.

Answer 3

Quase todos os problemas podem ser reescritos em termos de teoria dos grafos.Não estou brincando, olhe qualquer livro sobre problemas completos de NP, existem alguns problemas bem malucos que se transformam em teoria dos grafos porque temos boas ferramentas para trabalhar com gráficos...

Answer 4

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

Answer 5

Há um curso para essas coisas na minha universidade: CSE 326.Não achei o livro muito útil, mas os projetos são divertidos e ensinam bastante sobre a implementação de algumas das estruturas mais simples.

A título de exemplo, um dos problemas mais comuns (por número de pessoas que o utilizam) que se resolve com as árvores é o da digitação de texto no celular.Você pode usar árvores, não necessariamente binárias, para representar o espaço de palavras possíveis que podem surgir de qualquer lista de números que um usuário digita muito rapidamente.

Answer 6

Algoritmos para Java:Parte 5 de Robert Sedgewick é sobre algoritmos gráficos e estruturas de dados.Este seria um bom primeiro livro para trabalhar se você quiser implementar alguns algoritmos gráficos.

Answer 7

Os gráficos de cena para desenhar gráficos em jogos e aplicativos multimídia usam intensamente árvores e gráficos.Os nós representam objetos a serem renderizados, transformações, controles, grupos, ...

Os gráficos de cena geralmente possuem múltiplas camadas e atributos, o que significa que você pode desenhar apenas alguns nós de um gráfico (atributos) em uma ordem especificada (camadas).Dependendo do tipo de gráfico de cena que você possui, ele pode ter duas estruturas paralelas:declarações e instanciação.º

Answer 8

@DavidJoiner / todos:

FWIW:Uma nova versão do Manual de Design de Algoritmo está previsto para sair a qualquer momento.

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

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

Answer 9

As árvores são muito mais usadas em linguagens de programação funcionais devido à sua natureza recursiva.

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

Answer 10

Os jogos costumam usar gráficos para facilitar a localização de caminhos no mundo do jogo.A representação gráfica do mundo pode ter algoritmos como pesquisa em largura ou A* para encontrar uma rota através dele.

Eles também costumam usar árvores para representar entidades no mundo.Se você tem milhares de entidades e precisa encontrar uma em uma determinada posição, a iteração linear em uma lista pode ser ineficiente, especialmente se você precisar fazer isso com frequência.Portanto a área pode ser subdividida em uma árvore para permitir uma busca mais rápida.Assim como um espaço linear pode ser pesquisado eficientemente com uma pesquisa binária (e assim dividido em uma árvore binária), o espaço 2D pode ser dividido em uma árvore quádrupla e espaço 3D em um octree.