《编程原本》一2.3碰撞点

2.3 碰撞点

如果不知道定义而只能观察其行为,我们无法确定一个变换的一条特定轨道是否无穷,因为它完全可能在任意一点结束或者循环.如果知道一条轨道是有穷的,那就可以用一个算法来确定该轨道的形状了.因此,本章针对轨道的所有算法都有一个有关轨道有穷性的隐含前条件.
显然可以写一个简单而平凡的算法,让它保存已访问的每个元素,在每一步检查新遇到的元素是否曾经访问过.虽然可以用哈希技术来加快搜索,但这个算法至少需要线性的存储空间,而这种要求对于许多实际应用是不能接受的.还好,存在着只需要常量存储空间的算法.
下面的类比有助于理解这一算法.如果有一辆速度快的汽车和一辆速度慢的汽车在一条道路上行驶,当且仅当存在环路时快车将能追上慢车.如果没有环路,快车将比慢车先到达道路的终点.如果有环路,在慢车进入环路之后,快车一定会在环路中追上它.下面我们把这种直观想法从连续域转到离散域,还要小心地避免快车超过慢车.1
这一算法的离散版本基于找到快车遭遇慢车的点.变换f和起始点x确定的碰撞点(collisionpoint)就是那个唯一的y,它使

其中的n.0是满足这一条件的最小整数.这一定义给出了一个用于确定轨道结构的算法,它只需比较较快的迭代和较慢的迭代.如果要处理的是部分变换,那就必须给算法送一个定义空间谓词:

template
requires(Transformation(F) && UnaryPredicate(P) &&
Domain(F) &＃61;&＃61; Domain(P))
Domain(F) collision point(const Domain(F)& x, F f, P p)
{
//前条件:p(x). f(x)有定义
if (!p(x)) return x;
Domain(F) slow &＃61; x; //slow&＃61;f0(x)
1.Knuth[1997,7页]将这一算法归功于RobertW.Floyd.
Domain(F) fast &＃61; f(x); //fast&＃61;f1(x)
// n ← 0(完成迭代)
while (fast !&＃61; slow) { //slow&＃61;fn(x)∧fast&＃61;f2n&＃43;1(x)
slow &＃61; f(slow); //slow&＃61;fn&＃43;1(x)∧fast&＃61;f2n&＃43;1(x)
if (!p(fast)) return fast;
fast &＃61; f(fast); //slow&＃61;fn&＃43;1(x)∧fast&＃61;f2n&＃43;2(x)
if (!p(fast)) return fast;
fast &＃61; f(fast); //slow&＃61;fn&＃43;1(x)∧fast&＃61;f2n&＃43;3(x)
// nn &＃43; 1
←
}
return fast; //slow&＃61;fn(x)∧fast&＃61;f2n&＃43;1(x)
//后条件:返回终止点或碰撞点的值
}


我们将通过三个步骤来确立collisionpoint算法的正确性:(1)验证f不会被应用于定义空间之外的参数;(2)验证如果它终止,后条件一定满足;以及(3)验证它必定终止.
即使f是部分函数,它在这一过程中的使用也总是良定义的,因为fast的移动受到p调用的保护.而slow的移动不需要保护,这是由于f的规范性:slow和fast在同一轨道上,所以将f应用于slow时总有定义.
算法里的注释说明,如果经过n.0次迭代后fast变得等于slow,那就一定有fast&＃61;f2n&＃43;1(x)和slow&＃61;fn(x).进一步说,n就是满足这一条件的最小整数,因为对每个i如果没有环路,由于有穷性,p将最终返回假.如果有环路,slow最终将到达连接点(环路的第一个点).在程序里的循环语句开始处考虑当slow刚进入环路时从fast到slow的距离d,有0.d下面过程确定一条轨道是否终止:

template
requires(Transformation(F) && UnaryPredicate(P) &&
Domain(F) &＃61;&＃61; Domain(P)) bool terminating(const Domain(F)& x, F f, P p)
{
//前条件:p(x). f(x)有定义
return !p(collision point(x, f, p));
}


有时我们知道一个变换或者是全的,或者从某个特定开始点出发的轨道是不终止的.对于这种情况,下面特殊版本的collisionpoint会很有用:

