问一个删除元素的问题，要求要求速度快

[lozzow]

• 有如下一个矩阵，表示 ABCDEFG 这 7 个元素的两两关系（只写了下半部分，是对称的），现在要求删除其中关系值大于 0.5 的数据，使之留下的元素之间的两两关系值都小于 0.5 且元素最多

元素	A	B	C	D	E	F	G
A	1
B	0.3	1
C	0.4	0.2	1
D	0.5	0.1	0.33	1
E	0.7	0.9	0.56	0.2	1
F	0.5	0.4	0.1	0.9	0.9	1
G	0.3	0.2	0.23	0.2	0.7	0.7	1

现在我能想到的就是递归删除，每次删除大于 0.5 个数最多的那一条，但是速度太慢了，我们可能会有好几万一批的数据，得要几个小时，求好兄弟们给个牛逼的解法

[minamike]

多进程？
python 好像递归比 for 循环慢多了

[monster1priest]

先建图，只考虑大于 0.5 的路径。
问题转换为删除最少的节点，使得剩余结点之间相互独立。
也等价于在图中选择最多的互不相邻的结点。
等价于二分图的最大匹配问题。

[ZRS]

删除其中关系值大于 0.5 的数据，使之留下的元素之间的两两关系值都小于 0.5

且元素最多

第二个条件没看明白 第一个条件不就已经规定了删除方式了 怎么还能有元素最多这个约束

你是不是需要求解任务分配问题（ Assignment Problem ）

[lozzow]

@ZRS 比如你删除了元素 G 之后，元素 E 和 F 就少了一个大于 0.5 的关系，这样就只用删除一个元素，当然也可以删除 EF 两个元素，保留一个 G 元素

[edward1987]

你的递归方法不能解决吧。
比如要删除的是 AB,BC,CD,AE,BE,CE
最优解应该是删除 A,B,C 三个元素。 按你的递归会删除 E,A,B,C

[coymail]

根据关系值大于 0.5 的边及其邻接点构造子图；
将子图中大于 0.5 的边的关系值大小统一视为 1 ；
统计每个点的邻接关系值和；
迭代优先删除邻接关系值和最大的点同时更新该点邻接点的关系值和，直到关系值都降为 0 ；

[kimera]

处理思路
- 将原矩阵简化成 0 ，1 （大于等于 0.5 转换为 1 ，小于 0.5 转换为 0 ）
- 构建每个位置 i 的元素和与他相邻的节点放到 nexts 列表中
- 将列表放入大根堆，按照相邻元素从大到小排序
- 依次取出每一个元素 X 删除，并在邻接表中对应元素的 nexts 中删除 X
- 直到队列中的所有元素的 nexts 都变成 0 ，那么这些元素就是完全独立的，输出即可

代码实现 https://raw.githubusercontent.com/rikei/walle/master/walle-study/src/main/java/com/panpan/walle/study/temp/V2exAlg.java

[kimera]

@coymail 咱俩想一块了 哈哈

[edward1987]

@coymail @kimera 你们俩的思路是楼主的优化版吧，但是还是做不到最优解啊= =。

[imn1]

你是要解决问题，还是做算法题？
解决问题的话，扔进 pandas/numpy ，一行 mask 语句搞定
算法的话，我 pass

[ljn917]

https://stackoverflow.com/questions/32419189/remove-minimum-number-of-vertices-to-make-all-the-vertices-isolated

好像和这个一样

[kimera]

@edward1987 矩阵遍历的复杂度就是 O(N^2)了，想不到有啥可以降低复杂度的方法；算了下 10000 个元素，大概要 50s 左右，10w 数量级就要 5000s ，也是需要一个半小时

[wa007]

@monster1priest 后两者是等价的吗？要怎么理解呢？

[wa007]

如二楼，等价于在图中选择最多的互不相邻的结点。
初始成一个节点为根节点的有向图，深度优先遍历，动态规划，dp[point][status] 表示根节点为 point 、节点 point 的状态为 status 的子图中存在的最多互不相邻的节点数量。status 表示状态，只有两种取值，是否丢弃。空间复杂度 N*2 ，时间复杂度 N 。

[wa007]

@wa007 根据子节点的取值可以获取状态转移方程，获得父节点的取值

[vance123]

转化成 01 规划问题，丢给求解器试试

[vance123]

又找了会资料，这就是个 NP-hard 的顶点覆盖问题。用最少的点去所有覆盖大于 0.5 的边

[akira]

根据 2l 的提示，去看了下二分图的最大匹配问题 ，应该是可以满足需求的

[monster1priest]

@wa007 图论相关的结论，二分图的最大独立点个数=点的个数—最小点覆盖数，而最小点覆盖数又等于最大匹配数，具体证明过程我也没了解过。

[lozzow]

@imn1 哈哈哈解决问题