algorithm - Quels problèmes peuvent être résolus ou abordés plus facilement à l'aide de graphiques et d'arbres?

Translate

Quels sont les problèmes les plus courants qui peuvent être résolus avec ces deux structures de données?

Ce serait bien pour moi d'avoir également des recommandations sur les livres qui:

  • Mettre en œuvre les structures
  • Mettre en œuvre et expliquer le raisonnement des algorithmes qui les utilisent
This question and all comments follow the "Attribution Required."

Toutes les réponses

Translate

La première chose à laquelle je pense en lisant cette question est:Quels types de choses utilisent des graphiques / arbres?puis je repense à la façon dont je pourrais les utiliser.

Par exemple, prenons deux utilisations courantes d'un arbre:

  • Le DOM
  • Systèmes de fichiers

Le DOM, et XML d'ailleurs, ressemblent à des arborescences.
alt text

Cela a du sens aussi.Cela a du sens en raison de la façon dont ces données doivent être organisées. Un système de fichiers aussi. Sur un système UNIX, il y a un nœud racine et une branche en dessous. Lorsque vous montez un nouvel appareil, vous l'attachez à l'arborescence.

Vous devriez également vous demander: les données entrent-elles dans ce type de structure? Créez des structures de données adaptées au problème et le reste suivra.

Pour ce qui est d'être plus facile, je pense que c'est relatif. Êtes-vous bon avec les fonctions récursives pour parcourir un arbre / graphe? Et si vous avez besoin d'équilibrer l'arbre?

Pensez à un programme qui résout un casse-tête de recherche de mots. Vous pouvez mapper toutes les lettres de la recherche de mot dans un graphique et vérifier les nœuds environnants pour voir si cette chaîne correspond à l'un des mots. Mais ne pourriez-vous pas faire la même chose avec un seul tableau? Tout ce que vous devez vraiment faire est de déplacer un index pour vérifier les lettres vers la gauche et la droite, et de la largeur pour vérifier les lettres au-dessus et en dessous. Résoudre ce problème avec un graphique n'est pas difficile, mais cela peut créer beaucoup de travail supplémentaire et de difficultés si vous n'êtes pas à l'aise avec leur utilisation - bien sûr, cela ne devrait pas vous décourager de le faire, surtout si vous en apprenez leur.

J'espère que cela vous aide à réfléchir à ces structures. Quant à une recommandation de livre, je devrais aller avecIntroduction aux algorithmes.

La source
Translate

Schémas de circuit.

Compilation (graphes acycliques dirigés)

Plans. Très compact sous forme de graphiques.

Problèmes de flux réseau.

Décisiondes arbrespour systèmes experts (sic)

Diagrammes en arête de poisson pour la recherche de pannes, l'amélioration des processus, l'analyse de la sécurité. Pour les points bonus, implémentez votre code de récupération d'erreur sous forme d'objets quisontle diagramme en arête de poisson.

La source
Translate

Presque tous les problèmes peuvent être réécrits en termes de théorie des graphes. Je ne plaisante pas, regardez n'importe quel livre sur les problèmes complets de NP, il y a des problèmes assez farfelus qui se transforment en théorie des graphes parce que nous avons de bons outils pour travailler avec des graphiques ...

La source
Translate

Le manuel de conception d'algorithmescontient des études de cas intéressantes avec une utilisation créative des graphiques. Malgré son nom, le livre est très lisible et parfois même divertissant.

La source
Translate

Il y a un cours pour de telles choses dans mon université:CSE 326. Je ne pense pas que le livre était trop utile, mais les projets sont amusants et vous apprennent un peu comment mettre en œuvre certaines des structures les plus simples.

En ce qui concerne les exemples, l'un des problèmes les plus courants (en nombre de personnes qui l'utilisent) résolu avec les arbres est celui de la saisie de texte sur un téléphone portable. Vous pouvez utiliser des arbres, pas nécessairement binaires, pour représenter l'espace des mots possibles qui peuvent sortir d'une liste donnée de nombres qu'un utilisateur poinçonne très rapidement.

La source
King Lee
Translate

Algorithmes pour Java: partie 5par Robert Sedgewick est tout sur les algorithmes de graphes et les structures de données. Ce serait un bon premier livre à parcourir si vous souhaitez implémenter des algorithmes graphiques.

La source
Translate

Les graphiques de scène pour dessiner des graphiques dans les jeux et les applications multimédias utilisent fortement des arbres et des graphiques. Les nœuds représentent des objets à rendre, des transformations, des champs, des groupes, ...

Les graphiques de scène ont généralement plusieurs couches et attributs, ce qui signifie que vous ne pouvez dessiner que certains nœuds d'un graphique (attributs) dans un ordre spécifié (couches). Selon le type de graphe de scène que vous avez, il peut avoir deux structures parallèles: les déclarations et l'instanciation. Th

La source
Translate

@DavidJoiner / tous:

FWIW: Une nouvelle version duManuel de conception d'algorithmesest attendu n'importe quel jour maintenant.

L'ensemble du cours pour lequel le professeur Skiena a développé ce livre est également disponible sur le Web:

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

La source
Translate

Les arbres sont beaucoup plus utilisés dans les langages de programmation fonctionnels en raison de leur nature récursive.

De plus, les graphiques et les arbres sont un bon moyen de modéliser de nombreux problèmes d'IA.

La source
Translate

Les jeux utilisent souvent des graphiques pour faciliter la recherche de chemins dans le monde du jeu. La représentation graphique du monde peut avoir des algorithmes tels que la recherche en largeur d'abord ou A * afin de trouver une route à travers elle.

Ils utilisent également souvent des arbres pour représenter des entités dans le monde. Si vous avez des milliers d'entités et que vous devez en trouver une à une certaine position, itérer linéairement dans une liste peut être inefficace, surtout si vous devez le faire souvent. Par conséquent, la zone peut être subdivisée en un arbre pour permettre une recherche plus rapide. Tout comme un espace linéaire peut être recherché efficacement avec une recherche binaire (et donc divisé en un arbre binaire), l'espace 2D peut être divisé en unquadtreeet l'espace 3D dans unoctree.

La source