Ich suche nach einem Algorithmus, der in der Lage ist, ein Array (2D) von Buchstaben zu erstellen, aus dem ich jedes Wort einer gegebenen Liste extrahieren könnte. Wie in Scrabble können Wörter einander kreuzen und horizontal, vertikal oder diagonal sein. Natürlich gibt es einige offensichtliche Lösungen, aber das Ziel ist es, es so klein wie möglich zu machen, was auch bedeutet, die Anzahl der Überfahrten zu maximieren.kleinste "scrabble board", die jedes Wort einer Liste enthält
Ich habe über eine maschinelle Lernmethode nachgedacht, die eine große Anzahl von Scrabble-Grids verwendet, die entweder von Menschen oder Computern erstellt wurden, aber ich bin sicher, dass es eine sauberere Methode gibt.
Danke für Ihre Hilfe.
PS: Das ist für ein Kunstprojekt, kein Scherz.
Das Finden der minimalen Lösung wird extrem schwierig sein. Können Sie sich nicht einfach für eine gute Lösung entscheiden, anstatt für eine optimale Lösung? In Bezug auf "was auch bedeutet, die Zahl der Kreuzung zu maximieren": Dies ist keine wahre Aussage. Die Maximierung der Anzahl von Kreuzungen ist ein sehr ähnliches Problem, aber das optimale Ergebnis für diese beiden Probleme wird in vielen Fällen unterschiedlich sein. –
Danke Leute, und tut mir leid, dass ich nicht genau genug bin. Eine gute Lösung wäre genug, denn das absolut Optimale zu finden wäre die Hölle. Außerdem, danke für die Hervorhebung, dass es nicht das selbe Problem wie das Optimieren der Kreuzung ist. Ich stimme völlig zu, ich meinte, "diese Probleme scheinen eng zu sein". –
(Scoring) Wörter in Scrabble sind nicht diagonal. –