Welche Probleme können mithilfe von Grafiken und Bäumen gelöst oder einfacher bewältigt werden?[geschlossen]

StackOverflow https://stackoverflow.com/questions/2988

Frage

Was sind die häufigsten Probleme, die mit diesen beiden Datenstrukturen gelöst werden können?

Es wäre gut für mich, auch Empfehlungen zu Büchern zu haben, die:

  • Implementieren Sie die Strukturen
  • Implementieren und erläutern Sie die Argumentation der Algorithmen, die sie verwenden
War es hilfreich?

Lösung

Das erste, woran ich denke, wenn ich diese Frage lese, ist: Welche Arten von Dingen verwenden Diagramme/Bäume? und dann denke ich rückwärts darüber nach, wie ich sie nutzen könnte.

Nehmen Sie zum Beispiel zwei häufige Verwendungszwecke eines Baumes:

  • Der DOM
  • Dateisysteme

Das DOM und auch XML ähneln Baumstrukturen.
alt text

Es macht auch Sinn. Dies ist sinnvoll, da diese Daten angeordnet werden müssen.Auch ein Dateisystem.Auf einem UNIX-System gibt es einen Wurzelknoten und eine Verzweigung nach unten.Wenn Sie ein neues Gerät montieren, befestigen Sie es am Baum.

Sie sollten sich auch fragen:Fallen die Daten in diese Art von Struktur?Erstellen Sie Datenstrukturen, die für das Problem sinnvoll sind, und der Rest folgt.

Soweit es einfacher ist, denke ich, dass das relativ ist.Sind Sie gut im Umgang mit rekursiven Funktionen zum Durchlaufen eines Baums/Diagramms?Was ist, wenn Sie den Baum ausbalancieren müssen?

Denken Sie an ein Programm, das ein Wortsuchrätsel löst.Sie könnten alle Buchstaben der Wortsuche in einem Diagramm abbilden und die umliegenden Knoten überprüfen, um zu sehen, ob diese Zeichenfolge mit einem der Wörter übereinstimmt.Aber könnte man das nicht auch mit einem einzelnen Array machen?Alles, was Sie wirklich tun müssen, ist, einen Index nach links und rechts zu verschieben, um die Buchstaben zu überprüfen, und um die Breite, um die Buchstaben über und unter den Buchstaben zu überprüfen.Die Lösung dieses Problems mit einem Diagramm ist nicht schwierig, aber es kann eine Menge zusätzlicher Arbeit und Schwierigkeiten mit sich bringen, wenn Sie mit der Verwendung dieser Diagramme nicht vertraut sind – das sollte Sie natürlich nicht davon abhalten, es zu tun, vor allem, wenn Sie sich damit befassen ihnen.

Ich hoffe, das hilft Ihnen, über diese Strukturen nachzudenken.Was eine Buchempfehlung angeht, müsste ich zustimmen Einführung in Algorithmen.

Andere Tipps

Schaltpläne.

Kompilierung (gerichtete azyklische Graphen)

Karten.Sehr kompakt als Diagramme.

Probleme mit dem Netzwerkfluss.

Entscheidung Bäume für Expertensysteme (sic)

Fischgrätendiagramme zur Fehlersuche, Prozessverbesserung und Sicherheitsanalyse.Um Bonuspunkte zu erhalten, implementieren Sie Ihren Fehlerwiederherstellungscode als Objekte, die Sind das Fischgrätendiagramm.

Nahezu jedes Problem kann im Sinne der Graphentheorie umgeschrieben werden.Ich mache keine Witze, schauen Sie sich irgendein Buch über NP-Vollständigkeitsprobleme an, es gibt einige ziemlich verrückte Probleme, die in die Graphentheorie umgewandelt werden, weil wir gute Werkzeuge für die Arbeit mit Graphen haben ...

Das Algorithmus-Design-Handbuch enthält einige interessante Fallstudien zum kreativen Einsatz von Grafiken.Trotz seines Namens ist das Buch sehr lesenswert und teilweise sogar unterhaltsam.

An meiner Uni gibt es dafür einen Kurs: CSE 326.Ich fand das Buch nicht allzu nützlich, aber die Projekte machen Spaß und bringen einem einiges bei, wie man einige der einfacheren Strukturen umsetzt.

Beispielsweise ist eines der häufigsten Probleme (gemessen an der Anzahl der Benutzer), das mit Bäumen gelöst wird, die Texteingabe über Mobiltelefone.Sie können Bäume verwenden, die nicht unbedingt binär sind, um den Raum möglicher Wörter darzustellen, die aus einer bestimmten Liste von Zahlen hervorgehen können, die ein Benutzer sehr schnell eingibt.

Algorithmen für Java:Teil 5 von Robert Sedgewick dreht sich alles um Graphalgorithmen und Datenstrukturen.Dies wäre ein gutes erstes Buch zum Durcharbeiten, wenn Sie einige Diagrammalgorithmen implementieren möchten.

Szenendiagramme zum Zeichnen von Grafiken in Spielen und Multimediaanwendungen nutzen häufig Bäume und Diagramme.Knoten repräsentieren zu rendernde Objekte, Transformationen, Steuerelemente, Gruppen usw.

Szenendiagramme verfügen normalerweise über mehrere Ebenen und Attribute, was bedeutet, dass Sie nur einige Knoten eines Diagramms (Attribute) in einer bestimmten Reihenfolge (Ebenen) zeichnen können.Abhängig von der Art des Szenendiagramms kann es zwei parallele Strukturen haben:Deklarationen und Instanziierung.Th

@DavidJoiner / alle:

FWIW:Eine neue Version des Handbuch zum Algorithmusdesign erscheint jeden Tag.

Der gesamte Kurs, für den Prof. Skiena dieses Buch entwickelt hat, ist auch im Internet verfügbar:

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

Bäume werden aufgrund ihrer rekursiven Natur viel häufiger in funktionalen Programmiersprachen verwendet.

Außerdem sind Grafiken und Bäume eine gute Möglichkeit, viele KI-Probleme zu modellieren.

In Spielen werden häufig Diagramme verwendet, um das Finden von Pfaden durch die Spielwelt zu erleichtern.Die grafische Darstellung der Welt kann über Algorithmen wie Breitensuche oder A* verfügen, um eine Route durch die Welt zu finden.

Sie verwenden Bäume auch oft, um Entitäten innerhalb der Welt darzustellen.Wenn Sie Tausende von Entitäten haben und eine an einer bestimmten Position finden müssen, kann die lineare Iteration durch eine Liste ineffizient sein, insbesondere wenn Sie dies häufig tun müssen.Daher kann der Bereich in einen Baum unterteilt werden, um ihn schneller durchsuchen zu können.So wie ein linearer Raum mit einer binären Suche effizient durchsucht (und somit in einen Binärbaum unterteilt) werden kann, kann der 2D-Raum in a unterteilt werden Quadtree und 3D-Raum in einen Oktbaum.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top