Aufgabe: Algorithmus eines Zauberwürfels

[gordon freeman]

Zitat:

Zitat von Corpsman

Die Brute Force habe ich auch mal getestet. Selbst wenn man das mit einer Heuristischen Variante Koppelt geht es nicht.

Ich würde da auch eher zu Backtracking tendieren. Und dann den Backtracking-Algorythmus so anpassen, dass er nach der besten Lösung sucht. Sollte doch hinkommen, wenn man noch die kombinatorischen Elemente einbaut, wie sie oben schon aufgezählt sind.

[OT] Aber zum Thema Backtracking stelle ich jetzt auch mal ein kleines Tutorial in Aussicht mit allgemeiner Klasse, hab alles hier, muss es nur noch vernünftig dokumentieren und abtippen.

[Cöster]

Zitat:

Zitat von Corpsman

Sobald ich den Würfel mehr Verdreht habe ist die Rechenzeit derartig explodiert das nichts mehr ging. Zusätzlich mus man ja noch speichern wie man auf die Lösung kommt. Das hat mein 1 GB RAM Speicher dannn auch noch zerlegt.

Ließe sich das Problem nicht lösen? Ideal wäre es, wenn die Drehungsfolge an der Wegnummer ablesbar wäre.

Wenn das nicht ginge/zu kompliziert wäre:

Delphi-Quellcode:

private
  FBestWay: array of Byte;  // Speicherung des bisher besten Weges
  FCurrentWay: array of Byte; // Speicherung des aktuell berechneten Weges
  function AllTried(const Way: array of Byte): Boolean; // prüft, ob alles probiert wurde
  procedure CalcWay(var Way: array of Byte); // Berechnet nächsten Weg
  function Solved(var Way: array of Byte): Boolean; // geht Drehungen durch,
                                                    // bei Lösung: verkürzt Way und gibt True zurück
{...}

implementation

procedure TForm1.btnLoesen1Click(Sender: TObject);
var
  i: Byte;
begin
  SetLength(FCurrentWay, 30);
  for i := 1 to 29 do
    FCurrentWay[i] := 1;
  FCurrentWay[30] := 0;
  repeat
    CalcWay(FCurrentWay);
    if Solved(FCurrentWay) then
    begin
      SetLength(FBestWay, Length(FCurrentWay);
      FBestWay := FCurrentWay;
    end;
  until AllTried(FCurrentWay);
end;

{...}