矩阵问题
矩阵运算建模问题：假设任意一个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 发表于 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 发表于 2020-2-5 09:17
根据你给的例子，这是指派问题。但是这个不叫子矩阵
对，是指派问题，能用矩阵方式求解吗？ 因为 TPU/NPU/GPU求解矩阵比较方便 我刚好正在尝试用列表解决指派问题，采用匈牙利算法。用01矩阵方法我也想过，但要先要构造n！个01矩阵（满足每行每列只有1个0），弊端是构造麻烦且效率低（n较大时不敢想象）。 aimisiyou 发表于 2020-2-5 12:41
我刚好正在尝试用列表解决指派问题，采用匈牙利算法。用01矩阵方法我也想过，但要先要构造n！个01矩阵（满 ...
你说的对，O(n2)复杂度。 gushuheng 发表于 2020-2-5 08:36
单位矩阵是一个特例，也就是说 单位矩阵满足条件1,2的子矩阵也是单位矩阵。
假设N=6, 有如下矩阵。
...
想到一个办法来解决这个问题，但不知是否存在反例。
页:
[1]