Quels sont les bons exemples de problèmes que les graphiques peuvent résoudre mieux que l'alternative ?

Question

Après avoir lu le livre de Stevey Yegge Obtenez ce poste chez Google article, j'ai trouvé cette petite citation intéressante :

Chaque fois que quelqu'un vous pose un problème, pensez aux graphiques. Ils constituent le moyen le plus fondamental et le plus souple de représenter n'importe quel type de relation. Il y a donc une chance sur deux pour que tout problème de conception intéressant soit lié à un graphique. Assurez-vous que vous ne pouvez pas trouver de solution à l'aide de graphiques avant de passer à d'autres types de solutions. Ce conseil est important !

Quels sont des exemples de problèmes qui sont mieux représentés et/ou résolus par des structures de données/algorithmes de graphes ?

Un exemple auquel je peux penser : les unités de navigation (comme Garmin, TomTom), qui fournissent des indications routières de votre position actuelle à une autre, utilisent des graphiques et des algorithmes de cheminement avancés.

Quels sont les autres ?

Answer 1

Réseaux informatiques : Les graphes modélisent intuitivement les réseaux informatiques et l'internet. Les nœuds représentent souvent des systèmes finaux ou des routeurs, tandis que les arêtes représentent les connexions entre ces systèmes.

Structures de données : Toute structure de données qui utilise des pointeurs pour relier des données entre elles fait appel à un graphe quelconque. Cela inclut les structures arborescentes et les listes liées, qui sont utilisées en permanence.

Chemins et cartes : La recherche des chemins les plus courts ou les plus longs entre un endroit et une destination fait appel aux graphes. Il peut s'agir de tracer des chemins comme dans une application telle que Google Maps, ou de calculer les chemins que doivent emprunter les personnages IA dans un jeu vidéo, et bien d'autres problèmes similaires.

Satisfaction des contraintes : Un problème courant en IA est de trouver un objectif qui satisfasse une liste de contraintes. Par exemple, pour qu'une université établisse ses programmes de cours, elle doit s'assurer que certains cours n'entrent pas en conflit, qu'un professeur ne donne pas deux cours en même temps, que les conférences ont lieu pendant certaines plages horaires, etc. Les problèmes de satisfaction de contraintes de ce type sont souvent modélisés et résolus à l'aide de graphes.

Molécules : Les graphiques peuvent être utilisés pour modéliser les atomes et les molécules afin d'étudier, entre autres, leur interaction et leur structure.

Answer 2

Je suis très intéressé par la théorie des graphes et je l'ai utilisée pour résoudre de nombreux types de problèmes différents. Vous pouvez résoudre beaucoup de problèmes liés aux chemins, aux correspondances, aux structures en utilisant les graphes.

• Problèmes de cheminement ont beaucoup d'applications.

  C'était dans la question d'entretien d'une coupe de carrière. Disons que vous voulez trouver la somme la plus longue d'un sous tableau. Par exemple, [1, 2, 3, -1] a la plus longue somme de 6. Modélisez-la comme un Graphique acyclique dirigé ( DAG ), ajouter une source fictive, une destination fictive. Connectez chaque nœud avec une arête qui a un poids correspondant au nombre. Utilisez maintenant le Chemin le plus long algorithme dans le DAG pour résoudre ce problème.

  De même, les problèmes d'arbitrage dans le monde financier ou même les problèmes de géométrie consistant à trouver la plus longue structure de recouvrement sont des problèmes de chemin similaires.

• Parmi les plus évidentes, on peut citer problèmes de réseau (où votre réseau pourrait avoir des ordinateurs, des organigrammes, etc).
  Vous pouvez glaner beaucoup de informations structurelles comme

  • point qui divise le graphique en deux parties
  • quelle est la meilleure façon de les connecter
  • Quel est le meilleur moyen de se rendre d'un endroit à un autre ?
  • existe-t-il un moyen de rejoindre un endroit à partir d'un autre, etc.

