Baumstruktur

[Agent]

Hi,

ich möchte in Java eine Baumstruktur erstellen und die einzelnen Spielstellungen eines Spieles (8-puzzle) in den Knoten dieses Baumes ablegen. Ein Beispielbild:

Hierfür habe ich bereits eine vorgefertigte Klasse Node von hier. Jetzt brauche ich, denke ich, noch eine Klasse List oder Tree, um einen Zusammenhang zwischen meinen einzelnen Knoten herzustellen. Ich habe hier von JTree gelesen, aber leider nicht wirklich verstanden, wie das funktionieren soll. Erstens steht hier nicht, was alles importiert werden muss und zweitens muss dieses JTree doch auch zu meiner Node-Klasse passen, oder? Nach längerem googeln habe ich aber leider kein hilfreicheres Tutorial zu Bäumen in Java gefunden. Wäre super, wenn mir hier jemand eine kleine Hilfestellung / einen Motivationsschub geben könnte!

Hier noch eine mögliche Anfangsstellung des Spieles 8-puzzle. Wie würdet ihr die Spielstellung (3x3-Array) im Knoten abspeichern?

 

[0x7F800000]

ich möchte in Java eine Baumstruktur erstellen und die einzelnen Spielstellungen eines Spieles (8-puzzle) in den Knoten dieses Baumes ablegen.

Wozu das denn? ???:L Scheint keine allgemein anwendbare Strategie zu sein, bei 9 gibt es schon über 350000 mögliche zustände, bei einem 4x4 Spielchen dürfte es nicht mehr in Integer passen, bei 5x5 sind es schon irgendwelche Quadriliarden von Permutationen möglich, wenn du alle auf einmal haben willst, kommst du da nicht weit, auf gut Deutsch: es ist völlig sinnlos...

Ein Beispielbild:

schön, aber *ein bisschen* zu klein für mein Geschmack :autsch:

Hierfür habe ich bereits eine vorgefertigte Klasse Node von hier

was ist das, wieso hast du das ausgegraben? Wie kommst du auf die Idee das in deinem Programm gebrauchen zu können ???:L

Jetzt brauche ich, denke ich, noch eine Klasse List oder Tree, um einen Zusammenhang zwischen meinen einzelnen Knoten herzustellen

was auch immer du damit meinst... baumknoten speichern normalerweise referenzen auf andere knoten, ansonsten wär's ja kein baum.

Ich habe hier von JTree gelesen, aber leider nicht wirklich verstanden, wie das funktionieren soll.

Stichwort "Swing"? :bahnhof: Das ist keine Datenstruktur, das ist graphischer schnickschnack für GUI's, das kann man definitiv in keinem Puzzle-spiel verbraten

Erstens steht hier nicht, was alles importiert werden muss

wird wohl javax.swing sein, hat aber mit deinem Programm nicht im geringsten irgendetwas zu tun... :noe:

und zweitens muss dieses JTree doch auch zu meiner Node-Klasse passen, oder? Nach längerem googeln habe ich aber leider kein hilfreicheres Tutorial zu Bäumen in Java gefunden.

erstmal solltest du die ganzen vorgefertigten Klassen in ruhe lassen, dir nützen die eh nichts.
Dann solltest du die ersten ~12 Kapiteln von diesem: Galileo Computing :: Java ist auch eine Insel (8. Auflage) – 2 Sprachbeschreibung
oder einem vergleichbaren Buch durchlesen bzw selektiv durchblättern, um ein bisschen Überblick über Grundlagen zu verschaffen, irgendwie hinterlässt dein Beitrag einen ziemlich verlorenen Eindruck ???:L

Allgemeines zu Bäumen: der erste teil des Satzes aus diesem Abschnitt: Tree (data structure) - Wikipedia, the free encyclopedia
sagt eigentlisch schon alles...

Hier noch eine mögliche Anfangsstellung des Spieles 8-puzzle. Wie würdet ihr die Spielstellung (3x3-Array) im Knoten abspeichern?

