Bandbreitenoptimierung für Matrizen

[Bjoerk]

Ich habe eine Indextabelle (IndexOfU), die folgendermaßen aufgebaut wird:

Delphi-Quellcode:

procedure TFrame.GrowNU(const Index: integer); // Anzahl Unbekannte;
begin
  Inc(FNU);
  FIndexOfU[Index] := FNU;
end;

procedure TFrame.GrowNV(const Index: integer); // Anzahl Auflagergleichungen;
begin
  FIndexOfU[Index] := FN - FNV; // N = DG * Nodes.Count;
  Inc(FNV);
end;

procedure TFrame.CalcIndexOfU;
var
  I, J, Index: integer;
begin
  for I := 1 to FNodes.Count do
    for J := 1 to FDG do // Ebenes Stabwerk 3, Räumliches 6, Ebenes Fachwerk 2, Räumliches 3;
    begin
      Index := FDG * (I - 1) + J;
      if J = 1 then
        if not FNodes.Item[I].Fest.vX then
          GrowNU(Index)
        else
          GrowNV(Index);
      if J = 2 then
        if not FNodes.Item[I].Fest.vY then
          GrowNU(Index)
        else
          GrowNV(Index);
      if FD = 3 then // Räumlich;
      begin
        if J = 3 then
          if not FNodes.Item[I].Fest.vZ then
            GrowNU(Index)
          else
            GrowNV(Index);
        if not FSyst then // Stabwerk;
        begin
          if J = 4 then
            if not FNodes.Item[I].Fest.pX then
              GrowNU(Index)
            else
              GrowNV(Index);
          if J = 5 then
            if not FNodes.Item[I].Fest.pY then
              GrowNU(Index)
            else
              GrowNV(Index);
          if J = 6 then
            if not FNodes.Item[I].Fest.pZ then
              GrowNU(Index)
            else
              GrowNV(Index);
        end;
      end
      else
        if not FSyst and (J = 3) then // Ebenes StabwerK;
        begin
          if not FNodes.Item[I].Fest.pZ then
            GrowNU(Index)
          else
            GrowNV(Index);
        end;
    end;
end;

Nun soll IndexOfU im Bereich 1..NU so "gemischt" werden, so daß NB möglichst klein wird.

Delphi-Quellcode:

procedure TFrame.SimulateLoad(const T1, T2: integer);
var
  k1, k2, i1, i2, Row, Col: integer;
begin
  i1 := FDG * (T1 - 1);
  i2 := FDG * (T2 - 1);
  for k1 := 1 to FDG do
  begin
    Row := FIndexOfU[i1 + k1];
    if Row <= FNU then
      for k2 := 1 to FDG do
      begin
        Col := FIndexOfU[i2 + k2];
        if (Col >= Row) and (Col <= FNU) then
          FNB := Max(FNB, Col - Row + 1);
      end;
  end;
end;

procedure TFrame.CalcNB; // Bandbreite;
var
  I: integer;
begin
  FNB := 0;
  repeat ***
    FIndexOfU := ..
    for I := 1 to FElements.Count do
    begin
      SimulateLoad(FElements.Item[I].Left, FElements.Item[I].Left);
      SimulateLoad(FElements.Item[I].Right, FElements.Item[I].Right);
      SimulateLoad(FElements.Item[I].Left, FElements.Item[I].Right);
      SimulateLoad(FElements.Item[I].Right, FElements.Item[I].Left);
    end;
  until FB möglichst klein; ***
end;

Verstanden was ich meine? Kennt jemand ein Prinzip, nach welchem man NB iterieren könnte (außer Zufallslisten)? BTW, bitte nicht wundern, ist alles 1 basiert.

[Dejan Vu]

Vermutlich bin ich der Einzige, der das nicht verstanden hat. Es geht ja um irgendwelche Gleichungen, Stabwerke, Fachwerke, Ebenen, Räume oder irgendwie so.

Gibt es eine Möglichkeit, das so zu erklären, das man das versteht? Wenn es nämlich um Optimierungen geht, könnte sich das Problem auf eines der Standardprobleme reduzieren, für die es fertige Lösungen gibt.

[BUG]

Zitat von Dejan Vu:

Vermutlich bin ich der Einzige, der das nicht verstanden hat.

Nope Vermutlich wäre es auch hilfreich zu wissen, was NB, NV, NU, usw... bedeuten.

[frankyboy1974]

Hallo,

ich hab das Ausgangsproblem leider auch nicht verstanden, wenn ich aber etwas von Optimierung und Zufallslisten lese, würden mir spontan Evolutionäre Algorithmen einfallen. Ist nur mal so in den Raum geworfen.

mfg

Frank

[TheMiller]

Moin!

Nennt mich jetzt ruhig "kleinlich", aber ein "Hallo; Bitte; Danke; (Tschüss)" wäre auch noch ganz nett, wenn man möchte, dass einem geholfen wird. ( Nicht böse gemeint, also nicht sauer sein )

[bcvs]

Ich habe das in etwa verstanden (wir kommen aus der selben Branche, wobei das ja eher ein allgemeines mathematisches Problem ist)

Nochmal zum Verständnis:

Delphi-Quellcode:

procedure TFrame.CalcNB; // Bandbreite;
var
  I: integer;
begin
  FNB := 0;
  repeat ***
    FIndexOfU := .. 
    for I := 1 to FElements.Count do
    begin
      SimulateLoad(FElements.Item[I].Left, FElements.Item[I].Left);
      SimulateLoad(FElements.Item[I].Right, FElements.Item[I].Right);
      SimulateLoad(FElements.Item[I].Left, FElements.Item[I].Right);
      SimulateLoad(FElements.Item[I].Right, FElements.Item[I].Left);
    end;
  until FB möglichst klein; ***
