¿Qué problemas se pueden resolver o abordar más fácilmente utilizando gráficos y árboles?[cerrado]

Question

¿Cuáles son los problemas más comunes que se pueden resolver con ambas estructuras de datos?

Sería bueno para mí tener también recomendaciones sobre libros que:

• Implementar las estructuras.
• Implementar y explicar el razonamiento de los algoritmos que los utilizan.

Answer 1

Lo primero que pienso cuando leo esta pregunta es: ¿Qué tipo de cosas usan gráficos/árboles? y luego pienso hacia atrás en cómo podría usarlos.

Por ejemplo, tomemos dos usos comunes de un árbol:

• El DOM
• Sistemas de archivos

El DOM y el XML se parecen a estructuras de árbol.

También tiene sentido. Tiene sentido debido a cómo se deben organizar estos datos..Un sistema de archivos también.En un sistema UNIX hay un nodo raíz y se ramifica hacia abajo.Cuando montas un nuevo dispositivo, lo fijas al árbol.

También deberías preguntarte:¿Los datos caen en este tipo de estructura?Cree estructuras de datos que tengan sentido para el problema y el resto seguirá.

En cuanto a que sea más fácil, creo que es relativo.¿Eres bueno con funciones recursivas para recorrer un árbol/gráfico?¿Qué pasa si necesitas equilibrar el árbol?

Piensa en un programa que resuelve una sopa de letras.Puede representar todas las letras de la búsqueda de palabras en un gráfico y verificar los nodos circundantes para ver si esa cadena coincide con alguna de las palabras.¿Pero no podrías hacer lo mismo con una sola matriz?Todo lo que realmente necesita hacer es mover un índice para verificar las letras hacia la izquierda y hacia la derecha, y por el ancho para verificar las letras de arriba y de abajo.Resolver este problema con un gráfico no es difícil, pero puede generar mucho trabajo y dificultades adicionales si no te sientes cómodo usándolos; por supuesto, eso no debería desanimarte a hacerlo, especialmente si estás aprendiendo sobre a ellos.

Espero que te ayude a pensar en estas estructuras.En cuanto a una recomendación de libro, tendría que ir con Introducción a los algoritmos.

Answer 2

Diagramas de circuitos.

Compilación (gráficos acíclicos dirigidos)

Mapas.Muy compacto como gráficos.

Problemas de flujo de red.

Decisión árboles para sistemas expertos (sic)

Diagramas de espina de pescado para localización de fallas, mejora de procesos, análisis de seguridad.Para obtener puntos de bonificación, implemente su código de recuperación de errores como objetos que son el diagrama de espina de pescado.

Answer 3

Casi todos los problemas pueden reescribirse en términos de teoría de grafos.No estoy bromeando, mira cualquier libro sobre problemas completos de NP, hay algunos problemas bastante extravagantes que se convierten en teoría de grafos porque tenemos buenas herramientas para trabajar con gráficos...

Answer 4

El manual de diseño de algoritmos contiene algunos estudios de casos interesantes con uso creativo de gráficos.A pesar de su nombre, el libro es muy legible e incluso entretenido en ocasiones.

Answer 5

Hay un curso para este tipo de cosas en mi universidad: CSE 326.No pensé que el libro fuera demasiado útil, pero los proyectos son divertidos y te enseñan bastante sobre cómo implementar algunas de las estructuras más simples.

Por poner un ejemplo, uno de los problemas más habituales (por número de personas que lo utilizan) que se soluciona con los árboles es el de la introducción de texto en el móvil.Puede utilizar árboles, no necesariamente binarios, para representar el espacio de posibles palabras que pueden surgir de cualquier lista de números que un usuario ingresa muy rápidamente.

Answer 6

Algoritmos para Java:parte 5 de Robert Sedgewick trata sobre algoritmos gráficos y estructuras de datos.Este sería un buen primer libro para trabajar si desea implementar algunos algoritmos gráficos.

Answer 7

Los gráficos de escena para dibujar gráficos en juegos y aplicaciones multimedia utilizan mucho árboles y gráficos.Los nodos representan objetos a renderizar, transformaciones, controles, grupos, ...

Los gráficos de escena generalmente tienen múltiples capas y atributos, lo que significa que solo puede dibujar algún nodo de un gráfico (atributos) en un orden específico (capas).Dependiendo del tipo de gráfico de escena que tengas, puede tener dos estructuras paralelas:declaraciones e instanciación.Th

Answer 8

@DavidJoiner / todos:

FWIW:Una nueva versión del Manual de diseño de algoritmos saldrá en cualquier momento.

El curso completo para el que el profesor Skiena desarrolló este libro también está disponible en la web:

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

Answer 9

Los árboles se utilizan mucho más en lenguajes de programación funcionales debido a su naturaleza recursiva.

Además, los gráficos y los árboles son una buena forma de modelar muchos problemas de IA.

Answer 10

Los juegos suelen utilizar gráficos para facilitar la búsqueda de caminos en el mundo del juego.La representación gráfica del mundo puede tener algoritmos como la búsqueda en amplitud o A* para encontrar una ruta a través de él.

También suelen utilizar árboles para representar entidades dentro del mundo.Si tiene miles de entidades y necesita encontrar una en una posición determinada, iterar linealmente a través de una lista puede ser ineficiente, especialmente si necesita hacerlo con frecuencia.Por lo tanto, el área se puede subdividir en un árbol para permitir una búsqueda más rápida.Así como un espacio lineal se puede buscar eficientemente con una búsqueda binaria (y así dividirlo en un árbol binario), el espacio 2D se puede dividir en un árbol cuádruple y espacio 3D en un octree.