gar nicht. Alle Spielzustände abzuspeichern ist weder sinnvoll, noch machbar.

 

[Agent]

@0x7F800000: Dein Beitrag bringt mich leider nicht weiter.

Wozu das denn? ???:L Scheint keine allgemein anwendbare Strategie zu sein, bei 9 gibt es schon über 350000 mögliche zustände, bei einem 4x4 Spielchen dürfte es nicht mehr in Integer passen, bei 5x5 sind es schon irgendwelche Quadriliarden von Permutationen möglich, wenn du alle auf einmal haben willst, kommst du da nicht weit, auf gut Deutsch: es ist völlig sinnlos...

Ich habe nicht vor, den Baum voll zu expandieren. Dafür wäre er zu groß. Die Tiefe ist konstant und gegeben.

schön, aber *ein bisschen* zu klein für mein Geschmack :autsch:

Dann kauf dir eine (neue) Brille und nerve nicht mit sinnlosen Beiträgen! Das Bild ist groß genug um einen groben Überblick zu bekommen.

was ist das, wieso hast du das ausgegraben? Wie kommst du auf die Idee das in deinem Programm gebrauchen zu können ???:L

Es wäre mir nützlicher zu wissen, wieso ich es nicht gebrauchen kann. Ich wollte aus dieser Node-Klasse meine Spielstände/Knoten instanziieren :noe: Wenn du glaubst, dass das absoluter oberblödsinn ist, dann hättest du evtl. schreiben können, wieso du das glaubst

was auch immer du damit meinst... baumknoten speichern normalerweise referenzen auf andere knoten, ansonsten wär's ja kein baum.

Ja, das tun sie normalerweise. Darüber hinaus speichern sie aber doch auch ein paar Nutzdaten ab, oder etwa nicht ???:L

Stichwort "Swing"? :bahnhof: Das ist keine Datenstruktur, das ist graphischer schnickschnack für GUI's, das kann man definitiv in keinem Puzzle-spiel verbraten

Ja da lag ich komplett daneben. Ich hatte gehofft/geglaubt, dass es evtl. eine vorgefertigte Datenstruktur für Bäumchen gibt!?!

gar nicht. Alle Spielzustände abzuspeichern ist weder sinnvoll, noch machbar.

Ich hatte nie vor alle möglichen Spielstände in meinen Baum zu speichern. Falls ich es irgendwo geschrieben habe, muss ich mich korrigieren.

Und wenn mir jemand mit konstruktiver Kritik wirklich weiterhelfen will, dann freue ich mich auf die Beiträge!

 

[0x7F800000]

Ich habe nicht vor, den Baum voll zu expandieren. Dafür wäre er zu groß. Die Tiefe ist konstant und gegeben.

Okay, ohne Kontext ist das ein wenig schwierig zu beurteilen, habe den anderen Thread im Hausaufgaben-Subforum nicht wirklich verfolgt...

Dann kauf dir eine (neue) Brille und nerve nicht mit sinnlosen Beiträgen! Das Bild ist groß genug um einen groben Überblick zu bekommen.

Danke für den Tipp, aber ich glaube ich höre dann doch lieber auf den Optiker meines Vertrauens: der ist schließlich Profi und wird für schlaue ratschläge auch noch bezahlt, da kannst du nicht wirklich mithalten
Ich konnte auf dem Bild jedenfalls nichts lesen, und dachte daher, dass es evtl. ein Fehler mit dem Link ist, und du eigentlich nur ein Shortcut zu einem größeren Bild posten wolltest... whatever... :autsch:

Es wäre mir nützlicher zu wissen, wieso ich es nicht gebrauchen kann. Ich wollte aus dieser Node-Klasse meine Spielstände/Knoten instanziieren :noe: Wenn du glaubst, dass das absoluter oberblödsinn ist, dann hättest du evtl. schreiben können, wieso du das glaubst

