Hallo Leute,
die Frage, die ich heute an euch habe, ist eigentlich keine Javafrage, sondern viel mehr eine Frage nach einem guten Algorithmus für ein von mir selbst erdachtes Problem. Implementieren will ich die Sache dann natürlich in Java, aber das sollte, sobald wir uns den Algorithmus erarbeitet haben, kein Problem mehr sein.
Gegeben sind zwei Strings s1 und s2. Desweiteren haben wir drei Stringmanipulationsfunktionen:
Mit den drei Funktionen (es reichen bereits die ersten beiden) kann man durch wiederholtes Anwenden aus einem beliebigen String s1 jeden anderen String s2 in endlich vielen Schritten generieren (es geht zum Beispiel immer in s1.length()+s2.length() Schritten indem man erst alle Zeichen aus String s1 löscht und dann alle aus s2 in der richtigen Reihenfolge einfügt). Nun ordnen wir jeder der drei Funktionen eine nichtnegative Zahl zu, die sogenannten Kosten der Funktion. Die Kosten einer gegebenen Transformation berechnen sich einfach als Summe der Kosten der aufgerufenen Funktionen.
Was nun Aufgabe des Programms sein soll, ist, die geringsten Kosten zu ermitteln, um s1 zu s2 zu transformieren. Außerdem soll zusätzlich eine mögliche Vorgehensweise ermittelt werden, mit der man es zu diesen Kosten schafft.
Habt ihr Ideen, wie man hier vorgehen kann?
die Frage, die ich heute an euch habe, ist eigentlich keine Javafrage, sondern viel mehr eine Frage nach einem guten Algorithmus für ein von mir selbst erdachtes Problem. Implementieren will ich die Sache dann natürlich in Java, aber das sollte, sobald wir uns den Algorithmus erarbeitet haben, kein Problem mehr sein.
Gegeben sind zwei Strings s1 und s2. Desweiteren haben wir drei Stringmanipulationsfunktionen:
- Ein beliebiges Zeichen an einer beliebigen Stelle einfügen
- Ein Zeichen aus dem String entfernen
- Zwei benachbarte Zeichen vertauschen
Mit den drei Funktionen (es reichen bereits die ersten beiden) kann man durch wiederholtes Anwenden aus einem beliebigen String s1 jeden anderen String s2 in endlich vielen Schritten generieren (es geht zum Beispiel immer in s1.length()+s2.length() Schritten indem man erst alle Zeichen aus String s1 löscht und dann alle aus s2 in der richtigen Reihenfolge einfügt). Nun ordnen wir jeder der drei Funktionen eine nichtnegative Zahl zu, die sogenannten Kosten der Funktion. Die Kosten einer gegebenen Transformation berechnen sich einfach als Summe der Kosten der aufgerufenen Funktionen.
Was nun Aufgabe des Programms sein soll, ist, die geringsten Kosten zu ermitteln, um s1 zu s2 zu transformieren. Außerdem soll zusätzlich eine mögliche Vorgehensweise ermittelt werden, mit der man es zu diesen Kosten schafft.
Habt ihr Ideen, wie man hier vorgehen kann?
