如何生成具有特定模式的二进制矩阵？

Question

我有一个大小为 m×n 的二进制矩阵。 下面给出的是一个示例二进制矩阵（实际矩阵要大得多）：

1010001
1011011
1111000
0100100

给定 p = m*n，我有 2^p 种可能的矩阵配置。 我想得到一些满足某些规则的模式。 例如：

1. 我希望第 j 列中不少于 k 个单元格为零
2. 我希望第 i 行单元格值的总和大于给定的数字 Ai
3. 我希望一列中至少有 g 个单元格连续为 1
4. 等等...

如何在不按顺序检查所有 2^p 组合的情况下获得严格满足这些约束的模式？

就我而言，p 可以是像 2400 这样的数字，给出大约 2.96476e+722 种可能的组合。

Answer 1

如果您有足够的约束，则可以尝试探索所有可能的矩阵：

// Explore all possibilities starting at POSITION (0..P-1)
explore(int position)
{
   // Check if one or more constraints can't be verified anymore with
   // all values currently set.
   invalid = ...;
   if (invalid) return;

   // Do we have a solution?
   if (position >= p)
   {
     // print the matrix
     return;
   }   

   // Set one more value and continue exploring
   for (int value=0;value<2;value++)
   { matrix[position] = value; explore(position+1); }
}

如果约束的数量较少，则此方法将花费太多时间。

在这种情况下，对于您作为示例给出的约束类型，模拟退火可能是一个不错的选择解决方案。
您必须设计一个能量函数，当满足所有约束时，该函数为高能量函数。 这将是这样的：

1. 生成一个随机矩阵
2. 计算能量 E0
3. 更改一个单元格
4. 计算能量 E1
5. 如果 E1>E0，或 E0-E1 小于 f（温度），则保留它，否则反转移动
6. 更新温度，然后转到 2除非达到停止标准

Answer 2

如果所有约束都与列相关（如问题中的情况），那么您可以找到所有可能的有效列并检查矩阵中的每一列是否都在该集合中。 （即，当您独立考虑每一列时，您会大大减少可能性的数量。）

Answer 3

我可能离这里很远，但我记得曾经用某种遗传算法做过类似的事情。

Answer 4

查看伪布尔约束（也称为 0-1 整数规划）。

Answer 5

如果您的约束集足够复杂，这实际上是不可能的。 您可以尝试使用随机优化器（例如模拟退火、粒子群优化或遗传算法）来找到可行的解决方案。

但是，如果您可以为此类问题生成一个（非随机）解决方案，那么通常您可以通过对现有解决方案进行随机排列来生成其他解决方案。

Answer 6

生成此类二元矩阵的一种方法是根据给定的约束执行重复的行和列操作，而不是迭代所有 2^p 组合。 作为示例，我将发布一些代码，这些代码将根据上面列出的三个约束生成一个矩阵：

• 每列零的最小数量
• 每行的最小总和
• 每列的最小连续长度

初始化：

第一次开始通过初始化一些参数：

nRows = 10;         % Row size of matrix
nColumns = 10;      % Column size of matrix
minZeroes = 5;      % Constraint 1 (for columns)
minRowSum = 5;      % Constraint 2 (for rows)
minLengthOnes = 3;  % Constraint 3 (for columns)

辅助函数：

接下来，创建几个函数来生成与上面的约束 1 和 3 匹配的列向量：

function vector = make_column
  vector = [false(minZeroes,1); true(nRows-minZeroes,1)];  % Create vector
  [vector,maxLength] = randomize_column(vector);           % Randomize order
  while maxLength < minLengthOnes,      % Loop while constraint 3 is not met
    [vector,maxLength] = randomize_column(vector);         % Randomize order
  end
end

function [vector,maxLength] = randomize_column(vector)
  vector = vector(randperm(nRows));          % Randomize order
  edges = diff([false; vector; false]);      % Find rising and falling edges
  maxLength = max(find(edges == -1)-find(edges == 1));  % Find longest
                                                        % sequence of ones
end

函数 ma​​ke_column 将首先创建一个具有最小数量的逻辑列向量0 个元素，其余元素设置为 1（使用函数 正确和错误）。 该向量将对其元素进行随机重新排序，直到它包含大于或等于所需最小长度的序列。 这是使用randomize_column函数完成的。 使用 RANDPERM 函数对向量进行随机重新排序生成随机索引顺序。 使用 检测序列在 0 和 1 之间切换的边缘DIFF 函数。 然后使用边的索引来查找最长序列的长度（使用 查找和MAX< /a>）。

生成矩阵列：

通过上述两个函数，我们现在可以生成一个至少满足约束 1 和 3 的初始二元矩阵：

binMat = false(nRows,nColumns);  % Initialize matrix
for iColumn = 1:nColumns,
  binMat(:,iColumn) = make_column;  % Create each column
end

满足行和约束：

当然，现在我们必须确保满足约束 2。 我们可以使用 SUM 函数对每一行求和：

rowSum = sum(binMat,2);

如果rowSum的任何元素小于我们想要的最小行总和，我们将不得不调整一些列值来补偿。 您可以通过多种不同的方式来修改列值。 我在这里举一个例子：

while any(rowSum < minRowSum),            % Loop while constraint 2 is not met
  [minValue,rowIndex] = min(rowSum);      % Find row with lowest sum
  zeroIndex = find(~binMat(rowIndex,:));  % Find zeroes in that row
  randIndex = round(1+rand.*(numel(zeroIndex)-1));
  columnIndex = zeroIndex(randIndex);     % Choose a zero at random
  column = binMat(:,columnIndex);
  while ~column(rowIndex),                % Loop until zero changes to one
    column = make_column;                 % Make new column vector
  end
  binMat(:,columnIndex) = column;         % Update binary matrix
  rowSum = sum(binMat,2);                 % Update row sum vector
end

这段代码将循环，直到所有行的总和大于或等于我们想要的最小总和。 首先，使用 MIN. 接下来，找到该行中零的索引，并随机选择其中一个作为要修改的列的索引（columnIndex）。 使用ma​​ke_column，不断生成新的列向量，直到给定行中的 0 变为 1。然后更新二进制矩阵中的该列并计算新的行总和。

摘要：

对于相对较小的 10×10 二进制矩阵以及给定的约束，上述代码通常在不超过几秒钟的时间内完成。 有了更多的限制，事情当然会变得更加复杂。 根据您选择约束的方式，可能没有可能的解决方案（例如，将 minRowSum 设置为 6 将导致上述代码永远收敛到解决方案）。

希望这将为您提供一个起点，开始使用矢量化运算生成您想要的矩阵类型。