矩阵问题

gushuheng

矩阵运算建模问题：

假设任意一个  Matrix = N * N 的二维矩阵，只有 0， 1。
三个单独的子问题，试图从中寻找出一个 子矩阵  （以下问题均需要利用并行计算，或者利用整体矩阵运算-NPU/TPU/GPU，目的是使时间复杂度不随N增大而增大）
1) 寻找一个子矩阵 Matrix' , 使得 Matrix' 的每个行，或者列 最多只有一个 1   （只需要寻找一个，无需穷尽）
2) 寻找一个子矩阵 Matrix'', 使得 满足条件 1) 的 Matrix' 中 1 的个数最多


问题 1,2按优先级，最高优先级 先解决1,然后2


补充内容 (2020-2-5 08:40):
[
0 1 0 1 0 0
1 0 0 1 1 0
0 0 0 1 1 1
1 1 0 0 0 1
0 1 1 1 0 0
1 0 1 1 1 0
]
那么满足条件1 2的子矩阵为 （满足的矩阵其中之一）：
[
0 1 0 0 0 0
1 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 1
...

aimisiyou

单位矩阵不就是么？

gushuheng

aimisiyou 发表于 2020-2-4 22:39
单位矩阵不就是么？

单位矩阵是一个特例，也就是说 单位矩阵满足条件1,2的子矩阵也是单位矩阵。

假设N=6, 有如下矩阵。
[
0,1,0,1,0,0,
1,0,0,1,1,0,
0,0,0,1,1,1,
1,1,0,0,0,1,
0,1,1,1,0,0,
1,0,1,1,1,0,
]

那么满足条件1,2的子矩阵为 （满足的矩阵其中之一）：
[
0,1,0,0,0,0,
1,0,0,0,0,0,
0,0,0,1,0,0,
0,0,0,0,0,1,
0,0,1,0,0,0,
0,0,0,0,1,0,
]

mathe

根据你给的例子，这是指派问题。但是这个不叫子矩阵

gushuheng

mathe 发表于 2020-2-5 09:17
根据你给的例子，这是指派问题。但是这个不叫子矩阵

对，是指派问题，能用矩阵方式求解吗？ 因为 TPU/NPU/GPU  求解矩阵比较方便

aimisiyou

我刚好正在尝试用列表解决指派问题，采用匈牙利算法。用01矩阵方法我也想过，但要先要构造n！个01矩阵（满足每行每列只有1个0），弊端是构造麻烦且效率低（n较大时不敢想象）。

gushuheng

aimisiyou 发表于 2020-2-5 12:41
我刚好正在尝试用列表解决指派问题，采用匈牙利算法。用01矩阵方法我也想过，但要先要构造n！个01矩阵（满 ...

你说的对，O(n2)复杂度。

aimisiyou

gushuheng 发表于 2020-2-5 08:36
单位矩阵是一个特例，也就是说 单位矩阵满足条件1,2的子矩阵也是单位矩阵。

假设N=6, 有如下矩阵。
...

想到一个办法来解决这个问题，但不知是否存在反例。