Ergebnis der Suchanfrage

• Forum: Sonstige Fragen zu Delphi

  AW: Bandbreitenoptimierung für Matrizen

    Delphi
    by BUG, 25. Jun 2015
  Super, freut mich immer wenn Leute algorithmische Probleme lösen wollen und nicht nur Daten hin und her konvertieren :mrgreen:
  Andere Algorithmen haben vielleicht noch bessere Ergebnisse und so richtig toll finde ich den Stil der Implementierung nicht, aber den Einstieg hast du jetzt ja.
• Forum: Sonstige Fragen zu Delphi

  AW: Bandbreitenoptimierung für Matrizen

    Delphi
    by BUG, 25. Jun 2015
  Ich habe leider keine Delphi/Lazarus installiert, kann es also nicht ausprobieren.
  
  Vielleicht kannst du mal die Zwischenergebnisse und Ergebnis für eine (nicht optimale) Beispielmatrix ausgeben, also für jeden Schritt jeweils den aktuell den betrachteten Knoten, dessen Nachbarn (altes Label), usw.
• Forum: Sonstige Fragen zu Delphi

  AW: Bandbreitenoptimierung für Matrizen

    Delphi
    by BUG, 24. Jun 2015
  Ich hab noch mal darüber nachgedacht. Im Prinzip hast du hier ja schon einen Graphen. Die Stäbe sind die Kanten und die Knoten sind ... die Knoten.
  
  Wenn ich dich richtig verstehe, erstellst du daraus die folgende Matrix:
  
  | 1 2 3 4 5
  ------------
  1| - 1 0 0 0
  2| 1 - 0 0 1
  3| 0 0 - 1 1
  4| 0 0 1 - 0
• Forum: Sonstige Fragen zu Delphi

  AW: Bandbreitenoptimierung für Matrizen

    Delphi
    by BUG, 24. Jun 2015
  Auf den ersten Blick: Das Programm testet verschiedene Verfahren zur Bandbreitenreduktion :stupid: :mrgreen:
  
  Zu Cuthill-McKee: Jede symmetrische Matrix entspricht einem Graph, wobei jede Zeile/Spalte einem Knoten entspricht und jeder nicht-null Eintrag einer Kante. Dieser Graph wird in einer günstigeren Datenstruktur gespeichert (Knoten mit Nachbarschaftsliste) um nicht ständig in der Matrix...
• Forum: Sonstige Fragen zu Delphi

  AW: Bandbreitenoptimierung für Matrizen

    Delphi
    by BUG, 23. Jun 2015
  Deswegen habe ich ja Branch and Bound vorgeschlagen, wobei hoffentlich viele Zweige schon für kürzere Listen verworfen werden.
  Kann natürlich sein, dass das immer noch zu viel ist; das kommt auch auf die erste Schranke an.
  
  EDIT: Hui, ich hab mal nach matrix bandwidth minimization gesucht und da gibt es einiges an Material. Einmal tatsächlich Branch&Bound-Verfahren, aber auch vieles anderes....
• Forum: Sonstige Fragen zu Delphi

  AW: Bandbreitenoptimierung für Matrizen

    Delphi
    by BUG, 23. Jun 2015
  Wenn ich das richtig verstanden habe, ist das Aufbauen der Indexliste (=> Permutation) quasi das Sortieren der Elemente/Knoten so dass die Bandbreite minimal wird?
• Forum: Sonstige Fragen zu Delphi

  AW: Bandbreitenoptimierung für Matrizen

    Delphi
    by BUG, 23. Jun 2015
  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...
• Forum: Sonstige Fragen zu Delphi

  AW: Bandbreitenoptimierung für Matrizen

    Delphi
    by BUG, 23. Jun 2015
  Nope :stupid: Vermutlich wäre es auch hilfreich zu wissen, was NB, NV, NU, usw... bedeuten.