end;

Ich nehme an, bei FIndexOfU := soll die Indextabelle in einer geänderten Reigenfolge neu aufgebaut werden. Passiert das durch Aufruf von CalcIndexOfU? Dann könnte man dort vielleicht nicht mit for I := 1 to FNodes.Count über die Nodes laufen, sondern immer möglichst benachbarte Nodes als nächstes einsetzen.

Ansonsten ist auch die Frage, ob die Rechenzeit, die man in eine aufwändige Bandbreitenoptimierung reinsteckt, später bei der eigentlichen Martixberechnung wieder reingeholt wird.

[Rollo62]

Ich verstehe zwar auch nichts, zumal die Struktur der Nodes unklar sind.

Aber wenn es um Performance geht wäre es nicht vielleicht sinnvoll alles in Key/Value Hash-Tabellen umzuprogrammieren
http://docwiki.embarcadero.com/Libra...ns.TDictionary
(

Rollo

[BUG]

Ok, das hat mich jetzt doch interessiert und ich habe mich etwas eingelesen: Es geht darum die Breite des Bandes einer Bandmatrix zu minimieren.

Imho würde sich ein Branch-and-Bound-Verfahren anbieten: Jeden anfügen eines Elemente ist ein Branch-Schritt.
Wenn du das Minimum (oder einen "akzeptablen" Wert) erreicht hast brichst du ab; wenn du irgendwann beim Sortieren die bisherige obere Schranke überschreitest, kannst du den Branch abschneiden: egal wie du den Suffix sortierst, der Zielwert wird nicht besser.

Eine untere Schranke findet man leicht: Die minimale Breite des Bandes ist die maximale Anzahl von Abhängigkeiten eines Elementes.

Dann wäre es natürlich schön, eine möglichst gute erste obere Schranke zu haben.
Das könntest du mit einem Greedy-Verfahren versuchen: Fange mit einem Element mit maximal vielen Abhängigkeiten an, dann füge immer ein Element hinzu, das die älteste Abhängigkeit von Vorgängern erfüllt. Das Ergebnis ist vermutlich nicht optimal, aber vermutlich besser als ausgewürfelt. Alternativ hast du vielleicht Informationen, die du für eine erste Sortierung nutzen kannst, z.B. räumliche Anordnung.

[Bjoerk]

Am besten, ich mach ein Beispiel. Das Beispiel verwendet 5 Knoten und 4 Stäbe. Ein Knoten hat hier 3 Freiheitsgrade, eine Verschiebung in X-Richtung, eine Verschiebung in Y-Richtung und eine Verdrehung in Z-Richtung (Verdrehung um die Z-Achse). Man gibt die Koordinaten der Knoten vor und man gibt Stäbe an.

Ein Stab hat einen linken und einen rechten Anschlußknoten (FElements.Item[I].Left, FElements.Item[I].Right). Hier Stab 1 von Knoten 1 nach Knoten 2, Stab 2 geht von Knoten 2 nach Knoten 5, Stab 3 von Knoten 5 nach Knoten 3 und Stab 4 von Knoten 3 nach Knoten 4.

Dann gibt man an, welche Freiheitsgrade an Knoten ausgeschlossen werden (Auflager). Im Beispiel sind an den Knoten 1, 4 und 5 die Verschiebungen in Y-Richtung ausgeschlossen, am Knoten 5 zusätzlich die Verschiebung in X-Richtung.

Mit diesen Angaben kann man eine Indexliste aufbauen und damit eine Systemsteifigkeitsmatrix aufstellen. Die Indexliste gibt an, daß z.B. die Reihe/Spalte 2 der Matrix nach Reihe/Spalte 15 zu verschieben ist (IndexOfRow, IndexOfCol). Die Matrix ist symmetrisch und hat eine Bandstruktur. Wie groß die Bandbreite ist kann man berechnen.

Delphi-Quellcode:

procedure TFrame.SimulateLoad(const T1, T2: integer);
var
  k1, k2, i1, i2, Row, Col: integer;
begin
  i1 := FDG * (T1 - 1);
  i2 := FDG * (T2 - 1);
  for k1 := 1 to FDG do
  begin
    Row := FIndexOfU[i1 + k1];
    if Row <= FNU then
      for k2 := 1 to FDG do
      begin
        Col := FIndexOfU[i2 + k2];
        if (Col >= Row) and (Col <= FNU) then
          FNB := Max(FNB, Col - Row + 1);
      end;
  end;
end;

procedure TFrame.CalcNB; // Bandbreite;
var
  I: integer;
begin
  FNB := 0;
  for I := 1 to FElements.Count do
  begin
    SimulateLoad(FElements.Item[I].Left, FElements.Item[I].Left);
    SimulateLoad(FElements.Item[I].Right, FElements.Item[I].Right);
    SimulateLoad(FElements.Item[I].Left, FElements.Item[I].Right);
    SimulateLoad(FElements.Item[I].Right, FElements.Item[I].Left);
  end;
end;

Um die Bandbreite zu optimieren, benennt man die Knoten lediglich anders. Lisa heißt jetzt Petra und Petra Lisa. Damit ergibt sich eine andere Indexliste und eine andere Bandbreite. Man tauscht z.B. die Namen der Knoten von 1 und 5. Damit geht Stab 1 nicht mehr von Knoten 1 nach Knoten 2 sondern von Knoten 5 nach Knoten 2. Mit dieser Knotenbenennung durchläuft man den Algo nochmals. Gesucht ist die Knotenbenennung, die die kleinste Bandbreite ergibt.

[BUG]

Wenn ich das richtig verstanden habe, ist das Aufbauen der Indexliste (=> Permutation) quasi das Sortieren der Elemente/Knoten so dass die Bandbreite minimal wird?