章节目录 · 第 2 页
一章一页，已整理的按顺序列在这里。
第五十二节本节介绍用遗传算法求解0-1背包问题的具体实现。基因由7件物品的装入状态（0或1）组成，种群初始化时随机填充基因，不校验是否超重，而是在适应度函数中对非法个体给予惩罚值1……阅读第五十三节本节从作者写的第一个计算器程序因整数溢出和浮点数有效位不足导致计算不准确说起，引出大整数计算的必要性——如天文计算需要极高的精度。阅读第五十四节本节讲解大整数的除法、乘方及常用算法。除法采用试商优化，通过高位组成的64位整数试商并累加，反复减去除数的若干倍，被除数小于除数时即得余数，除法与取模为同一过程……阅读第五十五节扩展欧几里得算法通过递归将方程化简为a%b=0的平凡解，再利用x=y'、y=x'-(a/b)*y'的递推关系反向推出原方程的解。阅读第五十六节米勒-拉宾素性检验算法源于米勒教授基于广义黎曼猜想提出的确定性算法，后经拉宾教授改进为不依赖该假设的随机化算法。阅读第五十七节本节先介绍针对RSA的选择密文攻击：攻击者已知A的公钥和密文，自行选一个r算出Y1，再构造Y2与Y1的乘积求逆元t，然后以验证身份为名骗A对Y2签名，利用签名结果反推出明文X。阅读第五十八节分组解密与填充处理捆绑进行：将密文转为大整数做模幂运算，再转回字节串，依据截断标识（填充随机字节与原始数据之间的0）分离出随机填充，得到原始明文。阅读第五十九节本节介绍数独游戏的规则与计算机求解方法。数独是在9×9的格子中填入1～9，使每行、每列及每个3×3小九宫格内数字不重复，已给出的数字称为提示数。阅读第六十节本节介绍数独求解算法的数学模型与实现。模型将每个单元格定义为统一结构，用fixed标志区分是否已确定数字，未确定时保存候选数集合；整体用81格二维矩阵加已确定计数器表示……阅读第六十一节本节介绍华容道游戏的背景与求解算法原理。华容道取材于关羽义释曹操的三国故事，但游戏本身由美国人Lewis W. Hardy于1909年申请专利……阅读第六十二节本节讲华容道自动求解算法实现中的几个关键问题。棋子移动可用行、列坐标加减1的方向数组统一描述，避免分支判断；广度优先搜索用线性表存棋局，逐个展开直到找到目标或队列为空。阅读第六十三节本节讨论华容道游戏中武将棋子的移动。移动棋子即在棋盘上清除原位置信息、在新位置写入信息，需要武将编号和移动方向两个参数。阅读第六十四节本节介绍Dijkstra算法的实现与A*算法原理。Dijkstra算法维护已确定最短路径的集合S和待处理集合Q，每次从Q中取出距离最小的顶点移入S，并用它松弛相连顶点的距离……阅读第六十五节本节介绍切比雪夫距离：两个向量的切比雪夫距离是各分量差的绝对值中的最大值，二维平面上即两点横纵坐标差的最大值，并给出了对应的A*算法实现代码及其效果。阅读第六十六节本节讨论俄罗斯方块AI评估局面的参数与常用算法。评估一个板块的摆放位置，需考虑接触的小方块数量（越紧密越好）、板块最高点高度（越低越好）、能消除的行数（越多越好）……阅读第六十七节当两个局面的评分相同时，PierreDellacherie算法用优先度决定取舍：板块放在左侧（1～5列）时，优先度等于水平平移次数乘100再加10和旋转次数……阅读第六十八节本节介绍俄罗斯方块AI算法中穷举板块摆放方法的实现。摆放穷举分两步：先遍历板块的每种旋转形态，再对每种形态从游戏区域第0列开始逐个位置尝试。阅读第六十九节本节介绍博弈树搜索的基本方法。由于完整博弈树节点数极其庞大（如围棋可达10^170），实际应用中通常限定搜索深度，到达深度即评估棋局。阅读第七十节置换表是一种以空间换时间的辅助算法，用于提高启发式搜索效率。阅读第七十一节井字棋的估值函数需综合考虑空行数与双连子两个因素：一方在某行、列或斜线上只含己方棋子或空格即算空行，空行越多越可能连成三子……阅读第七十二节本节介绍黑白棋AI中落子判断、估值函数与搜索算法的实现。阅读第七十三节本节首先介绍在黑白棋搜索中应用走法排序启发，依据此前统计的每种走法的好值（即对手行动力的负值）对走法排序，以便更早建立准确的剪枝窗口，提高剪枝效率。阅读第七十四节本节讲五子棋AI的棋型识别、估值与搜索算法。SearchPatterns()遍历四个方向上的所有线，交给AnalysisLine()统一识别：先找连续棋子的起止位置……阅读第七十五节附录A整理了算法设计中常用的实现技巧。A.1利用数组下标属性，将标识性属性定义为从0开始的连续整数，可简化数据模型。阅读第七十六节本节承接上文，指出提炼出的函数若功能雷同仍是重复代码，解决办法是把各种条件抽象成统一形式，用一个函数一致处理，即表驱动方法，如第6章过河问题就是把过河动作做成数据表统一处理。阅读
