Quels problèmes peuvent être résolus ou abordés plus facilement à l’aide de graphiques et d’arbres ?[fermé]

Question

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 des livres qui :

• Mettre en œuvre les structures
• Mettre en œuvre et expliquer le raisonnement des algorithmes qui les utilisent

Answer 1

La première chose à laquelle je pense en lisant cette question est : quels types de choses utilisent des graphiques/arbres ? et puis je réfléchis à 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 structures arborescentes.

Cela a aussi du sens. Cela est logique en raison de la manière 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 des ramifications 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 qui ont du sens pour le problème et le reste suivra.

Dans la mesure où c'est plus facile, je pense que c'est relatif.Êtes-vous doué avec les fonctions récursives pour parcourir un arbre/un graphique ?Et si vous aviez besoin d'équilibrer l'arbre ?

Pensez à un programme qui résout un casse-tête de recherche de mots.Vous pouvez tracer toutes les lettres du mot recherché 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 avez à faire est de déplacer un index pour vérifier les lettres vers la gauche et la droite, et en 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 apprenez à le faire. eux.

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

Answer 2

Schémas de circuits.

Compilation (Graphiques acycliques dirigés)

Plans.Très compact comme graphiques.

Problèmes de flux réseau.

Décision des arbres pour les systèmes experts (sic)

Diagrammes en arête de poisson pour la recherche de pannes, l'amélioration des processus et l'analyse de la sécurité.Pour des points bonus, implémentez votre code de récupération d'erreur en tant qu'objets qui sont le diagramme en arête de poisson.

Answer 3

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

Answer 4

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

Answer 5

Il existe un cours pour de telles choses dans mon université : CSE 326.Je ne pensais pas que le livre était très utile, mais les projets sont amusants et vous en apprennent beaucoup sur la mise en œuvre de certaines des structures les plus simples.

Par exemple, l'un des problèmes les plus courants (en termes de nombre de personnes qui l'utilisent) résolu avec les arbres est celui de la saisie de texte sur le 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 saisit très rapidement.

Answer 6

Algorithmes pour Java :Partie 5 de Robert Sedgewick concerne les algorithmes graphiques et les structures de données.Ce serait un bon premier livre à parcourir si vous souhaitez implémenter des algorithmes graphiques.

Answer 7

Les graphiques de scène permettant de dessiner des graphiques dans des jeux et des applications multimédias utilisent largement des arbres et des graphiques.Les nœuds représentent les objets à restituer, les transformations, les contrôles, les 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 dont vous disposez, il peut avoir deux structures parallèles :déclarations et instanciation.Ème

Answer 8

@DavidJoiner / tous :

FWIW :Une nouvelle version du Manuel de conception d'algorithmes devrait sortir d'un jour à l'autre.

L'intégralité 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

Answer 9

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.

Answer 10

Les jeux utilisent souvent des graphiques pour faciliter la recherche de chemins à travers le monde du jeu.La représentation graphique du monde peut avoir des algorithmes tels que la recherche en largeur ou A* afin de trouver un itinéraire à travers celui-ci.

Ils utilisent aussi souvent des arbres pour représenter des entités du monde.Si vous avez des milliers d'entités et que vous devez en trouver une à une certaine position, parcourir une liste de manière linéaire peut s'avérer inefficace, surtout si vous devez le faire souvent.La zone peut donc être subdivisée en 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 un arbre quadruple et l'espace 3D dans un octarbre.