[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;
      5. public int BitsetSize { get; private set; }
      7. public int this[int n]
      8. {
      9. get
      10. {
      11. int layer = (int)(n / 32.0);
      12. int index = n - (layer * 32);
      14. int mask = 1 << index;
      15. int result = mBits[layer] & mask;
      17. return (result >> index) & 1;
      19. }
      20. set
      21. {
      22. int layer = (int)(n / 32.0);
      23. int index = n - (layer * 32);
      25. mBits[layer] = (mBits[layer] & ~(1 << index)) | ((value % 2)<< index);
      26. }
      27. }
      29. public Bitset(int n)
      30. {
      31. BitsetSize = n;
      33. mBits = new int[(int)Math.Ceiling(n / 32.0)];
      34. }
      36. public Bitset(string bits)
      37. {
      38. BitsetSize = bits.Length;
      39. mBits = new int[(int)Math.Ceiling(BitsetSize / 32.0)];
      41. for (int i = 0; i < BitsetSize; i++)
      42. this[BitsetSize - 1 - i] = bits[i] == '1' ? 1 : 0;
      44. }
      46. public Bitset(Bitset src)
      47. {
      48. this.mBits = new int[src.mBits.Length];
      50. for (int i = 0; i < src.mBits.Length; i++)
      51. this.mBits[i] = src.mBits[i];
      53. this.BitsetSize = src.BitsetSize;
      54. }
      56. public static Bitset operator &(Bitset a, Bitset b)
      57. {
      58. Bitset result = new Bitset(a.BitsetSize);
      60. for (int i = 0; i < result.mBits.Length; i++)
      61. result.mBits[i] = a.mBits[i] & b.mBits[i];
      63. return result;
      64. }
      66. public void Reset()
      67. {
      68. for (int i = 0; i < mBits.Length; i++)
      69. mBits[i] = 0;
      71. }
      73. public override string ToString()
      74. {
      75. StringBuilder sb = new StringBuilder();
      77. for (int i = 0; i < mBits.Length; i++)
      78. {
      79. for (int j = 0; j < BitsetSize; j++)
      80. {
      81. int bit = (mBits[i] >> j) & 1;
      82. sb.Append(bit + " ");
      83. }
      84. }
      86. return new string(sb.ToString().Reverse().ToArray());
      87. }
      88. }



      Dynamics.cs
      Spoiler anzeigen

      C#-Quellcode

      1. public static class Dynamics
      2. {
      4. public struct LRectDescription
      5. {
      6. public int MinRow;
      7. public int MaxRow;
      9. public int MinCol;
      10. public int MaxCol;
      12. public int Size;
      14. public override string ToString()
      15. {
      16. return "[Size = " + Size + " { Min Col = " + MinCol + ", Min Row = " + MinRow + ", Max Col = " + MaxCol + ", Max Row = " + MaxRow + "} ]";
      17. }
      18. }
      20. public static LRectDescription GetLargestRectangleInBooleanMatrix(List<Bitset> booleanMatrix)
      21. {
      22. LRectDescription lRectDescription = new LRectDescription();
      24. Bitset currentLevel = booleanMatrix[0];
      25. int n = currentLevel.BitsetSize;
      27. int locked_col = -1;
      29. int max_col_a = -1;
      30. int max_col_b = -1;
      32. int max_row_a = -1;
      33. int max_row_b = -1;
      35. int max = -1;
      37. for (int level = 0; level < booleanMatrix.Count; level++)
      38. {
      39. currentLevel = booleanMatrix[level];
      40. for (int j = level; j < booleanMatrix.Count; j++)
      41. {
      43. int current = 0;
      44. currentLevel &= booleanMatrix[j];
      46. for (int i = 0; i < n + 1; i++)
      47. {
      48. if (i < n && currentLevel[i] == 1)
      49. {
      50. if (current == 0)
      51. locked_col = i;
      52. current++;
      53. }
      54. else
      55. {
      56. current *= (j - level + 1);
      57. if (current > max)
      58. {
      59. max_col_a = locked_col;
      60. max_col_b = i - 1;
      62. max_row_a = level;
      63. max_row_b = j;
      65. max = current;
      66. }
      67. current = 0;
      68. }
      70. }
      71. }
      72. }
      74. lRectDescription.MinCol = max_col_a;
      75. lRectDescription.MaxCol = max_col_b;
      77. lRectDescription.MinRow = max_row_a;
      78. lRectDescription.MaxRow = max_row_b;
      80. lRectDescription.Size = max;
      82. return lRectDescription;
      83. }
      85. }



      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.