最小集集合覆盖问题。

mathe · 发表于 2022-10-22 10:57:11

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

您需要登录才可以下载或查看，没有账号？欢迎注册

×

给定M行数，所以数都在0~N-1之间，每行不同的4个数，要求从0~N-1中挑选k个数，使得完全包含这k个数的行尽量多。
比如下面的测试数据，所以数据都在0~105之间，共465行。
请问从0～105中挑选20个数，最多可以有多少行，使得它们的4个数都被挑中？
请设计一个有效的算法进行计算。

ft.out (7.72 KB, 下载次数: 0) (附件中内容即下面的465*4表格）

0 1 4 105
0 2 20 86
0 3 19 85
0 5 49 54
0 6 50 53
0 7 38 68
0 8 37 67
0 9 30 71
0 10 29 72
0 11 39 57
0 12 40 58
0 17 97 100
0 18 98 99
0 31 92 94
0 32 91 93
0 47 78 90
0 48 77 89
0 59 73 83
0 60 74 84
0 61 76 82
0 62 75 81
1 5 36 68
1 6 35 67
1 7 16 83
1 8 15 84
1 17 25 63
1 18 26 64
1 21 33 55
1 22 34 56
1 23 92 99
1 24 91 100
1 31 38 43
1 32 37 44
1 41 69 103
1 42 70 104
1 53 73 88
1 54 74 87
1 57 65 90
1 58 66 89
1 59 77 80
1 60 78 79
2 4 32 74
2 5 37 64
2 7 22 77
2 11 23 71
2 13 28 67
2 14 35 60
2 16 36 58
2 17 89 104
2 18 29 62
2 21 40 45
2 25 90 97
2 31 83 100
2 33 82 101
2 41 79 93
2 43 78 91
2 46 80 87
2 47 63 102
2 50 66 98
2 54 73 85
2 56 68 92
3 4 31 73
3 6 38 63
3 8 21 78
3 12 24 72
3 13 36 59
3 14 27 68
3 15 35 57
3 17 30 61
3 18 90 103
3 22 39 46
3 26 89 98
3 32 84 99
3 34 81 102
3 42 80 94
3 44 77 92
3 45 79 88
3 48 64 101
3 49 65 97
3 53 74 86
3 55 67 91
4 5 18 79
4 6 17 80
4 9 29 68
4 10 30 67
4 11 35 58
4 12 36 57
4 13 42 50
4 14 41 49
4 15 26 66
4 16 25 65
4 21 89 100
4 22 90 99
4 45 72 91
4 46 71 92
4 51 61 101
4 52 62 102
5 7 96 103
5 9 15 75
5 13 93 101
5 14 31 58
5 19 30 55
5 20 23 59
5 25 27 51
5 33 83 90
5 46 57 104
5 50 63 94
5 52 78 82
5 60 62 87
6 8 95 104
6 10 16 76
6 13 32 57
6 14 94 102
6 19 24 60
6 20 29 56
6 26 28 52
6 34 84 89
6 45 58 103
6 49 64 93
6 51 77 81
6 59 61 88
7 9 19 70
7 10 42 47
7 20 30 53
7 26 27 49
7 33 81 93
7 34 69 105
7 41 65 101
7 43 75 85
7 44 64 99
7 58 62 88
8 9 41 48
8 10 20 69
8 19 29 54
8 25 28 50
8 33 70 105
8 34 82 94
8 42 66 102
8 43 63 100
8 44 76 86
8 57 61 87
9 11 21 63
9 12 87 104
9 13 18 65
9 17 34 45
9 26 86 91
9 28 85 90
9 32 77 98
9 36 72 100
9 46 60 99
9 51 62 94
9 52 69 84
9 56 73 79
9 61 67 80
10 11 88 103
10 12 22 64
10 14 17 66
10 18 33 46
10 25 85 92
10 27 86 89
10 31 78 97
10 35 71 99
10 45 59 100
10 51 70 83
10 52 61 93
10 55 74 80
10 62 68 79
11 13 24 61
11 14 87 101
11 15 38 46
11 18 84 100
11 20 37 41
11 27 75 102
11 29 76 99
11 52 60 92
11 53 69 81
11 55 72 77
12 13 88 102
12 14 23 62
12 16 37 45
12 17 83 99
12 19 38 42
12 28 76 101
12 30 75 100
12 51 59 91
12 54 70 82
12 56 71 78
13 15 31 52
13 16 87 97
13 19 26 51
13 22 78 104
13 25 29 44
13 27 35 38
13 39 79 84
13 40 72 89
13 41 63 95
13 47 73 81
13 54 64 83
14 15 88 98
14 16 32 51
14 20 25 52
14 21 77 103
14 26 30 43
14 28 36 37
14 39 71 90
14 40 80 83
14 42 64 96
14 48 74 82
14 53 63 84
15 18 28 47
15 19 25 49
15 20 76 105
15 22 36 40
15 24 80 101
15 32 82 89
15 33 69 97
15 37 71 94
15 42 62 100
15 43 64 92
15 50 67 83
15 60 70 72
16 17 27 48
16 19 75 105
16 20 26 50
16 21 35 39
16 23 79 102
16 31 81 90
16 34 70 98
16 38 72 93
16 41 61 99
16 44 63 91
16 49 68 84
16 59 69 71
17 20 79 98
17 28 65 105
17 35 69 91
17 36 67 95
17 37 77 84
17 39 78 81
17 43 53 101
17 47 62 86
17 49 60 85
17 52 70 76
18 19 80 97
18 27 66 105
18 35 68 96
18 36 70 92
18 38 78 83
18 40 77 82
18 44 54 102
18 48 61 85
18 50 59 86
18 51 69 75
19 22 27 41
19 32 78 88
19 34 79 83
19 36 73 87
19 43 58 93
19 44 71 82
19 50 65 81
19 52 56 89
19 59 62 76
19 98 101 103
20 21 28 42
20 31 77 87
20 33 80 84
20 35 74 88
20 43 72 81
20 44 57 94
20 49 66 82
20 51 55 90
20 60 61 75
20 97 102 104
21 24 83 85
21 26 75 94
21 31 68 98
21 38 67 92
21 44 74 79
21 46 61 86
21 47 54 91
21 56 62 82
21 58 64 71
22 23 84 86
22 25 76 93
22 32 67 97
22 37 68 91
22 43 73 80
22 45 62 85
22 48 53 92
22 55 61 81
22 57 63 72
23 28 75 89
23 30 74 91
23 34 63 96
23 38 69 88
23 39 49 105
23 40 66 87
23 42 55 97
23 43 60 90
23 45 54 94
23 52 64 80
24 27 76 90
24 29 73 92
24 33 64 95
24 37 70 87
24 39 65 88
24 40 50 105
24 41 56 98
24 44 59 89
24 46 53 93
24 51 63 79
25 30 62 104
25 34 60 100
25 38 75 82
25 39 47 103
25 41 74 77
25 48 57 84
25 53 68 71
25 58 61 73
26 29 61 103
26 33 59 99
26 37 76 81
26 40 48 104
26 42 73 78
26 47 58 83
26 54 67 72
26 57 62 74
27 32 61 100
27 39 56 96
27 42 69 79
27 46 70 74
27 53 64 72
27 55 57 78
27 93 98 104
28 31 62 99
28 40 55 95
28 41 70 80
28 45 69 73
28 54 63 71
28 56 58 77
28 94 97 103
29 31 57 102
29 33 67 87
29 34 78 80
29 35 70 84
29 38 74 81
29 41 52 96
29 43 55 89
29 46 48 91
29 47 60 82
29 93 95 105
30 32 58 101
30 33 77 79
30 34 68 88
30 36 69 83
30 37 73 82
30 42 51 95
30 44 56 90
30 45 47 92
30 48 59 81
30 94 96 105
31 33 49 104
31 35 63 86
31 37 61 89
31 40 46 101
31 47 64 74
32 34 50 103
32 36 64 85
32 38 62 90
32 39 45 102
32 48 63 73
33 35 52 98
33 36 74 76
33 41 66 75
33 42 56 85
33 43 51 88
33 92 96 102
34 35 73 75
34 36 51 97
34 41 55 86
34 42 65 76
34 44 52 87
34 91 95 101
35 40 44 100
35 41 50 89
35 49 62 72
35 90 94 104
36 39 43 99
36 42 49 90
36 50 61 71
36 89 93 103
37 39 69 72
37 40 43 98
37 46 49 83
37 52 55 75
38 39 44 97
38 40 70 71
38 45 50 84
38 51 56 76
39 52 59 68
40 51 60 67
41 43 45 83
41 46 51 78
41 73 104 105
42 44 46 84
42 45 52 77
42 74 103 105
43 46 62 65
43 48 56 70
43 50 54 69
44 45 61 66
44 47 55 69
44 49 53 70
45 81 89 105
45 86 87 99
46 82 90 105
46 85 88 100
47 49 57 59
47 84 88 101
48 50 58 60
48 83 87 102
49 77 95 99
49 88 89 91
50 78 96 100
50 87 90 92
51 71 96 104
51 80 93 99
52 72 95 103
52 79 94 100
53 67 100 104
53 77 85 105
53 80 90 102
53 82 91 96
54 68 99 103
54 78 86 105
54 79 89 101
54 81 92 95
55 82 87 100
55 84 85 96
56 81 88 99
56 83 86 95
57 73 91 97
57 82 85 95
58 74 92 98
58 81 86 96
59 74 94 95
59 75 90 96
59 82 84 98
60 73 93 96
60 76 89 95
60 81 83 97
61 63 92 105
62 64 91 105
63 66 93 97
63 75 80 103
64 65 94 98
64 76 79 104
65 70 86 100
65 72 87 96
65 75 77 104
65 80 85 89
66 69 85 99
66 71 88 95
66 76 78 103
66 79 86 90

复制代码

mathe · 发表于 2022-10-22 11:05:25

另外再来一个测试集

0 7 47 49
0 8 14 70
0 11 12 65
0 17 37 41
0 22 72 90
0 24 78 82
0 27 28 38
0 31 33 34
0 39 63 73
0 42 57 85
0 43 55 89
0 46 60 80
0 48 58 79
0 52 54 81
1 6 46 48
1 9 15 69
1 10 13 66
1 16 36 40
1 23 71 89
1 25 77 81
1 26 29 39
1 30 32 35
1 38 64 74
1 42 56 90
1 43 58 86
1 47 59 79
1 49 57 80
1 52 53 82
2 4 31 58
2 6 43 49
2 8 36 51
2 10 21 57
2 15 27 52
2 16 84 86
2 18 79 87
2 22 73 85
2 32 67 78
2 34 72 74
2 35 66 77
2 38 62 83
2 40 63 68
2 48 61 70
3 5 30 57
3 7 42 48
3 9 37 50
3 11 20 58
3 14 26 52
3 17 83 85
3 19 80 88
3 23 74 86
3 33 68 77
3 34 65 78
3 35 71 73
3 39 61 84
3 41 64 67
3 49 62 69
4 6 14 67
4 8 39 48
4 13 33 49
4 17 29 44
4 18 27 47
4 19 34 40
4 21 71 85
4 22 65 88
4 24 76 77
4 26 73 78
4 36 57 87
4 37 60 86
4 50 53 80
4 51 59 64
5 7 15 68
5 9 38 49
5 12 32 48
5 16 28 45
5 18 35 41
5 19 26 46
5 20 72 86
5 23 66 87
5 25 75 78
5 27 74 77
5 36 59 85
5 37 58 88
5 50 60 63
5 51 54 79
6 12 34 47
6 18 77 86
6 20 64 89
6 21 27 40
6 23 25 41
6 26 31 35
6 32 70 72
6 33 62 90
6 38 61 79
6 42 60 76
6 51 58 65
7 13 35 46
7 19 78 85
7 20 26 41
7 21 63 90
7 22 24 40
7 27 30 34
7 32 61 89
7 33 69 71
7 39 62 80
7 43 59 75
7 50 57 66
8 16 71 88
8 19 31 38
8 20 73 77
8 23 72 78
8 29 68 74
8 30 63 76
8 35 57 90
8 42 62 66
8 43 54 83
8 47 53 81
9 17 72 87
9 18 30 39
9 21 74 78
9 22 71 77
9 28 67 73
9 31 64 75
9 34 58 89
9 42 53 84
9 43 61 65
9 46 54 82
10 14 35 38
10 15 75 87
10 25 70 71
10 30 65 67
10 33 59 84
10 39 52 90
10 40 55 79
10 41 54 86
10 48 53 74
10 49 50 82
11 14 76 88
11 15 34 39
11 24 69 72
11 31 66 68
11 32 60 83
11 38 52 89
11 40 53 85
11 41 56 80
11 48 51 81
11 49 54 73
12 16 69 80
12 22 68 70
12 25 58 90
12 28 62 79
12 36 61 63
12 39 50 88
12 53 55 60
13 17 70 79
13 23 67 69
13 24 57 89
13 29 61 80
13 37 62 64
13 38 51 87
13 54 56 59
14 16 21 39
14 19 63 81
14 20 24 30
14 23 61 85
14 28 57 83
14 32 62 73
14 34 54 87
14 36 60 66
14 40 56 71
14 45 51 77
15 17 20 38
15 18 64 82
15 21 25 31
15 22 62 86
15 29 58 84
15 33 61 74
15 35 53 88
15 37 59 65
15 41 55 72
15 44 50 78
16 19 20 35
16 25 62 76
16 27 55 83
16 31 59 72
16 37 56 66
16 44 57 61
16 47 50 68
17 18 21 34
17 24 61 75
17 26 56 84
17 30 60 71
17 36 55 65
17 45 58 62
17 46 51 67
18 20 61 78
18 25 56 83
18 28 59 71
18 38 54 69
18 40 46 84
19 21 62 77
19 24 55 84
19 29 60 72
19 39 53 70
19 41 47 83
20 25 60 68
20 27 59 66
20 31 55 69
20 36 50 71
20 37 40 87
20 47 54 62
21 24 59 67
21 26 60 65
21 30 56 70
21 36 41 88
21 37 51 72
21 46 53 61
22 29 48 87
22 32 55 64
22 38 50 67
22 41 46 75
23 28 49 88
23 33 56 63
23 39 51 68
23 40 47 76
24 27 58 64
24 28 48 86
24 35 45 83
25 26 57 63
25 29 49 85
25 34 44 84
26 40 45 72
26 42 44 64
27 41 44 71
27 43 45 63
28 30 43 85
28 33 52 65
28 36 42 74
28 37 39 81
29 31 42 86
29 32 52 66
29 36 38 82
29 37 43 73
30 33 45 80
30 42 50 61
30 44 52 58
30 72 88 89
31 32 44 79
31 43 51 62
31 45 52 57
31 71 87 90
32 43 53 56
32 76 84 87
33 42 54 55
33 75 83 88
34 36 45 64
34 37 52 61
35 36 52 62
35 37 44 63
36 73 79 86
37 74 80 85
38 40 48 60
39 41 49 59
40 67 77 88
40 70 82 83
40 75 80 81
41 68 78 87
41 69 81 84
41 76 79 82
42 46 49 52
42 73 75 82
43 47 48 52
43 74 76 81
44 60 88 90
44 67 76 83
45 59 87 89
45 68 75 84
46 64 70 90
47 63 69 89
48 63 77 80
48 64 73 83
48 66 72 84
49 63 74 84
49 64 78 79
49 65 71 83
50 59 83 86
50 64 65 85
51 60 84 85
51 63 66 86
53 62 67 89
53 66 69 73
54 61 68 90
54 65 70 74
57 59 70 81
57 62 74 75
58 60 69 82
58 61 73 76

复制代码

ft.out (4.94 KB, 下载次数: 1)

aimisiyou · 发表于 2022-10-23 19:18:30

按出现概率大小排序，选取靠前的K位么？

northwolves · 发表于 2022-10-23 22:11:22

aimisiyou 发表于 2022-10-23 19:18
按出现概率大小排序，选取靠前的K位么？

这个可以参考，但理论上不可行。看看双色球出号就明白了

northwolves · 发表于 2022-10-23 22:13:44

mathe 发表于 2022-10-22 11:05
另外再来一个测试集

我用随机选20个的方法，模拟1000次，得到了一组显示12行（平均5-8行）的：

13,34,19,33,29,45,70,38,10,4,21,1,36,52,25,65,54,41,44,17

mathe · 发表于 2022-10-24 08:40:49

看来这种方法找到较优秀解也比较困难。
这个问题和果树问题讨论相关。
由于考虑到在那个问题的计算中，我们发现实数域和有限域的解经常是相同的，所以可以考虑是否可以在有限域里先找到较优秀的解。
另外由于每条直线和四次曲线最多有4个交点，我们可以查看是否能够先选择一条四次曲线，找出它在有限域中和所有直线的相交情况，仅留下有四个不同交点的直线，然后再在这些直线中选择合适的点和直线。
比如一楼的数据选择的是101阶有限域上的曲线$y^2=x^4-6x^3+3x^2+10$
二楼选择的是101阶有限域上的曲线$y^2=x^4-6x^3-7x^2+11x+13$

aimisiyou · 发表于 2022-10-24 10:52:59

随机法找近优解，也要看运气吧。

mathe · 发表于 2022-10-26 19:54:02

由于我们很难找到有效的算法从一大批点中选择数十个点包含尽量多的合法曲线，我们可以改为考虑直接选择比较小的素数域中四次曲线，然后找出这个有限域中所有和这条曲线有四个交点的直线。
对于q阶有限域中非退化三次曲线，其上的点的数目是非常接近q的，通常和q的差值不超过$2\sqrt{q}$.
但是我试验了一下四次曲线，发现上面点的数目可以有比较大的波动。
为了计算方便，在计算中我们选择四次项只有$x^4+cy^4$两项，其中$-c$不是q的二次剩余，从而保证曲线上不存在无穷远点，便于我们计算。
我们可以穷举所有可能的x,y (穷举0~q-1所有组合),找出所有落在曲线上的点，得到了曲线的点集。
然后对于曲线上任意两点不同的$(x_i,y_i), (x_j, y_j)$,我们找出经过两点多直线$y=kx+m$ (或者直线$x=x_i$), 消去y可以得到关于x的四次方程$(1+ck^2)x^4+...=0
$，由于我们选择c不是二次剩余，那么首项系数$1+ck^2$必然不是0，所以可以所有系数乘上它的逆变成一个首一多项式比如$x^4+ux^3+vx^2+...=0$
由于我们已经知道$x_i,x_j$是这个方程的两个根，我们可以知道另外两个根$x_1,x_2$会满足$x_1+x_2+x_i+x_j=-u, x_1^2+x_2^2+x_i^2+x_j^2=u^2-2v$
由此得到$x_1+x_2=-u-x_i-x_j=A, x_1^2+x_2^2=u^2-2v-x_i^2-x_j^2=B$, 然后$2B-A^2=(x_1-x_2)^2$, 所以在$2B-A^2$是q的二次剩余时方程才有解，对应这条直线经过曲线上四个点，我们需要保留；不然直线上只有两个点，我们不予保留。
上面过程中，由于$2B-A^2$如果看成一个随机数，那么它是二次剩余的概率接近$1/2$, 所以我们可以知道对于总共n个点的情况，任意选择两个点确定一条直线可以得到大概$n^2/2$条直线，其中对于$2B-A^2$是平方剩余的只有一半，所以留下了约$n^2/4$种组合，但是对于任意一条过四点多直线，它上面任何两个点都会被计算一次，所以这种方案每条过四点的直线会被计算6次，所以实际上过四点的直线的期望数目大概只有$n^2/24$种（但是由于存在概率性，会有一定波动）。
计算结果也验证了这种方法的确只能找到$n^2/24$左右条直线，比如搜索了很多种不同曲线，有限域的阶比如可以选择11，19，23等，最优情况大概找到20个点有18条过四点的直线，远远没有达到我们以前找到的20棵树可以23行的结果。

于是我又想到我们是否可以考虑在有限域上同时使用两条不同的二次曲线，由于一条直线和每条二次曲线会有两个交点，合在一起也会有四个交点。
而如果假设两条二次曲线在有限域上点的数目比较接近，都约等于n,那么总共有约2n个点。那么从两条曲线上各自选择一个点，连接起来，得到的直线会必然和两条二次曲线均有另外一个合法的点，得到一条过四点的直线。同样，对于一条这样的直线，上面点的选择有四种不同的选择方法，所以每条直线被重复计数4次，我们得到这样的方法大概可以构造出$n^2/4 = (2n)^2/16$条直线。（如果这些点有重合的要淘汰点，但是重复点通常比例不高，可以忽略）。
试着挑选了一些二次曲线做计算的确发现这种方法得到的直线数目挺多的，但是可以发现到现在为止直线数目高的结果不是实数域中合法解，还没有找到特别好的结果。
https://github.com/emathgroup/se ... d/files/ft5.11.outs
比如上面链接中有23个数26行以及24个数36行的结果。（和11阶素数域中两条二次曲线相交的直线)
但是再次用更大数域筛选上面的数据，去除不符合的数据，淘汰后留下的数据就不怎么好了
https://github.com/emathgroup/se ... les/ft5.11.outs.flt
23个数和24个数都最多只能24行。
计算结果表明虽然两条二次曲线产生的初始结果的确会有更多"直线"数目更多的解,但是大部分不是实数域范围内的解。

wayne · 发表于 2022-10-27 06:44:15

我想到了超图这种数据结构，如果看成是k-匀齐线性无圈超图，应该能找到相关的定理

mathe · 发表于 2022-10-27 09:08:03

主要缺乏的是平面上直线关系的约束

账号		自动登录	找回密码
密码			欢迎注册

[擂台] 最小集集合覆盖问题。

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

点评