欢迎光临散文网 会员登陆 & 注册

第 60 讲:自噬

2021-09-15 07:55 作者:SunnieShine  | 我要投稿

不论是不是鱼技巧,在之前的叙述里都有提到过一个词汇:自噬(Cannibalism)。只要和这个术语词沾边的结构,都是可以删除掉结构本身的一部分的情况。

它的英文名Cannibalism的意思是“自相残杀”,所以在术语词里,我们把这个词语翻译为“自我吞噬”,简称“自噬”,暗示“吃掉”自己身上的某一个部分,而这个标题里的英文单词Cannibalistic是原词语的形容词。

在前文的叙述里,我们说过,自噬其实来自于鱼结构。那么下面就我们来看看,自噬到底是怎么回事。

Part 1 自噬鱼的形成

让我们来思考一种结构,既然定义域可以有重叠,那么,删除域有重叠,会如何呢?

如左图所示,这是一个之前介绍到的,全部区域类型都涉及了的交叉鱼结构。不过我们发现,删除域区域r3和c7实际上是拥有重叠的,只是图上画不出来,在r3c7,这个单元格确实属于r3和c7的重叠位置,但是由于它在定义域上,所以我们无法为其图上删除域的颜色。不过,我们现在拓展一下鱼结构,把它当作这个鱼的删数结论。或者换句话说,这里的r3c7(x)实际上也是一个正确的删数,而且它甚至位于定义域上。不过,这得如何证明和说明它呢?

我们通过反证法来说明。假设我们让r3c7 = x,会发生什么情况。首先是r3和c7这两处删除域区域,由于r3c7 = x的关系,r3c3和r7c7此时都不能放x了,于是c3和r7两个区域能放入x的位置此时挤入b7这一个宫里。显然,这样是放不下的,因为只有一个宫,而这个宫却要放下两处x,这是肯定不够放的。所以,原来的假设是错误的,也就是说,即使r3c7含有候选数x,我们也必须删掉它,否则结构就不能正常放下应该拥有的三个x。

我们称r3c7(x)这一处候选数,本身存在于定义域里,但由于填入后必然会出现矛盾导致结构出错的这一类候选数叫做自噬删数(Cannibalistic Elimination);而我们把带有自噬删数的鱼称为自噬鱼(Cannibalistic Fish)。

在早期的文献里,自噬删数也被称为鱼鳍,即称自噬鱼鳍(简称自噬鳍,Cannibalistic Fin)。算作鱼鳍的原因很简单,它确实影响了结构的成立,因为它占据了定义域的一处候选数位置。不过这种影响并不大,因为它的填入就必然导致了矛盾的出现,所以此时就已经应当把它删除掉了。所以它的影响不足以大到像是内鱼鳍和外鱼鳍一般。所以本文档此时不将其算作鱼鳍类别。

另外,自噬删数我们在鱼图里使用“*x”表示,x暗示结构在定义域区域上,表示这个单元格含有这个候选数;而“*”实际上表示的是鱼图的删数。在前面所有鱼图里,我们都没有用“*”表示删数,是因为我们可以通过涂色来说明删数位置,就没有在每一个单元格都写上该符号。而且,书写这个符号过多,就会导致它会和“x”符号混淆不清。

Part 2 原理进一步剖析

从上一个鱼图示例里看到,似乎最开始我们给出“删除域区域交集”的信息点跟删数实际上的关系并不大。所以这仅仅是巧合?实际上并不是。我们再举一个例子来说明这一点。

如图所示,这个结构的定义域为c237,删除域则为r36b4。显然,如果我们忽视r6c23(x)的话,它满足了全覆盖要求,而且区域数也一样,所以删数是肯定成立的。

不过,r6c23(x)的存在,会使得结构怎么样呢?假设我们让r6c2 = x,显然它占据了两处删除域区域r6和b4,以及一处定义域区域c2。那么,我们还需要放置的x的位置全部被挤入到唯一的一处删除域区域r3里了,此时结构出现错误,所以r6c2 <> x;同样地,如果你假设r6c3 = x,照样会这样出错。

对比上一个鱼图示例,和这里的示例,可以看到,它们的删数的推导过程大致相同的地方在于,最后都会使得后续要放的x被挤入到同一个删除域区域里。比如第一个鱼图示例里,可能的x被挤入到b7这个删除域区域之中;而这个示例里,可能的x被挤入到r3这个删除域区域之中。这难免也太巧合了吧,为什么会发生这种现象?

原因是这样的。当我们一旦在删除域区域的交集上放x后,如果这个数在定义域某处上,这个时候它会同时影响到一个定义域区域和两个删除域区域,这是毋庸置疑的,因为它处于删除域区域的交集上,显然影响了两处删除域区域,而它也在定义域区域上,自然也会影响到一个定义域区域。这样一来,它就会使得原本n个定义域区域和n个删除域区域恰好成立的结构立马变为只有(n - 1)个定义域区域和(n - 2)个删除域区域。

