最小集集合覆盖问题。
给定M行数，所以数都在0~N-1之间，每行不同的4个数，要求从0~N-1中挑选k个数，使得完全包含这k个数的行尽量多。比如下面的测试数据，所以数据都在0~105之间，共465行。
请问从0～105中挑选20个数，最多可以有多少行，使得它们的4个数都被挑中？
请设计一个有效的算法进行计算。
(附件中内容即下面的465*4表格）
0 1 4 105
0 22086
0 31985
0 54954
0 65053
0 73868
0 83767
0 93071
0102972
0113957
0124058
01797 100
0189899
0319294
0329193
0477890
0487789
0597383
0607484
0617682
0627581
1 53668
1 63567
1 71683
1 81584
1172563
1182664
1213355
1223456
1239299
12491 100
1313843
1323744
14169 103
14270 104
1537388
1547487
1576590
1586689
1597780
1607879
2 43274
2 53764
2 72277
2112371
2132867
2143560
2163658
21789 104
2182962
2214045
2259097
23183 100
23382 101
2417993
2437891
2468087
24763 102
2506698
2547385
2566892
3 43173
3 63863
3 82178
3122472
3133659
3142768
3153557
3173061
31890 103
3223946
3268998
3328499
33481 102
3428094
3447792
3457988
34864 101
3496597
3537486
3556791
4 51879
4 61780
4 92968
4103067
4113558
4123657
4134250
4144149
4152666
4162565
42189 100
4229099
4457291
4467192
45161 101
45262 102
5 796 103
5 91575
51393 101
5143158
5193055
5202359
5252751
5338390
54657 104
5506394
5527882
5606287
6 895 104
6101676
6133257
61494 102
6192460
6202956
6262852
6348489
64558 103
6496493
6517781
6596188
7 91970
7104247
7203053
7262749
7338193
73469 105
74165 101
7437585
7446499
7586288
8 94148
8102069
8192954
8252850
83370 105
8348294
84266 102
84363 100
8447686
8576187
9112163
91287 104
9131865
9173445
9268691
9288590
9327798
93672 100
9466099
9516294
9526984
9567379
9616780
101188 103
10122264
10141766
10183346
10258592
10278689
10317897
10357199
104559 100
10517083
10526193
10557480
10626879
11132461
111487 101
11153846
111884 100
11203741
112775 102
11297699
11526092
11536981
11557277
121388 102
12142362
12163745
12178399
12193842
122876 101
123075 100
12515991
12547082
12567178
13153152
13168797
13192651
132278 104
13252944
13273538
13397984
13407289
13416395
13477381
13546483
14158898
14163251
14202552
142177 103
14263043
14283637
14397190
14408083
14426496
14487482
14536384
15182847
15192549
152076 105
15223640
152480 101
15328289
15336997
15377194
154262 100
15436492
15506783
15607072
16172748
161975 105
16202650
16213539
162379 102
16318190
16347098
16387293
16416199
16446391
16496884
16596971
17207998
172865 105
17356991
17366795
17377784
17397881
174353 101
17476286
17496085
17527076
18198097
182766 105
18356896
18367092
18387883
18407782
184454 102
18486185
18505986
18516975
19222741
19327888
19347983
19367387
19435893
19447182
19506581
19525689
19596276
1998 101 103
20212842
20317787
20338084
20357488
20437281
20445794
20496682
20515590
20606175
2097 102 104
21248385
21267594
21316898
21386792
21447479
21466186
21475491
21566282
21586471
22238486
22257693
22326797
22376891
22437380
22456285
22485392
22556181
22576372
23287589
23307491
23346396
23386988
233949 105
23406687
23425597
23436090
23455494
23526480
24277690
24297392
24336495
24377087
24396588
244050 105
24415698
24445989
24465393
24516379
253062 104
253460 100
25387582
253947 103
25417477
25485784
25536871
25586173
262961 103
26335999
26377681
264048 104
26427378
26475883
26546772
26576274
273261 100
27395696
27426979
27467074
27536472
27555778
279398 104
28316299
28405595
28417080
28456973
28546371
28565877
289497 103
293157 102
29336787
29347880
29357084
29387481
29415296
29435589
29464891
29476082
299395 105
303258 101
30337779
30346888
30366983
30377382
30425195
30445690
30454792
30485981
309496 105
313349 104
31356386
31376189
314046 101
31476474
323450 103
32366485
32386290
323945 102
32486373
33355298
33367476
33416675
33425685
33435188
339296 102
34357375
34365197
34415586
34426576
34445287
349195 101
354044 100
35415089
35496272
359094 104
36394399
36424990
36506171
368993 103
37396972
37404398
37464983
37525575
38394497
38407071
38455084
38515676
39525968
40516067
41434583
41465178
4173 104 105
42444684
42455277
4274 103 105
43466265
43485670
43505469
44456166
44475569
44495370
458189 105
45868799
468290 105
468588 100
47495759
478488 101
48505860
488387 102
49779599
49888991
507896 100
50879092
517196 104
51809399
527295 103
527994 100
5367 100 104
537785 105
538090 102
53829196
546899 103
547886 105
547989 101
54819295
558287 100
55848596
56818899
56838695
57739197
57828595
58749298
58818696
59749495
59759096
59828498
60739396
60768995
60818397
616392 105
626491 105
63669397
637580 103
64659498
647679 104
657086 100
65728796
657577 104
65808589
66698599
66718895
667678 103
66798690
另外再来一个测试集
0 74749
0 81470
0111265
0173741
0227290
0247882
0272838
0313334
0396373
0425785
0435589
0466080
0485879
0525481
1 64648
1 91569
1101366
1163640
1237189
1257781
1262939
1303235
1386474
1425690
1435886
1475979
1495780
1525382
2 43158
2 64349
2 83651
2102157
2152752
2168486
2187987
2227385
2326778
2347274
2356677
2386283
2406368
2486170
3 53057
3 74248
3 93750
3112058
3142652
3178385
3198088
3237486
3336877
3346578
3357173
3396184
3416467
3496269
4 61467
4 83948
4133349
4172944
4182747
4193440
4217185
4226588
4247677
4267378
4365787
4376086
4505380
4515964
5 71568
5 93849
5123248
5162845
5183541
5192646
5207286
5236687
5257578
5277477
5365985
5375888
5506063
5515479
6123447
6187786
6206489
6212740
6232541
6263135
6327072
6336290
6386179
6426076
6515865
7133546
7197885
7202641
7216390
7222440
7273034
7326189
7336971
7396280
7435975
7505766
8167188
8193138
8207377
8237278
8296874
8306376
8355790
8426266
8435483
8475381
9177287
9183039
9217478
9227177
9286773
9316475
9345889
9425384
9436165
9465482
10143538
10157587
10257071
10306567
10335984
10395290
10405579
10415486
10485374
10495082
11147688
11153439
11246972
11316668
11326083
11385289
11405385
11415680
11485181
11495473
12166980
12226870
12255890
12286279
12366163
12395088
12535560
13177079
13236769
13245789
13296180
13376264
13385187
13545659
14162139
14196381
14202430
14236185
14285783
14326273
14345487
14366066
14405671
14455177
15172038
15186482
15212531
15226286
15295884
15336174
15355388
15375965
15415572
15445078
16192035
16256276
16275583
16315972
16375666
16445761
16475068
17182134
17246175
17265684
17306071
17365565
17455862
17465167
18206178
18255683
18285971
18385469
18404684
19216277
19245584
19296072
19395370
19414783
20256068
20275966
20315569
20365071
20374087
20475462
21245967
21266065
21305670
21364188
21375172
21465361
22294887
22325564
22385067
22414675
23284988
23335663
23395168
23404776
24275864
24284886
24354583
25265763
25294985
25344484
26404572
26424464
27414471
27434563
28304385
28335265
28364274
28373981
29314286
29325266
29363882
29374373
30334580
30425061
30445258
30728889
31324479
31435162
31455257
31718790
32435356
32768487
33425455
33758388
34364564
34375261
35365262
35374463
36737986
37748085
38404860
39414959
40677788
40708283
40758081
41687887
41698184
41767982
42464952
42737582
43474852
43747681
44608890
44677683
45598789
45687584
46647090
47636989
48637780
48647383
48667284
49637484
49647879
49657183
50598386
50646585
51608485
51636686
53626789
53666973
54616890
54657074
57597081
57627475
58606982
58617376 按出现概率大小排序，选取靠前的K位么？ aimisiyou 发表于 2022-10-23 19:18
按出现概率大小排序，选取靠前的K位么？
这个可以参考，但理论上不可行。看看双色球出号就明白了 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 看来这种方法找到较优秀解也比较困难。
这个问题和果树问题讨论相关。
由于考虑到在那个问题的计算中，我们发现实数域和有限域的解经常是相同的，所以可以考虑是否可以在有限域里先找到较优秀的解。
另外由于每条直线和四次曲线最多有4个交点，我们可以查看是否能够先选择一条四次曲线，找出它在有限域中和所有直线的相交情况，仅留下有四个不同交点的直线，然后再在这些直线中选择合适的点和直线。
比如一楼的数据选择的是101阶有限域上的曲线$y^2=x^4-6x^3+3x^2+10$
二楼选择的是101阶有限域上的曲线$y^2=x^4-6x^3-7x^2+11x+13$
随机法找近优解，也要看运气吧。 由于我们很难找到有效的算法从一大批点中选择数十个点包含尽量多的合法曲线，我们可以改为考虑直接选择比较小的素数域中四次曲线，然后找出这个有限域中所有和这条曲线有四个交点的直线。
对于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/selectedTopics/blob/master/content/attached/files/ft5.11.outs
比如上面链接中有23个数26行以及24个数36行的结果。（和11阶素数域中两条二次曲线相交的直线)
但是再次用更大数域筛选上面的数据，去除不符合的数据，淘汰后留下的数据就不怎么好了
https://github.com/emathgroup/selectedTopics/blob/master/content/attached/files/ft5.11.outs.flt
23个数和24个数都最多只能24行。
计算结果表明虽然两条二次曲线产生的初始结果的确会有更多"直线"数目更多的解,但是大部分不是实数域范围内的解。 我想到了超图这种 数据结构，如果看成是k-匀齐线性无圈超图，应该能找到相关的定理 主要缺乏的是平面上直线关系的约束
页:
[1]
2