2.3 碰撞点
如果不知道定义而只能观察其行为,我们无法确定一个变换的一条特定轨道是否无穷,因为它完全可能在任意一点结束或者循环.如果知道一条轨道是有穷的,那就可以用一个算法来确定该轨道的形状了.因此,本章针对轨道的所有算法都有一个有关轨道有穷性的隐含前条件.
显然可以写一个简单而平凡的算法,让它保存已访问的每个元素,在每一步检查新遇到的元素是否曾经访问过.虽然可以用哈希技术来加快搜索,但这个算法至少需要线性的存储空间,而这种要求对于许多实际应用是不能接受的.还好,存在着只需要常量存储空间的算法.
下面的类比有助于理解这一算法.如果有一辆速度快的汽车和一辆速度慢的汽车在一条道路上行驶,当且仅当存在环路时快车将能追上慢车.如果没有环路,快车将比慢车先到达道路的终点.如果有环路,在慢车进入环路之后,快车一定会在环路中追上它.下面我们把这种直观想法从连续域转到离散域,还要小心地避免快车超过慢车.1
这一算法的离散版本基于找到快车遭遇慢车的点.变换f和起始点x确定的碰撞点(collisionpoint)就是那个唯一的y,它使
其中的n.0是满足这一条件的最小整数.这一定义给出了一个用于确定轨道结构的算法,它只需比较较快的迭代和较慢的迭代.如果要处理的是部分变换,那就必须给算法送一个定义空间谓词:
template<typename F, typename P>
requires(Transformation(F) && UnaryPredicate(P) &&
Domain(F) == 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 = x; //slow=f0(x)
1.Knuth[1997,7页]将这一算法归功于RobertW.Floyd.
Domain(F) fast = f(x); //fast=f1(x)
// n ← 0(完成迭代)
while (fast != slow) { //slow=fn(x)∧fast=f2n+1(x)
slow = f(slow); //slow=fn+1(x)∧fast=f2n+1(x)
if (!p(fast)) return fast;
fast = f(fast); //slow=fn+1(x)∧fast=f2n+2(x)
if (!p(fast)) return fast;
fast = f(fast); //slow=fn+1(x)∧fast=f2n+3(x)
// nn + 1
←
}
return fast; //slow=fn(x)∧fast=f2n+1(x)
//后条件:返回终止点或碰撞点的值
}
我们将通过三个步骤来确立collisionpoint算法的正确性:(1)验证f不会被应用于定义空间之外的参数;(2)验证如果它终止,后条件一定满足;以及(3)验证它必定终止.
即使f是部分函数,它在这一过程中的使用也总是良定义的,因为fast的移动受到p调用的保护.而slow的移动不需要保护,这是由于f的规范性:slow和fast在同一轨道上,所以将f应用于slow时总有定义.
算法里的注释说明,如果经过n.0次迭代后fast变得等于slow,那就一定有fast=f2n+1(x)和slow=fn(x).进一步说,n就是满足这一条件的最小整数,因为对每个i如果没有环路,由于有穷性,p将最终返回假.如果有环路,slow最终将到达连接点(环路的第一个点).在程序里的循环语句开始处考虑当slow刚进入环路时从fast到slow的距离d,有0.d下面过程确定一条轨道是否终止:
template<typename F, typename P>
requires(Transformation(F) && UnaryPredicate(P) &&
Domain(F) == 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<typename F>
requires(Transformation(F)) Domain(F) collision point nonterminating orbit(const Domain(F)& x, F f)
{
Domain(F) slow = x; //slow=f0(x)Domain(F) fast = f(x); //fast=f1(x)
// n ← 0(完成迭代)
while (fast != slow) { //slow=fn(x)∧fast=f2n+1(x)slow = f(slow); //slow=fn+1(x)∧fast=f2n+1(x)fast = f(fast); //slow=fn+1(x)∧fast=f2n+2(x)fast = f(fast); //slow=fn+1(x)∧fast=f2n+3(x)
// nn + 1
←
}
return fast; //slow=fn(x)∧fast=f2n+1(x)
//后条件:返回碰撞点的值
}
要想确定环路的结构,即确定轨道的柄规模、连接点和环规模,就需要分析碰撞点的位置.当过程返回碰撞点时
其中n是slow走过的步数,2n+1是fast走过的步数.而且n=h+d这里的h是柄规模,0.d0是fast碰到slow时完成整个环的次数.由于n=h+d,所以2(h+d)+1=h+d+qc
通过化简得到
qc=h+d+1用下式表示h对c取模:h=mc+r其中0.r也就是
d=(q.m)c.r.10.d所以
d=c.r.1而且需要r+1步去完成整个环.这样,从碰撞点到连接点的距离就是e=r+1对环路轨道有h=0且r=0,从碰撞点到轨道开始点的距离是e=1由此可知,环路性质可以用下面过程检查:
template<typename F> requires(Transformation(F)) bool circular nonterminating orbit(const Domain(F)& x, F f)
{
return x == f(collision point nonterminating orbit(x, f));
}
template<typename F, typename P> requires(Transformation(F) && UnaryPredicate(P) && Domain(F) == Domain(P)) bool circular(const Domain(F)& x, F f, P p)
{
//前条件:p(x). f(x)有定义
Domain(F) y = collision point(x, f, p);return p(y) && x == f(y);
}
至此仍不可能知道柄规模h和环规模c.在知道碰撞点之后很容易确定后者,为此只需遍历环路一次并记录步数.要想确定h,先看看碰撞点的位置:
fh+d(x)=fh+c.r.1(x)=fmc+r+c.r.1(x)=f(m+1)c.1(x)
从冲突点走h+1步就到达了点f(m+1)c+h(x),它等于fh(x),因为(m+1)c对应于绕环m+1次.如果同时从x走h步并从碰撞点走h+1步,两者就会在连接点相遇.换句话说,x的轨道和过碰撞点1步的点在恰好h步后汇合,这一情况揭示了下面几个算法:
template<typename F> requires(Transformation(F)) Domain(F) convergent point(Domain(F) x0, Domain(F) x1, F f)
{
// 前条件: (.n ∈ DistanceType(F))n.0∧fn(x0)=fn(x1)
while (x0 != x1) {
x0 = f(x0);x1 = f(x1);
}
return x0;
}
template<typename F>
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<typename F, typename P> requires(Transformation(F) && UnaryPredicate(P) && Domain(F) == Domain(P)) Domain(F) connection point(const Domain(F)& x, F f, P p)
{
//前条件:p(x). f(x)有定义
Domain(F) y = 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.
