Welche Probleme können gelöst werden, oder leichter in Angriff genommen, mit Grafiken und Bäume?

stimmen
10

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 für Bücher zu haben, dass:

  • Implementieren Sie die Strukturen
  • Umzusetzen und die Argumentation der Algorithmen erklären, die sie verwenden
Veröffentlicht am 06/08/2008 um 01:56
quelle vom benutzer
In anderen Sprachen...                            


10 antworten

stimmen
16

Das erste , was ich denke , wenn ich lese diese Frage ist: welche Arten von Dingen verwendet Graphen / Bäume? und dann denke ich , nach hinten, wie ich sie nutzen könnten.

Nehmen wir zum Beispiel zwei gemeinsame Nutzungen eines Baumes:

  • der DOM
  • Dateisysteme

Das DOM und XML was das betrifft, ähneln Baumstrukturen.
Alt-Text

Es macht auch Sinn. Es macht Sinn , weil, wie diese Daten angeordnet werden muss . Ein Dateisystem, auch. Auf einem UNIX - System gibt es einen Wurzelknoten und Verzweigungen unten. Wenn Sie ein neues Gerät montieren, sind Sie es auf den Baum zu befestigen.

Sie sollten sich auch fragen: Hat die Daten fallen in diese Art von Struktur? Erstellen von Datenstrukturen, den Sinn für das Problem und der Rest wird folgen machen.

Was als einfacher, ich denke, das ist relativ. Sind Sie gut mit rekursiven Funktionen einen Baum / Graph zu durchqueren? Was passiert, wenn Sie den Baum balancieren müssen?

Denken Sie an ein Programm, das ein Wortsuchrätsel löst. Sie könnten alle Buchstaben des Wortes Suche in einem Diagramm kartieren und Prüfknoten Umgebung zu sehen, ob diese Zeichenfolge eines der Wörter ist passend. Aber könnte nicht Sie tun genau das gleiche mit mit einem einzigen Array? Alles, was Sie wirklich tun müssen, ist einen Index bewegen Buchstaben nach links und rechts, und durch die Breite zu prüfen, oben und unten Buchstaben zu überprüfen. Um dieses Problem mit einem Diagramm zu lösen, ist nicht schwierig, aber es kann eine Menge zusätzlicher Arbeit und Schwierigkeiten erstellen, wenn Sie mit der Verwendung von ihnen nicht vertraut sind - natürlich, dass von Ihnen tut es nicht entmutigen sollte, vor allem, wenn Sie lernen, über Sie.

Ich hoffe , das hilft Ihnen über diese Strukturen zu denken. Wie für ein Buch Empfehlung, würde ich mit gehen Introduction to Algorithms .

Beantwortet am 06/08/2008 um 02:28
quelle vom benutzer

stimmen
4

Schaltpläne.

Compilation (gerichteten azyklischen Graphen)

Maps. Sehr kompakt als Graphen.

Netzwerk-Flow-Probleme.

Entscheidung Bäume für Expertensysteme (sic)

Fishbone - Diagramme zur Fehlersuche, Prozessverbesserung, Sicherheitsanalyse. Für Bonuspunkte, implementieren Ihre Fehlerbehebungscodes als Objekte , die sind das fishbone Diagramm.

Beantwortet am 28/08/2008 um 04:29
quelle vom benutzer

stimmen
3

So gut wie jedes Problem kann in Bezug auf die Graphentheorie neu geschrieben werden. Ich scherze nicht, schauen Sie in jedem Buch über NP vollständigen Probleme gibt es einige ziemlich verrückte Probleme, die in der Graphentheorie erhalten verwandelt, weil wir für die Arbeit mit Graphen gute Werkzeuge haben ...

Beantwortet am 09/03/2009 um 14:54
quelle vom benutzer

stimmen
2

Der Algorithmus Design Manual enthält einige interessante Fallstudien mit kreativen Einsatz von Graphen. Trotz seines Namens ist das Buch sehr gut lesbar und sogar unterhaltsam zu Zeiten.

Beantwortet am 12/08/2008 um 21:59
quelle vom benutzer

stimmen
1

Spiele oft Diagramme verwenden zu erleichtern Pfade über die Spielwelt zu finden. Die Diagrammdarstellung der Welt kann Algorithmen wie Breitensuche oder A *, um eine Route über sie zu finden.

Sie verwenden auch oft Bäume Einheiten innerhalb der Welt zu vertreten. Wenn Sie Tausende von Unternehmen haben und brauchen eine an einer bestimmten Position zu finden , dann Iterieren linear durch eine Liste kann ineffizient sein, besonders wenn man es oft tun müssen. Daher kann die Fläche in einen Baum unterteilt werden , damit es schneller gesucht werden. So wie ein linearer Raum effizient mit einer binären Suche (und somit unterteilt in einen binären Baum), 2D - Raum gesucht werden kann in eine unterteilt werden Quadtree und 3D - Raum in einen Octree .

Beantwortet am 01/07/2010 um 12:11
quelle vom benutzer

stimmen
1

Bäume sind viel mehr in funktionalen Programmiersprachen wegen ihrer rekursiven Natur verwendet.

Auch Grafiken und Bäume sind eine gute Möglichkeit, eine Menge KI Probleme zu modellieren.

Beantwortet am 09/03/2009 um 14:25
quelle vom benutzer

stimmen
1

@DavidJoiner / all:

FWIW: Eine neue Version des Algorithmus Design Manual ist aufgrund out jetzt jeden Tag.

Der gesamte Kurs, den er Prof Skiena dieses Buch entwickelt ist auch im Internet verfügbar:

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

Beantwortet am 27/08/2008 um 00:56
quelle vom benutzer

stimmen
1

Szenengraphen für das Zeichnen Grafik in Spielen und Multimedia-Anwendungen verwenden stark Bäume und Graphen. Knoten repräsentieren Objekte gerendert, Transformationen, Kontrollen, Gruppen zu, ...

Szenegraphen haben in der Regel mehrere Schichten und Attribute, die bedeuten, dass Sie nur einige Knoten eines Graphen (Attribute) in einer bestimmten Reihenfolge (Schichten) zeichnen. Je nach Art des Szenegraphen haben Sie es zwei parralel Strukturen haben: Erklärungen und Instanziierung. th

Beantwortet am 08/08/2008 um 16:58
quelle vom benutzer

stimmen
1

Algorithmen für Java: Teil 5 von Robert Sedgewick ist über die Graph - Algorithmen und Datenstrukturen. Dies wäre ein gutes erstes Buch sein , durch arbeiten , wenn Sie einige Graphenalgorithmen implementieren mögen.

Beantwortet am 08/08/2008 um 16:46
quelle vom benutzer

stimmen
1

Es gibt einen Kurs für solche Dinge an meiner Universität: CSE 326 . Ich glaube nicht , das Buch zu nützlich war, aber die Projekte sind Spaß und lernen Sie ein gutes Stück über einige der einfacheren Strukturen umzusetzen.

Als Beispiele, eines der häufigsten Probleme (nach Anzahl der Menschen mit ihm), die mit Bäumen gelöst ist, dass der Texteingabe Handy. Sie können Bäume, die nicht unbedingt binär, verwenden Sie den Raum der möglichen Worte darzustellen, die von einer bestimmten Liste von Zahlen herauskommen kann, dass ein Benutzer Schläge in sehr schnell.

Beantwortet am 06/08/2008 um 02:18
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more