Teil 2 Teil 3 Teil 4 Zum Schreiben dieses Artikels wurde ich durch eine schädliche Aufgabe aus der Java-Multithreading-Aufgabe veranlasst, die von den Entwicklern, nicht ohne einige Neckereien, als „StringBuilder-Aufgabe“ bezeichnet wurde. Der Kern ihrer Bedingung bestand darin, dass eine Reihe von Wörtern (in der Bedingung werden die Namen von Städten angegeben, was an ein Wortspiel für Kinder erinnert) nach dem Dominoprinzip angeordnet werden mussten, wobei der letzte Buchstabe des Wortes „n“ sein sollte gleich dem ersten Buchstaben des Wortes (n+1) sein, und es war bekannt, dass alle gegebenen (einzelnen) Wörter in einer solchen Kette addiert wurden. Wenn es möglich war, mehrere Optionen für die gewünschte Wortkette zusammenzustellen, wurde jede davon als Lösung akzeptiert. Trotz der scheinbaren Einfachheit und Klarheit der Bedingung war die Lösung des Problems alles andere als einfach und der meisterhafte Einsatz von StringBuilder konnte die Situation nicht retten. Es stellte sich heraus, dass es sich bei den Entwicklern des Problems um geordnete Isomorphe vom Planeten Linear Chaos handelte, die JavaRush-Kadetten mehr als einmal in Angst und Schrecken versetzten. Wie erwartet passten oberflächliche Lösungen dem Validator nicht, da es immer Ketten gab, die den naiven Algorithmus dazu zwangen, Wörter zu überspringen. Es war notwendig, zusätzliche „Krücken“ anzuhäufen, was zwar das Problem verkomplizierte, die Lösung im allgemeinen Fall jedoch nicht näher brachte und das Gefühl zunehmend verstärkte, dass es für eine einfache Bedingung eine ebenso einfache Lösung geben sollte. Ich musste meine Taktik ändern und mich ein wenig mit grundlegenderen Bereichen befassen. Lassen Sie mich gleich einen Vorbehalt anbringen, dass ich mich in keinem Fall als Experte für Graphentheorie betrachte; die Themen, die ich ansprechen werde, gehen fast nicht über den Rahmen der Lösung des Domino-Wortproblems hinaus, mit Ausnahme vielleicht von nur ein paar Exkurse theoretischer Natur. Also, Grafiken. Was ist ein Graph: Es ist eine Sammlung (Menge, Menge, Liste – was auch immer) von miteinander verbundenen Eckpunkten . Verbindungen werden üblicherweise Kanten genannt , Eckpunkte werden auch Knoten oder Knotenpunkte genannt. Das ist ein Graph: Das ist auch ein Graph: Wenn wir über eine Kante sagen können, dass sie eine Richtung hat, dann heißt der Graph orientiert : Die Graphen in den ersten beiden Bildern sind ungerichtet. Über sie kann man sagen, dass die Kante (u, v) identisch mit der Kante (v, u) ist, also beispielsweise die Kanten (0, 4) und (4, 0) dieselbe Kante sind. Pfeile an den Kanten eines gerichteten Graphen bedeuten, dass die Kante (u, v) ein Pfad vom Scheitelpunkt u zum Scheitelpunkt v ist und die Kante (v, u) nicht existiert. Im dritten Bild gibt es eine Kante (E, A). Es gibt keine Kante (A, E). Schauen wir uns die letzte Zeichnung genauer an. Sie können feststellen, dass Scheitelpunkt F überhaupt keine Kanten hat, das ist durchaus möglich. Wir stellen auch fest, dass in der Nähe des Scheitelpunkts A eine Kante aufgetaucht ist – eine Schleife – und zwischen den Scheitelpunkten B und D zwei unterschiedlich gerichtete Kanten liegen. Gerichtete Graphen ermöglichen solche Artefakte. Nehmen wir an, dass die Grafik eine Gruppe von Bekannten beschreibt, die sich gegenseitig Geschenke machen. Wir sehen, dass der gierige F niemandem etwas gab, B und D Geschenke austauschten (außer der Tatsache, dass jeder von ihnen jemand anderem ein Geschenk machte) und A sich selbst ein Geschenk machte, wahrscheinlich anlässlich der erfolgreichen Lösung von a Problem vom Planeten Linear Chaos. Beachten Sie übrigens, dass die Eckpunkte des Diagramms keine Zahlen sein oder Zahlen enthalten müssen; es handelt sich vielmehr um Container, d. h. Sie können jedes Objekt speichern. Ein Diagramm ist eine Beschreibung von Zusammenhängen. Ein wichtiger Begriff, der uns später nützlich sein wird – die Anzahl der Kanten, die an einem Scheitelpunkt befestigt sind (oder, wie man auch sagt, mit ihm in Zusammenhang stehen ), wird als Grad eines bestimmten Scheitelpunkts bezeichnet. Im ersten Bild hat beispielsweise Scheitelpunkt 0 den Grad 2, 1 den Grad 4, 3 den Grad 3 und Scheitelpunkt 0 der zweiten Abbildung den Grad 1. In diesem Artikel werden wir uns nicht mit der Vielfalt der verschiedenen Diagrammtypen befassen. Wir erwähnen nur, dass es auch gewichtete Diagramme gibt. solche, bei denen an jeder Kante eine bestimmte Zahl angebracht ist, die den „Preis“ ihrer Passage angibt. Verbundene Graphen haben eine Reihe von Untertypen, die sich durch ihre Eigenschaften unterscheiden. Beispielsweise werden Diagramme, deren Kanten nirgendwo einen Kreis bilden, Bäume genannt (sie haben interessante Familien mit tollen Namen wie zum Beispiel „Rot-Schwarz-Bäume“) und werden häufig in einer Vielzahl wichtiger Algorithmen und Datenstrukturen verwendet. Einen Graphen verwenden, um ein Problem zu lösen Das ist alles sehr interessant, sagen Sie, aber was hat das alles mit der Konstruktion einer Wortkette zu tun? Es stellt sich heraus, dass es das Direkteste ist. Schauen wir uns unser Testbeispiel aus der Bedingung an: { Amsterdam Melbourne New York Kiew Wien }. Schreiben wir in beliebiger Reihenfolge die „Knoten“-Buchstaben auf, an denen die Wörter hängen: {A, M, N, K, B} und verbinden sie mit Wörtern. Wie wir sehen können, haben wir einen gerichteten Graphen, in dem die Knoten Buchstaben sind und die Kanten sind Wörter, die sie verbinden. Wenn wir einen Weg finden, alle Kanten von Scheitelpunkt zu Scheitelpunkt zu durchlaufen, sodass wir jede Kante nur einmal besuchen, ist unser Problem gelöst. Versuchen wir, die Knoten im Diagramm etwas anders zu verteilen: Jetzt können wir besser erkennen, dass unser Diagramm eine geschlossene Schleife ist. Wir können die Sequenz mit jedem beliebigen Wort beginnen und es wird die richtige Entscheidung sein. Der Zustand des Problems sagt uns jedoch, dass jede Lösung ausreichend sein wird. Ersetzen wir Vena durch Vladimir: Wir sehen zwei Konsequenzen: Erstens mussten wir einen neuen Knoten hinzufügen, den Buchstaben P, und zweitens sehen wir, dass es nicht mehr möglich ist, unseren Graphen zu schleifen. Fassen wir das oben Genannte zusammen und führen wir zwei neue Begriffe ein: 1. Ein verbundener Graph, dessen Kanten durchquert werden können, indem jede einzelne nur einmal besucht wird, wird als Graph bezeichnet, der einen „ Euleschen Pfad“ enthält . Ein Merkmal eines solchen Graphen (mit Ausnahme des Fehlens von Eckpunkten ohne Kanten) ist der gerade Grad aller Eckpunkte außer zwei (und nur zwei). 2. Wenn sich herausstellt, dass es möglich ist, zum ursprünglichen Knoten zurückzukehren, sagen wir, dass es im Diagramm einen „Euleschen Kreis“ gibt . Ein Merkmal eines solchen Graphen (mit Ausnahme des Fehlens von Eckpunkten ohne Kanten) ist der gerade Grad aller Eckpunkte. Stellen wir uns unsere Städteliste wie folgt vor: {Moskau Anapa Adler Rostow am Don Wuhan}. Erstellen wir einen Graphen: Im Diagramm sehen Sie, dass dieser Graph einen Eulerschen Pfad hat. Es gibt nur zwei Eckpunkte mit ungeradem Grad – das sind M und L, der Rest ist gerade: A hat Grad 4, weil Die Schleife wird zweimal gezählt und P und Y haben Grad 2. Wenn wir einen Algorithmus entwickeln, der eine Eulersche Route basierend auf diesem Schema erstellen kann, beispielsweise in Form einer Liste {M, A, A, P, Y , L}, dann werden wir das Problem lösen, weil Die Ausgabe von Wörtern in einer bestimmten Reihenfolge ist nur eine Frage der Technik. Die Lösung unseres Domino-Wortproblems besteht also darin, einen Algorithmus zum Finden eines Eulerschen Pfades (der Kreis ist „frei“) in einem gerichteten Graphen zu implementieren. Weiter ->
Das ist auch ein Graph: 
Wenn wir über eine Kante sagen können, dass sie eine Richtung hat, dann heißt der Graph orientiert : 
Die Graphen in den ersten beiden Bildern sind ungerichtet. Über sie kann man sagen, dass die Kante (u, v) identisch mit der Kante (v, u) ist, also beispielsweise die Kanten (0, 4) und (4, 0) dieselbe Kante sind. Pfeile an den Kanten eines gerichteten Graphen bedeuten, dass die Kante (u, v) ein Pfad vom Scheitelpunkt u zum Scheitelpunkt v ist und die Kante (v, u) nicht existiert. Im dritten Bild gibt es eine Kante (E, A). Es gibt keine Kante (A, E). Schauen wir uns die letzte Zeichnung genauer an. Sie können feststellen, dass Scheitelpunkt F überhaupt keine Kanten hat, das ist durchaus möglich. Wir stellen auch fest, dass in der Nähe des Scheitelpunkts A eine Kante aufgetaucht ist – eine Schleife – und zwischen den Scheitelpunkten B und D zwei unterschiedlich gerichtete Kanten liegen. Gerichtete Graphen ermöglichen solche Artefakte. Nehmen wir an, dass die Grafik eine Gruppe von Bekannten beschreibt, die sich gegenseitig Geschenke machen. Wir sehen, dass der gierige F niemandem etwas gab, B und D Geschenke austauschten (außer der Tatsache, dass jeder von ihnen jemand anderem ein Geschenk machte) und A sich selbst ein Geschenk machte, wahrscheinlich anlässlich der erfolgreichen Lösung von a Problem vom Planeten Linear Chaos. Beachten Sie übrigens, dass die Eckpunkte des Diagramms keine Zahlen sein oder Zahlen enthalten müssen; es handelt sich vielmehr um Container, d. h. Sie können jedes Objekt speichern. Ein Diagramm ist eine Beschreibung von Zusammenhängen. Ein wichtiger Begriff, der uns später nützlich sein wird – die Anzahl der Kanten, die an einem Scheitelpunkt befestigt sind (oder, wie man auch sagt, mit ihm in Zusammenhang stehen ), wird als Grad eines bestimmten Scheitelpunkts bezeichnet. Im ersten Bild hat beispielsweise Scheitelpunkt 0 den Grad 2, 1 den Grad 4, 3 den Grad 3 und Scheitelpunkt 0 der zweiten Abbildung den Grad 1. In diesem Artikel werden wir uns nicht mit der Vielfalt der verschiedenen Diagrammtypen befassen. Wir erwähnen nur, dass es auch gewichtete Diagramme gibt. solche, bei denen an jeder Kante eine bestimmte Zahl angebracht ist, die den „Preis“ ihrer Passage angibt. Verbundene Graphen haben eine Reihe von Untertypen, die sich durch ihre Eigenschaften unterscheiden. Beispielsweise werden Diagramme, deren Kanten nirgendwo einen Kreis bilden, Bäume genannt (sie haben interessante Familien mit tollen Namen wie zum Beispiel „Rot-Schwarz-Bäume“) und werden häufig in einer Vielzahl wichtiger Algorithmen und Datenstrukturen verwendet. Einen Graphen verwenden, um ein Problem zu lösen Das ist alles sehr interessant, sagen Sie, aber was hat das alles mit der Konstruktion einer Wortkette zu tun? Es stellt sich heraus, dass es das Direkteste ist. Schauen wir uns unser Testbeispiel aus der Bedingung an: { Amsterdam Melbourne New York Kiew Wien }. Schreiben wir in beliebiger Reihenfolge die „Knoten“-Buchstaben auf, an denen die Wörter hängen: {A, M, N, K, B} 
und verbinden sie mit Wörtern. 
Wie wir sehen können, haben wir einen gerichteten Graphen, in dem die Knoten Buchstaben sind und die Kanten sind Wörter, die sie verbinden. Wenn wir einen Weg finden, alle Kanten von Scheitelpunkt zu Scheitelpunkt zu durchlaufen, sodass wir jede Kante nur einmal besuchen, ist unser Problem gelöst. Versuchen wir, die Knoten im Diagramm etwas anders zu verteilen: 
Jetzt können wir besser erkennen, dass unser Diagramm eine geschlossene Schleife ist. Wir können die Sequenz mit jedem beliebigen Wort beginnen und es wird die richtige Entscheidung sein. Der Zustand des Problems sagt uns jedoch, dass jede Lösung ausreichend sein wird. Ersetzen wir Vena durch Vladimir: 
Wir sehen zwei Konsequenzen: Erstens mussten wir einen neuen Knoten hinzufügen, den Buchstaben P, und zweitens sehen wir, dass es nicht mehr möglich ist, unseren Graphen zu schleifen. Fassen wir das oben Genannte zusammen und führen wir zwei neue Begriffe ein: 1. Ein verbundener Graph, dessen Kanten durchquert werden können, indem jede einzelne nur einmal besucht wird, wird als Graph bezeichnet, der einen „ Euleschen Pfad“ enthält . Ein Merkmal eines solchen Graphen (mit Ausnahme des Fehlens von Eckpunkten ohne Kanten) ist der gerade Grad aller Eckpunkte außer zwei (und nur zwei). 2. Wenn sich herausstellt, dass es möglich ist, zum ursprünglichen Knoten zurückzukehren, sagen wir, dass es im Diagramm einen „Euleschen Kreis“ gibt . Ein Merkmal eines solchen Graphen (mit Ausnahme des Fehlens von Eckpunkten ohne Kanten) ist der gerade Grad aller Eckpunkte. Stellen wir uns unsere Städteliste wie folgt vor: {Moskau Anapa Adler Rostow am Don Wuhan}. Erstellen wir einen Graphen: 
Im Diagramm sehen Sie, dass dieser Graph einen Eulerschen Pfad hat. Es gibt nur zwei Eckpunkte mit ungeradem Grad – das sind M und L, der Rest ist gerade: A hat Grad 4, weil Die Schleife wird zweimal gezählt und P und Y haben Grad 2. Wenn wir einen Algorithmus entwickeln, der eine Eulersche Route basierend auf diesem Schema erstellen kann, beispielsweise in Form einer Liste {M, A, A, P, Y , L}, dann werden wir das Problem lösen, weil Die Ausgabe von Wörtern in einer bestimmten Reihenfolge ist nur eine Frage der Technik. Die Lösung unseres Domino-Wortproblems besteht also darin, einen Algorithmus zum Finden eines Eulerschen Pfades (der Kreis ist „frei“) in einem gerichteten Graphen zu implementieren. Weiter ->
GO TO FULL VERSION