下面我来谈谈我的迫真思路。
迫真尺规作图计划~搜索策略(最终版):
1 使用递归进行限制深度的深度优先搜索,遍历一切可能的尺规作图方式,给出一切可能得到的不同的点。
2.以下7种基本操作均视为1步:
2.1.构造两线交点
2.2.构造线与圆的交点
2.3.构造圆与圆的交点
2.4.过两点构造直线
2.5.过一点构造一条线的垂线
2.6.过一点构造一条线的平行线
2.7.以一点为圆心,两点间距离为半径构造圆
3.深度搜索剪枝策略:
3.1.构造点,线,圆时,与当前图上已有的点,线,圆不得重合。
3.2.构造圆时所用的半径长度,或构造线时所用的两点距离,或构造平行线时的点线距离,不得过短。
3.3.构造两图形交点时,在交点上,两图形切线的夹角不得过小。
3.4.限定画布大小,不构造画布外的点。
3.5.如果要构造点,该点必与之前最后一次构造的线或圆有关。否则,可以在构造那线或圆之前就构造该点,将得到重复的局面。
3.6.深度搜索的最后一层仅构造点,因为构造了线或圆也无法为点数做出贡献。
3.7.对每一步递归做出的图进行hash,以kdtree的形式将同层(除最后两层外)所有图形的hash记录下来。每次作图完毕后将新图形的hash与记录比较,若有相同hash的记录,说明是重复局面,不再对该局面进行递归计算。
4.将每次构造的有效点的位置在内存中以kdtree的形式记录下来。每次构造出点,都要与记录进行比较,只有不重复的点是有效的。同时在磁盘中线性记录有效点的尺规作法。kdtree中保存有磁盘记录的编号,以便查找。
5.在一切点对中挑选出迫真点对,即距离与目标超越数相差小于事先给定值的点对。在对点进行排序后,该过程可加速至O(N^(3/2))。
6.首先使用double精度进行递归作图与搜索迫真点对以确保计算速度。然后对迫真数对,从磁盘中读取尺规作法,使用任意精度浮点数进行复盘,并求出精确距离及误差。
7.为了节省内存,由于起始图(仅有两点(-1/2,0), (1/2,0))是有x和y方向的镜像对称性的,故仅记录x>=0和y>=0的有效点,这样可以节省4倍内存。计算迫真点对时,需考虑从每个点(x,y)获得的座标为(x,y), (x,-y), (-x,-y), (-x,y) 的四个点。