graphs data algorithms algorithm data-structures tree computer-science graph-theory

data - tree search algorithm



¿Qué problemas pueden resolverse o abordarse más fácilmente usando gráficos y árboles? (10)

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

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

  • Implementa las estructuras
  • Implementar y explicar el razonamiento de los algoritmos que los usan

Hay un curso para tales cosas en mi universidad: CSE 326 . No pensé que el libro fuera demasiado útil, pero los proyectos son divertidos y te enseñaron bastante sobre la implementación de algunas de las estructuras más simples.

En cuanto a los ejemplos, uno de los problemas más comunes (por número de personas que lo usan) que se resuelve con árboles es el de la entrada de texto del teléfono celular. Puede usar árboles, no necesariamente binarios, para representar el espacio de posibles palabras que pueden salir de una lista dada de números que un usuario introduce rápidamente.

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

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

Algoritmos para Java: la Parte 5 de Robert Sedgewick tiene que ver con algoritmos de gráficos y estructuras de datos. Este sería un buen primer libro para trabajar si quieres implementar algunos algoritmos de gráficos.

El Manual de diseño de algoritmos contiene algunos casos de estudio interesantes con uso creativo de gráficos. A pesar de su nombre, el libro es muy legible e incluso entretenido a veces.

Diagramas de circuito.

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

Mapas. Muy compacto como gráficos.

Problemas de flujo de red

Árboles de decisión para sistemas expertos (sic)

Diagramas de Fishbone para encontrar fallas, mejorar el proceso, 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 pez.

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 extraños que se convierten en teoría de grafos porque tenemos buenas herramientas para trabajar con gráficos ...

Los árboles se usan 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.

Los juegos a menudo usan 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 de amplitud o A * para encontrar una ruta a través de ella.

También suelen usar árboles para representar entidades en el mundo. Si tiene miles de entidades y necesita encontrar una en cierta posición, iterar linealmente en una lista puede ser ineficiente, especialmente si necesita hacerlo a menudo. Por lo tanto, el área se puede subdividir en un árbol para permitir que se busque más rápidamente. Del mismo modo que un espacio lineal puede buscarse eficientemente con una búsqueda binaria (y, por lo tanto, dividido en un árbol binario), el espacio 2D puede dividirse en un quadtree y espacio tridimensional en un octárbol .

Lo primero que pienso cuando leo esta pregunta es: ¿qué tipos de cosas usan gráficos / árboles? y luego pienso en cómo puedo usarlos.

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

  • El DOM
  • Sistemas de archivos

El DOM y XML, para el caso, se asemejan a estructuras de árbol.

Tiene sentido, también. 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 bifurca a continuación. Cuando montas un nuevo dispositivo, lo estás conectando al árbol.

También debería preguntarse: ¿los datos caen en este tipo de estructura? Crea estructuras de datos que tengan sentido para el problema y el resto seguirá.

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

Piense en un programa que resuelve un acertijo de búsqueda de palabras. Puede mapear 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 necesita hacer es mover un índice para revisar las letras a la izquierda y derecha, y por el ancho para verificar las letras arriba y abajo. Resolver este problema con un gráfico no es difícil, pero puede crear mucho trabajo extra y dificultad si no te sientes cómodo con su uso; por supuesto, eso no debería desanimarte, especialmente si estás aprendiendo sobre ellos.

Espero que eso te ayude a pensar sobre estas estructuras. En cuanto a una recomendación de libro, tendría que ir con Introducción a Algoritmos .