template
requires(Transformation(F)) Domain(F) collision point nonterminating orbit(const Domain(F)& x, F f)
{
Domain(F) slow &＃61; x; //slow&＃61;f0(x)Domain(F) fast &＃61; f(x); //fast&＃61;f1(x)
// n ← 0(完成迭代)
while (fast !&＃61; slow) { //slow&＃61;fn(x)∧fast&＃61;f2n&＃43;1(x)slow &＃61; f(slow); //slow&＃61;fn&＃43;1(x)∧fast&＃61;f2n&＃43;1(x)fast &＃61; f(fast); //slow&＃61;fn&＃43;1(x)∧fast&＃61;f2n&＃43;2(x)fast &＃61; f(fast); //slow&＃61;fn&＃43;1(x)∧fast&＃61;f2n&＃43;3(x)
// nn &＃43; 1
←
}
return fast; //slow&＃61;fn(x)∧fast&＃61;f2n&＃43;1(x)
//后条件:返回碰撞点的值
}


要想确定环路的结构,即确定轨道的柄规模、连接点和环规模,就需要分析碰撞点的位置.当过程返回碰撞点时

其中n是slow走过的步数,2n&＃43;1是fast走过的步数.而且n&＃61;h&＃43;d这里的h是柄规模,0.d0是fast碰到slow时完成整个环的次数.由于n&＃61;h&＃43;d,所以2(h&＃43;d)&＃43;1&＃61;h&＃43;d&＃43;qc
通过化简得到
qc&＃61;h&＃43;d&＃43;1用下式表示h对c取模:h&＃61;mc&＃43;r其中0.r也就是
d&＃61;(q.m)c.r.10.d所以
d&＃61;c.r.1而且需要r&＃43;1步去完成整个环.这样,从碰撞点到连接点的距离就是e&＃61;r&＃43;1对环路轨道有h&＃61;0且r&＃61;0,从碰撞点到轨道开始点的距离是e&＃61;1由此可知,环路性质可以用下面过程检查:

template requires(Transformation(F)) bool circular nonterminating orbit(const Domain(F)& x, F f)
{
return x &＃61;&＃61; f(collision point nonterminating orbit(x, f));
}
template requires(Transformation(F) && UnaryPredicate(P) && Domain(F) &＃61;&＃61; Domain(P)) bool circular(const Domain(F)& x, F f, P p)
{
//前条件:p(x). f(x)有定义
Domain(F) y &＃61; collision point(x, f, p);return p(y) && x &＃61;&＃61; f(y);
}


至此仍不可能知道柄规模h和环规模c.在知道碰撞点之后很容易确定后者,为此只需遍历环路一次并记录步数.要想确定h,先看看碰撞点的位置:
fh&＃43;d(x)&＃61;fh&＃43;c.r.1(x)&＃61;fmc&＃43;r&＃43;c.r.1(x)&＃61;f(m&＃43;1)c.1(x)
从冲突点走h&＃43;1步就到达了点f(m&＃43;1)c&＃43;h(x),它等于fh(x),因为(m&＃43;1)c对应于绕环m&＃43;1次.如果同时从x走h步并从碰撞点走h&＃43;1步,两者就会在连接点相遇.换句话说,x的轨道和过碰撞点1步的点在恰好h步后汇合,这一情况揭示了下面几个算法:

template requires(Transformation(F)) Domain(F) convergent point(Domain(F) x0, Domain(F) x1, F f)
{
// 前条件: (.n ∈ DistanceType(F))n.0∧fn(x0)&＃61;fn(x1)
while (x0 !&＃61; x1) { x0 &＃61; f(x0);x1 &＃61; f(x1);
}
return x0;
}
template
requires(Transformation(F)) Domain(F) connection point nonterminating orbit(const Domain(F)& x, F f)
{
return convergent point(x,f(collision point nonterminating orbit(x, f)),f);
}
template requires(Transformation(F) && UnaryPredicate(P) && Domain(F) &＃61;&＃61; Domain(P)) Domain(F) connection point(const Domain(F)& x, F f, P p)
{
//前条件:p(x). f(x)有定义
Domain(F) y &＃61; collision point(x, f, p);if (!p(y)) return y;return convergent point(x, f(y), f);
}


引理2.8如果两个元素的轨道相交,它们将有同样的环路元素.
练习2.2请设计一个算法,对于给定的变换和定义空间谓词,它能确定两个元素的轨道是否相交.
练习2.3convergentpoint的前条件保证它终止.请针对没有该条件,但已知在两点x0和x1的轨道上有共同元素的情况实现算法convergentpointguarded.