[Dynamische Programmierung] Größtes Rechteck in einer booleschen Matrix ermitteln

    • C#
    • .NET (FX) 4.5–4.8

    Es gibt 4 Antworten in diesem Thema. Der letzte Beitrag () ist von φConst.

      [Dynamische Programmierung] Größtes Rechteck in einer booleschen Matrix ermitteln

      -1-

      Gegeben sei folgende boolesche Matrix

      1 1 1 0 0 0 1 1 1
      0 0 1 1 1 1 0 0 0
      1 0 1 1 1 1 0 1 0
      1 0 1 1 1 1 0 0 1
      0 0 1 1 1 1 0 0 1
      0 0 0 0 0 0 0 0 0


      Ziel ist es, dasjenige Rechteck bestehend aus Einsen zu finden, das die größte Fläche hat, in unserem Beispiel also


      1 1 1 0 0 0 1 1 1
      0 0 1 1 1 1 0 0 0
      1 0 1 1 1 1 0 1 0
      1 0 1 1 1 1 0 0 1
      0 0 1 1 1 1 0 0 1
      0 0 0 0 0 0 0 0 0


      Jede Zeile der Matrix wird als Bitset behandelt.

      Der Algorithmus lautet dann:

      Iteriere durch jede Zeile, zähle pro Zeile alle zusammenhängenden Einsen,
      also exemplarisch Zeile 1:
      0 0 1 1 1 1 0 0 0 wären das genau 4 Einsen.

      Ist die Anzahl der zusammenhängenden Einsen der jeweiligen Zeile größer als das Maximum, dann setze Maximum = Anzahl Einsen der Zeile i).

      Um das größte Rechteck zu ermitteln, müssen alle möglichen Variationen ab der i-ten Zeile gebildet werden.
      Die nächste Zeilen-Variation wird durch Anwendung des boolschen &-Operators auf die i-te und (i+1)-te Zeile gebildet, also

      Quellcode

      1. CurrentBitsetLine = Matrix[i] & Matrix[i + 1],


      Dann wird erneut die Anzahl der zusammenhängenden Einsen berechnet. Ist dieser größer als das Maximum, dann setze Maximum = Anzahl zusammenhängender Einsen der Zeile (Matrix UND Matrix[i + 1])..
      dies wird fortgesetzt bis alle Zeilen ( 0 <= i < N ) mit allen Zeilen ( i <= j < N ) über das booleschen UND verknüpft, die Anzahl zusammenhängender Einsen gezählt und der Maximumwert gegebenenfalls aktualisiert wird.


      Bitset.cs:

      Spoiler anzeigen

      C#-Quellcode

      1. public class Bitset
      2. {
      3. private int[] mBits;
      4. public int BitsetSize { get; private set; }
      5. public int this[int n]
      6. {
      7. get
      8. {
      9. int layer = (int)(n / 32.0);
      10. int index = n - (layer * 32);
      11. int mask = 1 << index;
      12. int result = mBits[layer] & mask;
      13. return (result >> index) & 1;
      14. }
      15. set
      16. {
      17. int layer = (int)(n / 32.0);
      18. int index = n - (layer * 32);
      19. mBits[layer] = (mBits[layer] & ~(1 << index)) | ((value % 2)<< index);
      20. }
      21. }
      22. public Bitset(int n)
      23. {
      24. BitsetSize = n;
      25. mBits = new int[(int)Math.Ceiling(n / 32.0)];
      26. }
      27. public Bitset(string bits)
      28. {
      29. BitsetSize = bits.Length;
      30. mBits = new int[(int)Math.Ceiling(BitsetSize / 32.0)];
      31. for (int i = 0; i < BitsetSize; i++)
      32. this[BitsetSize - 1 - i] = bits[i] == '1' ? 1 : 0;
      33. }
      34. public Bitset(Bitset src)
      35. {
      36. this.mBits = new int[src.mBits.Length];
      37. for (int i = 0; i < src.mBits.Length; i++)
      38. this.mBits[i] = src.mBits[i];
      39. this.BitsetSize = src.BitsetSize;
      40. }
      41. public static Bitset operator &(Bitset a, Bitset b)
      42. {
      43. Bitset result = new Bitset(a.BitsetSize);
      44. for (int i = 0; i < result.mBits.Length; i++)
      45. result.mBits[i] = a.mBits[i] & b.mBits[i];
      46. return result;
      47. }
      48. public void Reset()
      49. {
      50. for (int i = 0; i < mBits.Length; i++)
      51. mBits[i] = 0;
      52. }
      53. public override string ToString()
      54. {
      55. StringBuilder sb = new StringBuilder();
      56. for (int i = 0; i < mBits.Length; i++)
      57. {
      58. for (int j = 0; j < BitsetSize; j++)
      59. {
      60. int bit = (mBits[i] >> j) & 1;
      61. sb.Append(bit + " ");
      62. }
      63. }
      64. return new string(sb.ToString().Reverse().ToArray());
      65. }
      66. }



      Dynamics.cs
      Spoiler anzeigen

      C#-Quellcode

      1. public static class Dynamics
      2. {
      3. public struct LRectDescription
      4. {
      5. public int MinRow;
      6. public int MaxRow;
      7. public int MinCol;
      8. public int MaxCol;
      9. public int Size;
      10. public override string ToString()
      11. {
      12. return "[Size = " + Size + " { Min Col = " + MinCol + ", Min Row = " + MinRow + ", Max Col = " + MaxCol + ", Max Row = " + MaxRow + "} ]";
      13. }
      14. }
      15. public static LRectDescription GetLargestRectangleInBooleanMatrix(List<Bitset> booleanMatrix)
      16. {
      17. LRectDescription lRectDescription = new LRectDescription();
      18. Bitset currentLevel = booleanMatrix[0];
      19. int n = currentLevel.BitsetSize;
      20. int locked_col = -1;
      21. int max_col_a = -1;
      22. int max_col_b = -1;
      23. int max_row_a = -1;
      24. int max_row_b = -1;
      25. int max = -1;
      26. for (int level = 0; level < booleanMatrix.Count; level++)
      27. {
      28. currentLevel = booleanMatrix[level];
      29. for (int j = level; j < booleanMatrix.Count; j++)
      30. {
      31. int current = 0;
      32. currentLevel &= booleanMatrix[j];
      33. for (int i = 0; i < n + 1; i++)
      34. {
      35. if (i < n && currentLevel[i] == 1)
      36. {
      37. if (current == 0)
      38. locked_col = i;
      39. current++;
      40. }
      41. else
      42. {
      43. current *= (j - level + 1);
      44. if (current > max)
      45. {
      46. max_col_a = locked_col;
      47. max_col_b = i - 1;
      48. max_row_a = level;
      49. max_row_b = j;
      50. max = current;
      51. }
      52. current = 0;
      53. }
      54. }
      55. }
      56. }
      57. lRectDescription.MinCol = max_col_a;
      58. lRectDescription.MaxCol = max_col_b;
      59. lRectDescription.MinRow = max_row_a;
      60. lRectDescription.MaxRow = max_row_b;
      61. lRectDescription.Size = max;
      62. return lRectDescription;
      63. }
      64. }



      Damit ist es exemplarisch möglich, Voxels optimierter zu rendern: Zusammenhängende Flächen werden einfach durch ein großes Rechteck repräsentiert, statt durch viele kleine.
      Demo-Video:


      (Klicken)

      _
      Und Gott alleine weiß alles am allerbesten und besser.

      Dieser Beitrag wurde bereits 9 mal editiert, zuletzt von „φConst“ ()

      Deine Algo-Erläuterungen sind mir unbestimmt, bzw. scheinen nicht zu passen zur Beschreibung deines Lösungswegs.
      zB was wäre hier das richtige Ergebnis?
      1. 1 1 1 0 0 0 1 1 1
        0 0 1 1 1 1 0 0 0
        1 0 1 1 1 1 0 1 0
        1 0 1 1 1 1 1 0 1
        0 0 1 1 1 1 0 0 1
        0 0 0 0 0 0 0 0 0
        Die "Anzahl zusammenhängender Einsen" ist in Zeile 3 maximal
      2. 1 1 1 0 0 0 1 1 1
        0 0 1 1 1 1 0 0 0
        1 0 1 1 1 1 0 1 0
        1 0 1 0 1 1 1 0 1
        0 0 1 1 1 1 0 0 1
        0 0 0 0 0 0 0 0 0
        Wegen des "Lochs" in #4 gilt das nicht als Rechteck?
      3. 1 1 1 0 0 0 1 1 1
        0 0 1 1 1 1 0 0 0
        0 1 0 1 1 1 1 0 1
        0 1 1 0 1 1 1 1 0
        1 0 1 0 0 1 1 1 1
        0 0 0 0 0 0 0 0 0
        Die "Anzahl zusammenhängender Einsen" ist in Zeilen 2 - 5 immer gleich.


      Also scheint mir eine schwierige Aufgabe, und man braucht zunächstmal eine Test-Anwendung, mit der man schnell verschiedene Eingaben konstruieren kann, durch Augenschein überprüfen, und abspeichern.
      Ich könnte mir auch eine Geschwindigkeits-Optimierung vorstellen, indem ein Turtle-Algo die Ränder von so Einser-Feldern abläuft, und iwelche Ergebnisse daraus auswertet. Aber das ist ganz unausgegoren.

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „ErfinderDesRades“ ()

      Resultat:

      1.)


      2.)


      3.)


      Der Algorithmus sollte eigentlich immer funktionieren. Hab diesen Lösungsweg auf leetcode hochgeladen: Alle Tests' bestanden.

      Wegen des "Lochs" in #4 gilt das nicht als Rechteck?

      Nein.
      _
      Und Gott alleine weiß alles am allerbesten und besser.
      Vermute mal, dass ich zu jenem Zeitpunkt gar nicht wusste, dass es sowas wie einen BitArray im. NET-Framework gibt.
      Meine Implementierung ist sowieso fraglich, schätze ein Boolean-Array und anschließende boolesche Operationen auf die jeweiligen Boolean-Elemente sind vielfach effizienter.

      Ursprünglich war das für meine Voxel-Engine entwickelt worden, ich muss aber zugeben, dass Voxel-Engines offenbar mit
      Raycasting + Sparse-Voxel-Octrees besser zu realisieren sind. Macht einfach mehr Sinn, finde ich.
      _
      Und Gott alleine weiß alles am allerbesten und besser.