data structures - keywords - ¿Cuáles son buenos ejemplos de problemas que los gráficos pueden resolver mejor que la alternativa?
meta tags google (19)
Algoritmos e implementaciones de perfil y / o benchmarking en código.
Después de leer el artículo de Getvey Job At Google de Stevey Yegge, encontré esta pequeña cita interesante:
Cuando alguien te da un problema, piensa en gráficos. Son la forma más fundamental y flexible de representar cualquier tipo de relación, por lo que se trata de una captura de 50-50 que cualquier problema de diseño interesante tiene un gráfico involucrado. Asegúrese de que no se le ocurra una forma de resolverlo mediante gráficos antes de pasar a otros tipos de soluciones. ¡Este consejo es importante!
¿Cuáles son algunos ejemplos de problemas que están mejor representados y / o resueltos por estructuras / algoritmos de datos de gráficos?
Un ejemplo en el que puedo pensar: unidades de navegación (como Garmin, TomTom), que suministran direcciones de carreteras desde su ubicación actual a otra, utilizan gráficos y algoritmos de rutas avanzadas.
¿Cuáles son algunos otros?
Analizando la serialisability transacciones en teoría de bases de datos.
Básicamente, casi todas las estructuras de datos comunes, como árboles, listas, colas, etc., pueden considerarse como un tipo de gráfico, algunas con diferentes tipos de limitaciones.
Según mis experiencias, he utilizado el gráfico de forma intensiva en problemas de flujo de red , que se utiliza en muchas áreas, como enrutamiento y optimización de redes de telecomunicaciones , asignación de carga de trabajo , correspondencia , optimización de la cadena de suministro y planificación del transporte público .
Otra área interesante es el modelado de redes sociales como se mencionó anteriormente.
Hay mucho más, como la optimización de circuitos integrados , etc.
Bueno, muchos algoritmos de optimización de programas que usan los compiladores se basan en gráficos (por ej., Calcular el gráfico de llamadas, el control de flujo, muchos análisis estáticos).
Muchos problemas de optimización se basan en gráficos. Dado que muchos problemas son reducibles a la coloración gráfica y problemas similares, muchos otros problemas también se basan en gráficos.
No estoy seguro de estar de acuerdo en que los gráficos son la mejor manera de representar a todas las relaciones y, desde luego, trato de evitar estos enfoques de "tengo un clavo, vamos a encontrar un martillo". Los gráficos a menudo tienen representaciones de memoria deficientes y muchos algoritmos son realmente más eficientes (en la práctica) cuando se implementan con matrices, conjuntos de bits y otras cosas.
En mi humilde opinión, la mayoría de los modelos de dominio que utilizamos en aplicaciones normales son, en algunos aspectos, gráficos. Si mira los diagramas UML, observará que con un gráfico dirigido y etiquetado, puede traducirlos fácilmente a un modelo de persistencia. Hay algunos ejemplos de eso en Neo4j
Aclamaciones
/ peter
Estoy muy interesado en la teoría de grafos y la he usado para resolver tantos tipos diferentes de problemas. Puede resolver una gran cantidad de problemas relacionados con la ruta, resolver problemas, estructurar problemas usando gráficos.
Los problemas de ruta tienen muchas aplicaciones.
Esto fue en la pregunta de la entrevista de una taza de carrera. Digamos que quiere encontrar la suma más larga de una matriz secundaria. Por ejemplo,
[1, 2, 3, -1]tiene la suma más larga de 6. Lo modela como un Gráfico Acíclico Dirigido ( DAG ), agrega una fuente ficticia, un destino ficticio. Conecte cada nodo con un borde que tenga un peso correspondiente al número. Ahora usa el algoritmo de ruta más larga en el DAG para resolver este problema.Del mismo modo, los problemas de arbitraje en el mundo financiero o incluso los problemas de geometría para encontrar la estructura superpuesta más larga son un problema de ruta similar.
Algunos obvios serían los problemas de red (donde su red podría tener computadoras, organigramas, etc.).
Puedes obtener mucha información estructural como- qué punto divide el gráfico en dos partes
- cuál es la mejor manera de conectarlos
- cuál es la mejor manera de llegar a un lugar a otro
- hay una manera de llegar a un lugar desde otro, etc.
He resuelto muchos problemas relacionados con la gestión de proyectos usando gráficos. Una secuencia de eventos se puede representar como un gráfico dirigido (si no tienes ciclos, eso es aún mejor). Entonces, ahora puedes
- ordenar los eventos según su prioridad
- puedes encontrar el evento que es el más crucial (es decir, liberaría muchos otros proyectos)
- puede encontrar la duración necesaria para resolver el proyecto total (problema de ruta), etc.
Muchos problemas de coincidencia pueden resolverse mediante un gráfico. Por ejemplo, si necesita unir los procesadores a la carga de trabajo o unir los trabajadores a sus trabajos. En mi examen final, tuve que unir personas a mesas en restaurantes. Sigue el mismo principio (correspondencia bipartita -> algoritmos de flujo de red). Es simple pero poderoso.
Un gráfico especial, un árbol , tiene numerosas aplicaciones en el mundo de la informática. Por ejemplo, en la sintaxis de un lenguaje de programación o en una estructura de indexación de base de datos.
Recientemente, también utilicé gráficos en problemas de optimización del compilador . Estoy usando Morgan''s Book, que me está enseñando técnicas fascinantes.
La lista realmente sigue y sigue y sigue. Los gráficos son una hermosa abstracción matemática para la relación . Realmente puedes hacer maravillas, si puedes modelarlo correctamente. Y dado que la teoría de grafos ha encontrado tantas aplicaciones, hay muchas investigaciones activas en el campo. Y debido a numerosas investigaciones, estamos viendo incluso más aplicaciones que están impulsando investigaciones posteriores.
Si quieres empezar con la teoría de grafos, consigue un buen libro de matemáticas discretas para principiantes (se me ocurre Rosen ), y puedes comprar libros de autores como Fould o Even . CLRS también tiene buenos algoritmos de gráficos.
LOC. Imagine una página de texto escaneada en ángulo, con algo de ruido en la imagen, donde debe encontrar el espacio entre las líneas de texto. Una forma es hacer un gráfico de píxeles y encontrar el camino más corto de un lado a otro de la página, donde la diferencia de brillo es la distancia entre los píxeles.
Este ejemplo proviene del Algorithm Design Manual , que tiene muchos otros ejemplos del mundo real de problemas de gráficos.
Las conexiones sociales entre personas hacen un ejemplo gráfico interesante. Intenté modelar estas conexiones a nivel de base de datos usando un RDMS tradicional, pero me resultó demasiado difícil. Terminé eligiendo una base de datos de gráficos y fue una gran elección porque hace que sea fácil seguir las conexiones (bordes) entre personas (nodos).
Los gráficos no son estructuras de datos. Son una representación matemática de las relaciones. Sí, puedes pensar y teorizar acerca de los problemas usando gráficos, y hay un gran cuerpo de teoría al respecto. Pero cuando se necesita implementar un algoritmo, se eligen las estructuras de datos para representar mejor el problema, no los gráficos. Hay muchas estructuras de datos que representan gráficos generales, y aún más para tipos especiales de gráficos.
En tu pregunta, mezclas estas dos cosas. La misma solución teórica puede ser en términos de gráfico, pero las soluciones prácticas pueden usar diferentes estructuras de datos para representar el gráfico.
Los gráficos son geniales para administrar dependencias.
Recientemente comencé a usar Castle Windsor Container, después de inspeccionar el Kernel encontré una propiedad GraphNodes. Castle Windsor usa un gráfico para representar las dependencias entre los objetos para que la inyección funcione correctamente. Mira este article .
También utilicé la teoría de grafos simple para desarrollar un marco de plugin, cada nodo de grafo representa un plugin, una vez que las dependencias han sido definidas puedo atravesar el gráfico para crear un orden de carga de plugins.
Estoy planeando cambiar el algoritmo para implementar el algoritmo de Dijkstra de modo que cada complemento se pondere con una versión específica, por lo tanto, un cambio simple solo cargará la última versión del complemento.
Yo con yo había descubierto esto antes. Me gusta esa frase: "Cuando alguien te da un problema, piensa en los gráficos". Definitivamente creo que es verdad.
Los siguientes están basados en la teoría de grafos:
- Árboles binarios y otros árboles tales como árboles Rojo-negros, árboles abiertos, etc.
- Listas enlazadas
- Cualquier cosa que se modele como una máquina de estado (GUI, pilas de red, CPU, etc.)
- Árboles de decisión (utilizados en IA y otras aplicaciones)
- Herencia de clase compleja
Para saber si dos moléculas pueden encajar. Cuando se desarrollan drogas, a menudo uno está interesado en ver si las moléculas de la droga pueden encajar en moléculas más grandes en el cuerpo. El problema para determinar si esto es posible es que las moléculas no son estáticas. Diferentes partes de la molécula pueden girar alrededor de sus uniones químicas para que una molécula pueda cambiar en muchas formas diferentes.
Se puede decir que cada forma representa un punto en un espacio que consiste en formas. Resolver este problema implica encontrar un camino a través de este espacio. Puede hacerlo creando un mapa de ruta a través del espacio, que es esencialmente un gráfico que consiste en formas legales y que indica en qué forma se puede convertir una forma. Al usar un algoritmo de búsqueda de gráficos A * a través de esta hoja de ruta, puede encontrar una solución.
Bueno, eso era mucho parloteo que quizás no era muy comprensible o claro. Pero mi punto era que los gráficos aparecen en todo tipo de problemas.
Podrías echar un vistazo a algunos de los ejemplos en la wiki de Neo4j,
y los proyectos en los que se usa Neo4j (los conocidos)
De lo contrario, los Algoritmos de Recomendación son un buen uso para los Gráficos, ver por ejemplo PageRank, y otras cosas en
Puede utilizar gráficos en cualquier lugar donde pueda definir los objetos del dominio problemático en nodos y la solución como flujo de control y / o datos entre los nodos.
Teniendo en cuenta el hecho de que los árboles están efectivamente conectados, los gráficos acíclicos, hay incluso más áreas donde puedes usar la teoría de los gráficos.
Su código fuente está estructurado por árbol, y un árbol es un tipo de gráfico. Cada vez que escuche a personas hablar sobre un AST (Árbol de sintaxis abstracta), están hablando de un tipo de gráfico.
Los punteros forman estructuras gráficas. Cualquier cosa que pase punteros está haciendo algún tipo de manipulación de gráficos.
La web es un enorme gráfico dirigido. La idea clave de Google, que los llevó a dominar en la búsqueda, es que la estructura gráfica de la web es de importancia comparable o mayor que el contenido textual de las páginas.
Las máquinas de estado son gráficos. Las máquinas de estado se utilizan en protocolos de red, expresiones regulares, juegos y todo tipo de otros campos.
Es bastante difícil pensar en cualquier cosa que hagas que no implique algún tipo de estructura gráfica.
Todo lo que se puede modelar como una clave externa en una base de datos relacional es esencialmente un borde y nodos en un gráfico.
Quizás eso te ayude a pensar en ejemplos, ya que la mayoría de las cosas se modelan fácilmente en un RDBMS.
Un ejemplo popular es la recolección de basura.
El recolector comienza con un conjunto de referencias, luego atraviesa todos los objetos a los que hace referencia, luego todos los objetos a los que se hace referencia, y así sucesivamente. Todo lo que encuentra se agrega a un gráfico de objetos alcanzables. Todos los demás objetos son inalcanzables y recopilados.
Un ejemplo que la mayoría de la gente conoce: sistemas de construcción. Make es el ejemplo típico, pero casi cualquier buen sistema de compilación se basa en un gráfico acíclico dirigido. La idea básica es que la dirección modele la dependencia entre una fuente y un objetivo, y usted debe "caminar" la gráfica en un cierto orden para construir las cosas correctamente -> este es un ejemplo de ordenamiento topológico.
Otro ejemplo es el sistema de control de fuente: nuevamente basado en un DAG. Se usa para combinar, por ejemplo, para encontrar padres comunes.
Redes de computadoras: el modelo de gráficos modela de manera intuitiva redes de computadoras e Internet. A menudo, los nodos representan sistemas finales o enrutadores, mientras que los bordes representan conexiones entre estos sistemas.
Estructuras de datos: cualquier estructura de datos que utiliza punteros para vincular datos está haciendo uso de un gráfico de algún tipo. Esto incluye estructuras de árbol y listas vinculadas que se usan todo el tiempo.
Pathing and Maps: Tratar de encontrar las rutas más cortas o más largas desde una ubicación a un destino hace uso de gráficos. Esto puede incluir rutas como las que se ven en una aplicación como Google Maps, o calcular rutas para que los personajes de AI tomen un videojuego, y muchos otros problemas similares.
Satisfacción por Restricción: Un problema común en AI es encontrar algún objetivo que satisfaga una lista de restricciones. Por ejemplo, para que una Universidad establezca sus horarios de cursos, necesita asegurarse de que ciertos cursos no entren en conflicto, que un profesor no esté impartiendo dos cursos al mismo tiempo, que las clases se dicten durante ciertas franjas horarias, y así sucesivamente. . Los problemas de satisfacción de restricción como este a menudo se modelan y resuelven usando gráficos.
Moléculas: los gráficos se pueden usar para modelar átomos y moléculas para estudiar su interacción y estructura, entre otras cosas.