UOJ Logo mcfxmcfx的博客

博客

挑战图同构(大雾)

2021-08-02 18:10:28 By mcfxmcfx

前几天在 EI 群看到 EtaoinWu 在 UOJ 搞了一道编码题 #679. 无标号图编码,感觉很有意思,于是就来做了做。

根据 OEIS,不同的图个数约为 $\frac{2^{n(n-1)/2}}{n!}$,而这个结果也非常的精确。写一下代码可以发现,在 $n=70$ 时,这个估计和实际值的差距已经不超过实际值的 $10^{-16}$。

当 $n=100$ 时,$\frac{2^{n(n-1)/2}}{n!}\approx 1.176\cdot 2^{4425}$。根据信息熵,能编码的 01 串长度最多只能是 4425,而此时分数为 170。

引入

首先考虑把点定一个顺序。一种简单的方法是,把 $0\sim K-1$ 连成独立集,然后 $i+K$ 往前面 $j$ 连边当且仅当 $g_i$ 的第 $j$ 位是 1,其中 $g_i\in[0,2^K)$。 令 $f_i=\sum_j [g_j=i]$,我们需要保证 $f_i\in \{0,1\}$,并且改变 $0\sim K-1$ 的顺序会使得 $f$ 不同(这样才能还原出 $0\sim K-1$ 的顺序)。假设 $f$ 是在程序中预先写死的。 解码时可以先找到独立集,然后根据后面点的连边情况还原整个序列。假设 $K=7$,7 个点形成独立集的概率非常低,而 $f$ 也满足的概率就更低了。

这个做法一共使用了 $\frac{7\cdot 6}2+7\cdot 93=672\text{bits}$ 来区分顺序,剩下还有 $\frac{93\cdot 92}2=4278\text{bits}$ 可以存储实际序列。

算法一

$7$ 实际上也太大了。$7$ 元独立集本身就占用了许多边,而很多数只需要 6bits 确定,不需要 7bits。我们可以让 $K=5$,然后令 $f_i=\sum_j [g_j=i]$,并且移除 $f_i\in \{0,1\}$ 的限制。可以让 $f$ 中存在一个 $f_i=1$,一个 $f_i=2$,并且所有 $f_i\le 8$。$f_i=1$ 的点标号可以唯一确定。设他为 $x$,我们可以用是否向 $x$ 连边区分出 $f_i=2$ 的点。接下来所有点都可以用和这三个点的连边情况来区分了。胡乱实现一个可以得到 93 分

算法二

这种排序方法仍然浪费了大量 bit。他的本质是,用 $n$ 个 bit,可以把大小为 $n$ 的集合分为两个集合。当 $n$ 较大时,这种方法的浪费不大(如 $2\log 10+20-\log 20\approx 2.5\text{bits}$),但是 $n$ 小的时候会造成非常大的浪费(如 $n=2$ 需要 2bits,然而实际信息量只有 1bit)。

假设我们按照前面的方法确定了几个点的标号(把这几个点叫做 $B$,最前面 $K$ 个叫做 $A$),接下来问题的就是,如何更快地把剩下的集合排序。对于 $f_i$ 对应的集合,可以强制要求里面每个点到 $B$ 的连边情况都不同,那么它花掉了 $|B|\cdot|f_i|\text{bits}$,但是可以贡献 $\log\binom{2^{|B|}}{f_i}\text{bits}$。经过计算可以发现,当 $B$ 较大时,净损失几乎就是 $\log f_i!$,也就是几乎没有额外开销。实现上,可以在标程里抄一个 BinomTable

在此基础上,还有一些优化。把每个集合贡献的 $\log\binom{2^{|B|}}{f_i}\text{bits}$ 乘起来,作为一个高精度整数考虑,可以多赚回来一些 bit。把 $K$ 换成 4,可以节省一些 bit。

这些优化全部应用上可以得到 138 分

算法三

刚才的优化始终没有绕开必须有 $f_i=1$ 和 $f_i=2$ 作为 $B$ 的种子这个条件。为了绕开,我们可以要求 $B$ 的内部是一个不对称图(asymmetric graph),这样就可以直接在内部确定编号。

假设 $|B|=8$,8 个点的不对称图有 3696 个。这样净开销就只有 $\frac{8\cdot 7}2-\log\left(3696\cdot 8!\right)=0.85\text{bits}$,非常节省。应用这个可以得到 143 分

算法四

前面的过程一直假设 $f$ 是固定的,而这也损失了大量的信息。如果把 $f$ 变成动态的,$f$ 本身也可以编码大量信息。我当时的实现可以得到 158 分。(但是这代码有个 bug,一直到 170 分的提交才发现并修复,所以应该还可以再得更高一点的分)

算法五

在算法四的基础上,经过调参可以发现,如果放宽了 $f$ 的范围,那么一个图可能会有多种解码方式。假设在这些方式中选择 hash 值最小的。

经过多次调参,发现可以让算法四将 100 个点的图和长为 4427 的 01 序列建立联系,并且约有 30% 的序列编码再解码可以得到自身(实际上上界是 $1.176/4=0.294$,也就是说几乎每个图都可以编码了)。

于是我们可以考虑这个新问题:有一个 $F:[0,2^{4427})\to\{0,1\}$,约 30% 的 $F(x)$ 是 1,并且是随机分布的,需要找一个 $G:[0,2^{4425})\to [0,2^{4427})$,以及 $G^{-1}$,使得 $F(G(x))=1$。

假设我们建了一棵 4425bits 的 trie 树,每个叶节点有 $0\sim 4$ 个 $y$ 满足 $F(y)$ 为 1,有一个需要求 $G$ 的值 $x$。每个节点内部先尽量把 $x$ 和 $y$ 匹配,然后匹配不完的再往父亲丢。

这个 trie 树当然不用实际建出,可以从叶子开始往上一层一层搜索,直到找到匹配位置。

显然最后所有的 $x$ 都能找到匹配,只是时间复杂度可能会爆,感性理解一下可以发现大概有 $\exp(-i)$ 的概率在 $\exp(i)$ 的时间内跑出来。

最后我的实现在题目要求的时限内错误率略高于 2%,多次提交可以得到理论上界 170 分

(这份代码实现上有一些小区别,但是大致思想如此)

碎碎念

看到这题时,我首先想到了之前看到的一道题,大概是把一个长为 100 的串编码到 100 个点的图中,但是他还限制了边数也不超过 100。那题可以用一条链来做,这给了我把点编号的启发。

这题到达了理论上界并不意味着图同构被解决了。假设有两个图 $A,B$,其中 $A$ 是随机图,$B$ 要么和 $A$ 同构,要么是另一个随机图。那么将度数序列排序后比较可以有几乎为 1 的正确率。这题其实就类似这种情况。

这题的对偶版本——将图编码成 01 串,看起来也已经解决了(并且几乎达到了下界)。但是有个大问题:对于 01 串编码的情况,即使串本身不是随机的,也可以随机异或一些东西,把他变随机;但是给你一个精心构造的图,并不能把他变得随机。不过,这其实也并不是问题,因为要是 corner case 都能做,那就直接可以判定图同构了。

评论

EtaoinWu
您太强辣!

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。