《编程原本 》一2.3 碰撞点

简介: 本节书摘来自华章出版社《编程原本 》一书中的第2章,第2.3节,作者(美)斯特潘诺夫(Stepanov, A.),(美)麦克琼斯(McJones, P.),更多章节内容可以访问云栖社区“华章计算机”公众号查看

2.3 碰撞点

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

其中的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)
//后条件:返回碰撞点的值
}

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

其中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.

相关文章
|
9月前
|
PHP 开发者
|
存储 数据采集 算法
库调多了,都忘了最基础的概念-方法篇
库调多了,都忘了最基础的概念-方法篇
105 0
库调多了,都忘了最基础的概念-方法篇
|
设计模式 缓存 前端开发
可否举例说明你在工作中是如何优化前端代码的?
可否举例说明你在工作中是如何优化前端代码的?
162 0
|
算法
【自然框架】重新整理后的自然框架源码!
  整理后的自然框架源码,有九个项目,可以看下面的脑图,带“对号”的表示是一个独立的项目。后面的是主要内容。     欢迎下载http://www.naturefw.com/Down/kind38/List1.aspx ,但是请保留源码里的版权信息,以及dll里的版权信息。
757 0
|
前端开发 大数据 程序员
还在看视频读文档学编程?这有7种编程学习方式,哪种最适合你?
学习编程不仅仅是学会各种语言,你还需要学习如何像程序员一样思考。这里有七种学习编程的方式,视频、文档、听觉、触摸……,你需要找到最适合你的那种。
1834 0
《编程原本 》一2.6 总结
本节书摘来自华章出版社《编程原本 》一书中的第2章,第2.6节,作者(美)斯特潘诺夫(Stepanov, A.),(美)麦克琼斯(McJones, P.),更多章节内容可以访问云栖社区“华章计算机”公众号查看
764 0
《编程原本 》一1.8 总结
本节书摘来自华章出版社《编程原本 》一书中的第1章,第1.8节,作者(美)斯特潘诺夫(Stepanov, A.),(美)麦克琼斯(McJones, P.),更多章节内容可以访问云栖社区“华章计算机”公众号查看
883 0
|
机器学习/深度学习 人工智能 JavaScript
《编程原本 》一3.3 程序变换
本节书摘来自华章出版社《编程原本 》一书中的第3章,第3.3节,作者(美)斯特潘诺夫(Stepanov, A.),(美)麦克琼斯(McJones, P.),更多章节内容可以访问云栖社区“华章计算机”公众号查看
1161 0
|
算法
《编程原本 》一导读
本书是想奉献给那些希望更深入地理解程序设计的人们,无论他们是专职软件开发人员,还是把程序设计看作其专业活动中一个重要组成部分的科学家或工程师.
1023 0