Optimale Platzierung von 4 Wörtern innerhalb eines beliebig großen Rasters [duplizieren]
Problemstellung:
Platziere sie mit vier Wörtern innerhalb eines m x n Quadrats so, dass die Fläche des Gitters so klein wie möglich ist.
Wörter müssen von links nach rechts und von oben nach unten innerhalb des Rasters verlaufen. Buchstaben können sich überlappen, aber zusätzliche Wörter können nicht gebildet werden. Alle Wörter müssen in einer riesigen Kette miteinander verbunden sein.
Beispielgittern, die mit den 4 Wörtern "eins, zwei, drei und vier" gebildet werden können. Beachten Sie, dass das letzte Gitter am meisten optimiert ist.
Ich versuche Python zu lernen, und ich dachte, das wäre eine gute Anwendung, um mir die Zähne anzubeißen.
Irgendwelche Ideen, wie ich meine Daten und Algorithmen strukturieren kann, um ein Problem wie dieses zu lösen? Ich suche keine direkte Antwort, aber einige Tipps wie:
Verwenden Sie diese Bibliothek oder diese Klasse oder diese Datenstruktur. Oder iteriere so durch den verfügbaren Platz.
1 Antwort
Denken Sie darüber nach, welches Raster Sie maximal benötigen würden? Wenn die Wörter one , two , three , four sind, dann wäre das maximale Größenraster
12 x 12. Dies ist die Größe eines Rasters, in dem jedes Wort Ende an Ende platziert wird und den letzten Buchstaben des vorherigen Wortes teilt.
Jetzt haben wir den Raum. Wie passen Sie die Wörter in den Raum? Versuchen Sie, über eine Brute-Force-Methode nachzudenken. Was würde das zur Folge haben?
Versuchen Sie, alle möglichen Kombinationen von Mustern zu durchlaufen. Du kannst jedes Wort auf 24 Arten platzieren und es gibt 4 Wörter, also hast du ~ 500.000 Kombinationen, die für moderne Computer nicht viel sind. Sehen Sie, welche Muster tatsächlich die Kriterien erfüllen (Buchstaben stimmen überein, usw.).
Sobald Sie eine Brute-Force-Methode haben, wie könnten Sie sie verfeinern?
Was die Datenstruktur angeht, brauchen Sie nur ein Raster, in dem Zeichen gespeichert werden können. Du könntest eine verschachtelte Listenstruktur, ein numpy Array, Pandas oder eine Menge anderer Sachen verwenden. Versuchen Sie zunächst, das Problem zu lösen, und verfeinern Sie es später.
Tags und Links python algorithm optimization constraint-satisfaction