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

votos
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
Publicado el 06/08/2008 a las 01:56
fuente por usuario
En otros idiomas...                            


10 respuestas

votos
16

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.
texto alternativo

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 .

Respondida el 06/08/2008 a las 02:28
fuente por usuario

votos
4

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.

Respondida el 28/08/2008 a las 04:29
fuente por usuario

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

Respondida el 09/03/2009 a las 14:54
fuente por usuario

votos
2

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.

Respondida el 12/08/2008 a las 21:59
fuente por usuario

votos
1

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

Asimismo, a menudo utilizan los árboles para representar entidades del mundo. Si usted tiene miles de entidades y la necesidad de encontrar uno en una posición determinada y luego iterar linealmente a través de una lista puede ser ineficiente, especialmente si tiene que hacerlo a menudo. Por lo tanto, la zona se puede subdividir en un árbol para que pueda ser buscado con mayor rapidez. Del mismo modo que un espacio lineal puede ser eficiente buscó con una búsqueda binaria (y por lo tanto dividido en un árbol binario), el espacio 2D se puede dividir en un árbol cuaternario y en el espacio 3D en un octree .

Respondida el 01/07/2010 a las 12:11
fuente por usuario

votos
1

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.

Respondida el 09/03/2009 a las 14:25
fuente por usuario

votos
1

@DavidJoiner / all:

FWIW: una nueva versión del Algorithm Design Manual saldrá a la venta en cualquier momento.

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

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

Respondida el 27/08/2008 a las 00:56
fuente por usuario

votos
1

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

Respondida el 08/08/2008 a las 16:58
fuente por usuario

votos
1

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.

Respondida el 08/08/2008 a las 16:46
fuente por usuario

votos
1

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.

Respondida el 06/08/2008 a las 02:18
fuente por usuario

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