einfach so code aus irgendwelchen eher unbekannten Bibliotheken zu nehmen und damit irgendwas machen zu wollen ist nunmal eine recht unübliche Vorgehensweise. Wenn die Aufgabe aus diesem Buch über künstliche Intelligenz stammt, und du das entsprechende Kapitel durchgearbeitet hast, und weißt, was da implementiert wurde, dann ist das natürlich was ganz anderes... ist das der Fall?

Ja, das tun sie normalerweise. Darüber hinaus speichern sie aber doch auch ein paar Nutzdaten ab, oder etwa nicht ???:L

ja, genau. Und das war's eigentlich schon. Wert des Knotens, und referenzen auf Kinder und/oder eine referenz auf den Parent, mehr ist normalerweise nicht nötig. Alles andere ist dann aber recht anwendungsspezifisch, daher lohnt es sich kaum, dafür irgendeine "allgemeine" datenstruktur zu basteln, deswegen ist das in der API auch nicht drin.

Ja da lag ich komplett daneben. Ich hatte gehofft/geglaubt, dass es evtl. eine vorgefertigte Datenstruktur für Bäumchen gibt!?!

wie gesagt... Es ist vom Anwendungsfall zu Anwendungsfall so unterschiedlich, dass man da kaum irgendwas "vorfertigen" kann. Es fängt schon damit an, dass man i.Allg. nicht wirklich weiß, in welche Richtung alles Zeigen soll: bei zB. TreeSet o.ä braucht man nur Referenzen auf Kinder, bei UnionFind Strukturen ist dagegen alles umgedreht, und man will nur den Zeiger auf parent. Zudem werden kleine Sachen in java allgemein ungerne vorgefertigt, weil man ja immer nur von einer nicht abstrakten Oberklasse ableiten kann: so eine allgemeine baumKnoten-Klasse würde also wahrscheinlich kaum einer verwenden.

Ich hatte nie vor alle möglichen Spielstände in meinen Baum zu speichern. Falls ich es irgendwo geschrieben habe, muss ich mich korrigieren.

nene, das hast du in der tat nirgends geschrieben, das hab ich mir wohl selbst irgendwie dazugedichtet... :bahnhof:

=> passende Baumstruktur einfach selber basteln...

 

[Ark]

@Agent: Für dieses Spiel braucht man keinen Baum, oder siehst du in den Spielsteinen irgendwo eine Gehört-Zu-Beziehung? Wie kommst du überhaupt auf die Idee, Bäume zu verwenden? Weißt du überhaupt was das ist? Und weißt du auch, was du willst?

Um mal zu zitieren: "You'll never find a programming language that frees you from the burden of clarifying your ideas."

Ark

 

[Agent]

@Agent: Für dieses Spiel braucht man keinen Baum

Wie kommst du zu dieser weisen Behauptung?

oder siehst du in den Spielsteinen irgendwo eine Gehört-Zu-Beziehung?

Ja, eigentlich schon. Jede Ebene im Baum repräsentiert eine Spieltiefe. Sprich: Die Wurzel ist das Anfangsfeld,...

Wie kommst du überhaupt auf die Idee, Bäume zu verwenden?

Wie sonst? Statisch, mittels Array? Wenn du sowas schreibst, wäre es gut einen Alternativvorschlag zu bekommen. Ich sehe hier gar keine andere Möglichkeit, als einen Such-Baum!?! Dieser enthält einfach eine gewisse Tiefe an möglichen Spielzügen.

Weißt du überhaupt was das ist? Und weißt du auch, was du willst?

Ich denke schon

 

[Ark]

@Agent: Dein "die einzelnen Spielstellungen eines Spieles" ist aber auch sehr missverständlich.

Also, was willst du?

1. Alle möglichen Spielzüge durchgehen und dabei diejenigen finden, die das Spiel lösen.
2. Gemachte Spielzüge speichern, damit sie rückgängig gemacht werden können.
3. etwas ganz anderes

Ark