最小集集合覆盖问题。

SAY

给定M行数，所以数都在0~N-1之间，每行不同的4个数，要求从0~N-1中挑选k个数，使得完全包含这k个数的行尽量多。
比如下面的测试数据，所以数据都在0~105之间，共465行。
请问从0～105中挑选20个数，最多可以有多少行，使得它们的4个数都被挑中？
请设计一个有效的算法进行计算。
ft.out(7.72 KB, 下载次数: 0)2022-10-22 10:57 上传
点击文件名下载附件

(附件中内容即下面的465*4表格）

1.    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

复制代码

IsacSes

另外再来一个测试集

1.    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)2022-10-22 11:05 上传
点击文件名下载附件

mirakhatun

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

Sherryufas

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

anaboewako

我用随机选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

ivamvanibumiq

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

owobapiakuw

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

ucobiit

由于我们很难找到有效的算法从一大批点中选择数十个点包含尽量多的合法曲线，我们可以改为考虑直接选择比较小的素数域中四次曲线，然后找出这个有限域中所有和这条曲线有四个交点的直线。
对于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行。
计算结果表明虽然两条二次曲线产生的初始结果的确会有更多"直线"数目更多的解,但是大部分不是实数域范围内的解。

dingji

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

iwejinawiciru

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