数学研发论坛

 找回密码
 欢迎注册
查看: 585|回复: 7

[讨论] 矩阵问题

[复制链接]
发表于 2020-2-4 15:31:10 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
矩阵运算建模问题:

假设任意一个  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
...

评分

参与人数 1金币 +20 收起 理由
gxqcn + 20 首帖奖励,欢迎常来。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-4 22:39:46 | 显示全部楼层
单位矩阵不就是么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-5 08:36:59 | 显示全部楼层
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,
]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-5 09:17:47 来自手机 | 显示全部楼层
根据你给的例子,这是指派问题。但是这个不叫子矩阵
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-5 10:02:32 | 显示全部楼层
mathe 发表于 2020-2-5 09:17
根据你给的例子,这是指派问题。但是这个不叫子矩阵

对,是指派问题,能用矩阵方式求解吗? 因为 TPU/NPU/GPU  求解矩阵比较方便
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-5 12:41:28 | 显示全部楼层
我刚好正在尝试用列表解决指派问题,采用匈牙利算法。用01矩阵方法我也想过,但要先要构造n!个01矩阵(满足每行每列只有1个0),弊端是构造麻烦且效率低(n较大时不敢想象)。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-2-6 10:33:17 | 显示全部楼层
aimisiyou 发表于 2020-2-5 12:41
我刚好正在尝试用列表解决指派问题,采用匈牙利算法。用01矩阵方法我也想过,但要先要构造n!个01矩阵(满 ...

你说的对,O(n2)复杂度。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-2-22 02:54:44 | 显示全部楼层
gushuheng 发表于 2020-2-5 08:36
单位矩阵是一个特例,也就是说 单位矩阵满足条件1,2的子矩阵也是单位矩阵。

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

想到一个办法来解决这个问题,但不知是否存在反例。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-4-8 11:11 , Processed in 0.210485 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表