MastersForum

Habs zuerst in java auch rekursiv gemacht (sieht man vielleicht noch am Aufbau der GreedySearch-Funktion ), aber bei zu vielen Wörtern verursacht das n Stack-Overflow...

Die rekursive wär schöner, jo. Aber die iterative Variante is halt speicherfreundlicher.

Im Endeffekt gehts glaub ich in Sprachen wie Haskell&Co am einfachsten zu implementiern. [Btw, Haskell zB wandelt einfache Rekursionen in Iterationen um...] Prolog wär für sowas n bisserl Overkill.

@]I[plexiq : da ich mit meinem Info studium noch nich begonnen habe, hab ich keine ahnung von der begrifflichkeit, und hab da wohl einiges durcheinandergeworfen.

mit "suchbaum" usw hab ich das verfahren gemeint, dass die schachcomputer anwenden, um stellungen durchzugehen.

die computer haben ja so eine art suchbaum mit verästelungen, und wenn bei einem bestimmten knoten nichts rauskommt, wird dieser abgebrochen bzw. übergangen beim nächsten mal, wenn die tiefe grösser wird

ka wie ich es beschreiben soll, aber ich hab (glaube ich zumindest ^^) das gemeint, was du zuletzt beschrieben hast, auch wenns mangels fachbegriffe meinerseits ganz anders rüberkam ^^

@Max:
Ich versuch ganz auf die schnelle vielleicht nochmal zu erklärn worums mir bei dem Thema gegangen ist:

Zum Begriff:
Heuristik = Information/Wissen über die Problemstellung, das vom Suchalgorithmus verwendet wird um den Suchraum einzuschränken. Dh beim Schachspiel zB wird als Heuristik eine Beweertung der Stellung gemacht, und danach entschieden ob es sich lohnt diese Zugfolge weiter zu untersuchen.

In der Angabe von Nilpferd steht, man soll die optimale (längste) Wortkette finden. Das kann man nur machen, wenn du den gesamten Suchraum abgrast, also im Prinzip alle möglichen Kombinationen durchprobierst. Dh die Angabe is, so wie sie formuliert ist, eigentlich schwachsinnig.

Man kann mit Heuristiken sehr wohl in kurzer Laufzeit gute Lösungen finden, aber man verzichtet dabei auf die geforderte "optimale" Lösung.

Nun kam von dir der Einwurf, das Schachcomputer wohl auch riesige Suchraume nach guten Zugfolgen abgrasen, und das das kleine Problem hier wohl einfach zu lösen sein sollte.

Quoted

Wenn man von einer begrenzten Wörterkette ausgeht und einem anständigen prozessor, dazu ein gescheiter algorithmus, sollte sich auf jeden fall ein ergebnis ergeben, dass in vertretbarer zeit gefunden wird.

ansonsten würden die schachcomputer auch nicht weltermeister besiegen Augenzwinkern

Ist schon richtig, das Schachkomputer sehr grosse Suchräume absuchen, aber sie setzen stark auf Heuristiken um schwache Zugfolgen vorzeitig zu erkennen und dadurch den Suchraum möglichst klein zu halten.

Man hat dabei keine Gewissheit, ob sich ne vermeintlich schwache Zugfolge nicht doch zu ner genialen Kombination entwickeln könnte. Dh man verwirft vorzeitig mögliche (optimale) Lösungen - das ist halt der Preis den man für die Schnelligkeit zahlen muss.

Worauf ich eigentlich hinaus wollte:
Deine Argumentation mit dem Schachprogramm ist deshalb falsch, weil genau diese Schachprogramme sehr auf Heuristiken aufbauen, also *keine* optimalen Lösungen finden.

Es ist für die Wortketten-Angabe schon ab ein paar hundert Wörtern nicht mehr möglich die optimale Lösung zu finden.

Quoted

Original von ]I[plexiq
Wenn du die Wörter nach Anfangsbuchstaben unterteilst (Hashtable!, oder auch nen Suchbaum - is aber net so gut), brauchst jede Runde nur k Möglichkeiten Checken. Wobei k hier die durchschnittliche Anzahl der Wörter mit gleichem Anfang ist. Alle andren Möglichkeiten brauchst net checken, da die sicher keine gültige Lösung ergeben.

Für k = Länge der Längsten Kette ergibt sich ein Laufzeitverhalten von O(n*v^k).

Ok, eine Hashtabelle mit Alphabetsgrösse hoch 3 wäre eine feine Sache.

Quoted

Wenn du versuchen würdest mit allen PCs der Welt für die 300.000-Wörter Liste oben, die optimale Wortkette zu finden, würd die Lösung net vor Ende des Universums ausgespuckt werden

Wie komm ich drauf?

Meine Wortketten werden da so um 8800 Wörter lang. Wenn man davon ausgeht das die beste wahrscheinlich jenseits der 10.000 lang is, und man zumindest 2 (arge Untertreibung btw!) Entscheidungen pro Wört machen muss, kommt man auf 2^10.000 = 2x10^3000. Das würd dem Brute-Forcen eines 10.000 Bit Keys gleichkommen.

Wie wahrscheinlich ist eine 8800er Kette bei 300.000 Wörtern? Spontan würde ich sagen, es ist irrsinnig wenig - allerdings gibt es ja die kombinatorische Explosion bei den Möglichkeiten.

Bei 1.000.000 zufällig generierten Ketten war die längste 44 Wörter lang.

Mit Greedy-Search findet man die 8800 Wörter lange Kette .

Also, ja: Die Chance so lange Ketten ohne Heuristiken zu finden geht gegen Null

kopf brum ich darf das jetzt alles in java schreiben

und muss noch eine grafische oberfläche machen


geht das nicht ein wenig simpler?? da war immerhin die junior aufgabe und das muss aus dem ersten kapitel von faust sein

Ich habs doch schon komplett in Java geproggt?

Da n Swing gui drüberzuschmeissen dauert 10 min -_-

merk schon aber das hatten die anderen in anderen aufgaben auch das dauerte immer ewig mit true und false naja dann nehm ich das so und amch noch ne oberfläche wo ich den text auf den er sich beziehen muss rein schreibe hoffe das klappt

und noch ma thx das ihr uns so geholfen habt

@shabby, das Programm das ich geschrieben hab kann den Text schon direkt aus nem beliebigen File einlesen. Versteh net warum du überhaupt ne grafische Oberfläche brauchst?

Oder war das gefordert...?

Quoted

Original von ]I[plexiq
Mit Greedy-Search findet man die 8800 Wörter lange Kette .

Also, ja: Die Chance so lange Ketten ohne Heuristiken zu finden geht gegen Null

Ah, ok, Instinkt funktioniert doch.

Ein gutes hat die Aufgabe: sie ist ein Vorzeigebeispiel für die Effizienz von Greedy-Approximationsalgorithmen, gleich mal merken.

So, jetzt sogar mit GUI

"auführbares" jar incl. Source

jaja, i suck @ GUIs

Falls java korrekt installiert is, sollte man das eigentlich nur mehr downloaden & doppelklicken müssen -_-

apropos Java Swing usw.
ist es möglich in einer JTable Zahlen tieferzustellen, also Einträge wie z.B. a² (die zwei als Index, aber weiß auch hier nicht, wie das tiefergestellt geht...)?
Und wenn ja wie?

so eigentlich muss es jetzt klappen ich glaub ich wähle info ab

thx für euren aufwand wenn ihr lust habt wir haben da sicher noch ein paar HA s für euch^^

ne hat uns geholfen und ich hoff das funzt so morgen auch


mfg shabby

Hab grad erst gecheckt, das diese Aufgabe für nen Informatik-Wettbewerb ausgeschrieben is, lol

Btw, mit leichter Modifikation kriegt man aus der Wortliste oben sogar Wortketten bis 22.000 Wörter hin. Allerdings auch bei ~100 facher Suchzeit

Aus dem Faust-Text der Info-Angabe find ich aber nur 3 Wörter-Ketten. Dort gibts nur ~300 verschiedene Wörter, hätte man also noch bisserl "tiefer" suchen können. Hättet ihr mal den Faust-Text als Angabe mitgepostet