接下来的内容会比较绕,希望你能一句一句地分析和理解。(n - 1)个定义域区域保证这个结构还需要填入(n - 1)处x,而删除域保证这些区域里最多只能放下(n - 2)处x,注意,此时是最多能放这么多个x。试想一下,由于原结构是全覆盖的,但现在只剩下最多可以放(n - 2)个x,但定义域又必须规定此时还必须填(n - 1)个,显然(n - 1)是比(n - 2)要大的,这不是矛盾了吗,最多能放的个数居然比必须规定要放的个数还要少,这怎么可能?所以矛盾了。

上述的两则示例,在这个理论里,都表示n = 3时的情况,实际上,当n = 4甚至更高,也都符合这个理论,因为鱼的定义域和删除域的定义是这么规定的:定义域要求每一个区域都恰好填入一个x;而删除域要求每一个区域都最多填入一个x,而我们仅通过这个定义就能得到这个结论,所以它本身就是带有普遍和广泛意义的,跟n数值多少是无关的。当然了,这里的n肯定不能小于2,否则(n - 2)就变为了一个负数,就没有意义了。

所以,我们只需要掌握的是,只要原鱼结构是成立的(满足区域数一样多,以及全覆盖的要求即可),那么删除域一旦存在交集,那么交集处的元素就可以删除,不论它在哪里。

这里就需要你注意一个地方了。如果删除域区域的交集如果不处于定义域上,这显然是可以删的,因为毕竟它在删除域区域上,而且又不受定义域区域填数的限制和影响,本来就可以删除,它这就是一个普通的、平凡的删数;而如果删除域区域的交集在定义域上的话,那么就需要理论的依托才可以删数。所以,实际上它们都是可以删的。只是需要请你注意它们的区别,虽然都是可以删除的,但删数原因不同:一个是普通的删数,而一个是理论支持得到的矛盾而引起的删数。

Part 3 自噬鱼的示例

下面我们来看一些自噬鱼的示例。

3-1 自噬三链列

如图所示,这是一个带有自噬删数的交叉三链列结构。首先我们来分析自噬删数的删数原因。由于它同时位于两个删除域区域和一个定义域区域上,如果贸然让此处填入7,就会使得两个删除域区域r3和c5受到填数影响,一个定义域区域b2受到影响。显然,整个结构需要放置三处7(因为有三个定义域),但由于删除域区域目前只有一个,而定义域区域区域却有两个,删除域使得结构最多只能让结构上再放1个7进去,而定义域却要求结构必须放2个7,这显然冲突了。所以r3c5 <> 7;另外,由于这个数已经删除后,剩余的部分就成了一个普通的交叉三链列结构,所以删数全部都属于正常的删数情况,这里就不用阐述了。

3-2 自噬四链列

接下来来看一些带有自噬删数的四链列结构。

如图所示,我们尝试把c2689作为定义域,而r259b3作为删除域,显然可以看到的是,r2c8位于r2和b3的交集处,而且它确实在定义域区域c8上。如果r2c8 = 8,则定义域区域变为三个,而删除域区域则变为两个。显然,最多只能放2个8和恰好放入3个8的说法是互相矛盾的,所以矛盾。所以,r2c8 <> 3。其它的删数就不用再次作出介绍了,因为都是普通的宫内四链列的基本删数。

如图所示,这一则示例和上面的类型页非常类似,而逻辑也是一样的,就不必作出阐述了。希望你能够独立理解。

3-3 自噬五链列

这一个示例是我个人最喜欢的一个例子了,因为它的删数对于结构的每一处都是可以删掉的,非常整齐。

如图所示,这个结构的定义域为c23569,删除域则是r147b15。可以看到,这样看结构的话,必然b1和r1会有重叠,而b5和r4会有重叠,而重叠的位置也都恰好位于定义域区域上。假设这些重叠的位置但凡有一处填入9,比如r1c2 = 9,则定义域区域少一个,删除域区域数少两个,产生矛盾;其它的候选数也都是如此。

3-4 带鱼鳍的自噬鱼

最后来介绍一个带有其它鱼鳍和自噬删数的鱼结构。

如图所示,这个结构的定义域为r35b567,删除域则是r6c2368。可以发现,定义域区域r5和b6产生了重叠,且重叠处存在候选数,即r5c8(7)。我们不得不把它视为内鱼鳍来看。假设它不存在的话,那么带有自噬删数的鱼结构就成立了,注意,删除域区域r6和c8是有重叠的,r6c8也确实恰好在定义域区域上,所以它被看作自噬删数。

如果内鱼鳍r5c8(7)为假,则这个自噬删数可以删除,原因是会导致定义域区域少一个,删除域区域少两个的矛盾;而其它的删除域区域上的删数也都是可以正常删除掉的。但是内鱼鳍的客观存在,所以最终删数就只能是内鱼鳍能够对应到的位置,即c8这个删除域区域了。

可以看到,此时c8上包含了刚才的自噬删数r6c8(7),那么此时它能否被删除呢?答案自然是肯定的。因为在鱼鳍为假的时候,我们通过了自噬的原理来删掉了它;而当鱼鳍为真的时候,显然它也作为同一区域的其它候选而存在,当然也可以被删掉。所以其实这里的r6c8(7)是可以被删除的。


第 60 讲:自噬的评论 (共 条)

分享到微博请遵守国家法律