• J'ai résolu beaucoup de gestion de projet des problèmes liés à l'utilisation de graphiques. Une séquence d'événements peut être imaginée comme un graphe dirigé (si vous n'avez pas de cycles, c'est encore mieux). Donc, maintenant vous pouvez

  • trier les événements en fonction de leur priorité
  • vous pouvez trouver l'événement qui est le plus crucial (qui libérerait beaucoup d'autres projets)
  • vous pouvez trouver la durée nécessaire pour résoudre l'ensemble du projet (problème du chemin), etc.

• Beaucoup de problèmes de correspondance peut être résolu par un graphique. Par exemple, si vous devez faire correspondre les processeurs à la charge de travail ou les travailleurs à leur emploi. Dans mon examen final, j'ai dû faire correspondre des personnes à des tables dans des restaurants. Cela suit le même principe (correspondance bipartite -> algorithmes de flux de réseau). C'est simple mais puissant.

• Un graphe spécial, un arbre a de nombreuses applications dans le monde de l'informatique. Par exemple, dans la syntaxe d'un langage de programmation, ou dans la structure d'indexation d'une base de données.

• Plus récemment, j'ai également utilisé des graphiques dans compilateur les problèmes d'optimisation. J'utilise le livre de Morgan, qui m'enseigne des techniques fascinantes.

La liste est vraiment longue, longue et longue. Les graphiques sont une belle abstraction mathématique pour relation . Vous pouvez vraiment faire des merveilles, si vous pouvez le modéliser correctement. Et comme le théorie des graphes a trouvé tant d'applications qu'il y a de nombreuses recherches actives dans ce domaine. Et grâce à ces nombreuses recherches, nous voyons encore plus d'applications, ce qui alimente de nouvelles recherches.

Si vous voulez vous initier à la théorie des graphes, procurez-vous un bon livre de mathématiques discrètes pour débutants ( Rosen me vient à l'esprit), et vous pouvez acheter des livres d'auteurs tels que Fould ou Même . CLRS possède également de bons algorithmes pour les graphes.

Answer 3

Votre code source est structuré en arbre, et un arbre est un type de graphe. Chaque fois que vous entendez des gens parler d'un AST (Abstract Syntax Tree), ils parlent d'un type de graphe.

Les pointeurs forment des structures de graphe. Tout ce qui parcourt les pointeurs effectue une sorte de manipulation de graphe.

Le web est un immense graphe dirigé. L'idée maîtresse de Google, qui lui a permis de dominer la recherche, est que la structure graphique du web est d'une importance comparable ou supérieure au contenu textuel des pages.

Les machines à états sont des graphes. Les machines à états sont utilisées dans les protocoles de réseau, les expressions régulières, les jeux et toutes sortes d'autres domaines.

Il est assez difficile de penser à quelque chose que vous faites qui n'implique pas une sorte de structure graphique.

Answer 4

Un exemple que la plupart des gens connaissent : les systèmes de construction. Make est l'exemple typique, mais presque tous les bons systèmes de compilation reposent sur un graphe acyclique dirigé. L'idée de base est que la direction modélise la dépendance entre une source et une cible, et que vous devez "parcourir" le graphe dans un certain ordre pour construire les choses correctement -> c'est un exemple de tri topologique.

Un autre exemple est le système de contrôle des sources : là encore, il est basé sur un DAG. Il est utilisé pour la fusion, par exemple pour trouver un parent commun.

Answer 5

De nombreux algorithmes d'optimisation des programmes utilisés par les compilateurs sont basés sur des graphes (par exemple, le graphe des appels, le contrôle de flux, de nombreuses analyses statiques).

De nombreux problèmes d'optimisation sont basés sur des graphes. Puisque de nombreux problèmes sont réductibles à la coloration des graphes et à des problèmes similaires, de nombreux autres problèmes sont également basés sur les graphes.

Je ne suis pas sûr d'être d'accord pour dire que les graphes sont la meilleure façon de représenter chaque relation et j'essaie certainement d'éviter ces approches du type "j'ai un clou, trouvons un marteau". Les graphes ont souvent de mauvaises représentations en mémoire et de nombreux algorithmes sont en fait plus efficaces (en pratique) lorsqu'ils sont implémentés avec des matrices, des bitsets et d'autres choses.