博文
搜索方法小结(2006-09-11 00:30:00)
摘要：搜索方法小结 2006/09/11 rickone
不管哪种搜索，都统一用这样的形式表示：搜索的对象是一个图，它面向一个问题，不一定有明确的存储形式，但它里面的一个结点都有可能是一个解（可行解），搜索的目的有两个方面，或者求可行解，或者从可行解集中求最优解，我们用两张表来进行搜索，一个叫OPEN表，表示那些已经展开但还没有访问的结点集，另一个叫CLOSE表，表示那些已经访问的结点集。
一、蛮力搜索（DFS，BFS）DFS和BFS是最基本的搜索算法，用上面的形式表示它们是非常相似的。
BFS（Breadth-First-Search 宽度优先搜索）首先将起始结点放入OPEN表，CLOSE表置空，算法开始时：1、如果OPEN表不为空，从表中开始取一个结点S，如果为空算法失败2、S是目标解吗？是，找到一个解（继续寻找，或终止算法）；不是到33、将S的所有后继结点展开，就是从S可以直接关联的结点（子结点），如果不在CLOSE表中，就将它们放入OPEN表末尾，并把S放入CLOSE表，重复算法到1
DFS（Depth-First-Search 深度优先搜索）首先将起始结点放入OPEN表，CLOSE表置空，算法开始时：1、如果OPEN表不为空，从表中开始取一个结点S，如果为空算法失败2、S是目标解吗？是，找到一个解（继续寻找，或终止算法）；不是到33、将S的所有后继结点展开，就是从S可以直接关联的结点（子结点），如果不在CLOSE表中，就将它们放入OPEN表开始，并把S放入CLOSE表，重复算法到1
没看出有什么不同？擦干净了眼镜再看一遍吧。
知道BFS和DFS有什么不同吗？B和D嘛。-_-!
仔细观察OPEN表中待访问的结点的组织形式，BFS是从表头取结点，从表尾添加结点，也就是说OPEN表是一个队列，没错，BFS首先就要让你想到‘队列’；而DFS，它是从OPEN表头取结点，也从表头添加结点，也就是说OPEN表是一个栈！
DFS用到了栈，所以有一个很好的实现方法，那就是递归，系统栈是计算机程序中极重要的部分之一，你不想递归？怕它用完了？放那儿也是浪费。而且用递归也有个好处就是，在系统栈中只需要存结点最大深度那么大的空间，也就是在展开一个结点的后续结点时可以不用一次全部展开，用一些环境变量记录当前的状态，在递归调用结束后继续展开。
利用系统栈实现的DFS函数 d......
误差的积累(2006-09-02 00:22:00)
摘要：这学期开了一门我很喜欢的课程《数值分析》，我感觉它讨论的都是如何控制误差，还有如何提高算法效率。
教科书上的例子，计算定积分I(n)=e^-1Sx^ne^xdx[0,1] 积分区间[0,1]并估计误差。
首先是找到递推公式I(n)=1-nI(n-1)，然后求出I(0)=1-1/e，用泰勒公式以部分和近似代替取值为0.6321，且知道误差限为0.25*10^-4，然后以递推公式算I(1),I(2),...I(n)，并求它们的误差限，结果是求到I(8)的时候出现了负值，从原始积分看不可能为负值，于是就考虑误差从哪里‘积累’起来了？
原来是递推公式有问题，这样的东西以前从来没考虑过，从操作次数和效率上看这个递推式是不错的算法，但从误差角度看很烂，可以算出e(n)=n!*e(0)=n!*0.25*10^-4，阶乘啊，多么恐怖，即使是e(0)有非常大的精确度，在阶乘面前也是弱不禁风，算不了几下，指数效应就出来了，所以整个算法彻底失败。
误差的累积是算法上的问题，所以要控制误差就需要改进算法，做的改进是，将它反过来，化成：
I(n-1)=(1-I(n))/n
一眼看去，反过来不是很好的办法，如果我要求I(n)就要先求I(n+1)，如此没有个头了，其实不然，从原积分看知道I(n)单调减，且有下界，所以它的I-n图是一个无穷趋于0的图像，所以取一个很大的n，比如n=1000，设I(1000)=0，那误差也是很小的，然后反过来递推，由于这里误差没有累积，所以算1000前面的所有值，误差也可以在控制之中，有相当的精准度，而整个算法也是线性的，相当巧妙。......
到底应该如何分类？(2006-08-22 20:06:00)
摘要：学了C++，就学了一些面向对象的机制，或者这门语言对面向对象提供的支持，但是否真的懂了面向对象，我觉得这是两码事。
什么是面向对象？我常这样问自己。现在struct可以改用class，成员可以是函数，一个类有自己的一组成员，数据+操作，类可以生成它的实例：对象！
我常常写‘class’，但不知道为什么要写它，同样的功能我可以不这样写，于是就开始反思为什么要C++？前段时间写黑白棋，一开始分了好多类，类之间要相互引用，于是就开了好多friend/friend class，到最后发现这样分简直是糟透了，或许不用C++还不会这么一团糟，再后来，对实现过程没有变，重新分类，分两个：一个是CReversiMap，一个是CReversiBot。从模型的角度看，分‘类’就是对实物建模，我有多少个实物，就建多少个类，想象一下两个人下棋，无非就两个类：人和棋，人和棋之间只传递一些棋面数据，分工明确，人负责想棋，然后告诉棋盘怎么走棋，棋盘负责接受走棋规则，移动（改变）棋面再等待另一方走棋。这样分类，类和类之间没有什么耦合，只通过接口打交道。所以也不用开friend。做为黑白棋程序设计也是如此，CReversiMap负责棋盘的数据处理，包括走棋的结果和棋盘的显示，CReversiBot就是机器人棋手，然后其它的像置换表、搜索引擎都是它的一部分，如果你要将它们分开方便管理，可以用不同的.cpp文件来写，比如我可以用Evaluation.cpp写它的估值函数一部分。
C++是一种建模思想，也可以从‘代码复用’的角度建模，但我觉得基于实物的建模更合理，算法的复用可以用模板，写成库，实际开发的时候还是基于实物建模。建模建得好不好可以看你不得以用了多少friend，friend破坏类的封闭性，本质上就是一种耦合。
我的一点感想，还在学习中。......
关于人工神经网络(2006-08-20 14:34:00)
摘要：今天有看这方面资料，一点点感想。
首先这样的模型，从功能上讲是很强的，人脑有神经元10^11左右个，我们就可以随心所欲的思考。人的视觉，触觉，听觉都是输入，肢体的控制神经，语言中枢神经和口腔发声控制神经都是输出，从本质上讲这样的抽象是根本的，所谓思维就是这个神经网络中的神经元的相互作用的过程。其次，什么是记忆？记忆就是‘反馈神经’，不知道这个名词准确与否。在《数字逻辑》中时序逻辑电路中也是这样的，输出反过来当成输入，构成一个‘反馈线’，反馈线上的电信号就是‘记忆’，简单的触发器就是这样两个反馈线的与非门构成的，触发器就是‘存储器’的基本元件，一个触发器可以记录一bit，内存上的Memory就是这样做的，同样在神经网络中也是这样，我们把回忆拿出来，重新思考，我们把昨天未下完的一盘棋拿出来继续思考，这就是反馈输入嘛。至于有没有硬盘式的存储器，就不清楚了，实际上，如果把我们的神经系统看成‘电系统’，我们什么时候断过电哟，你拿你的脑袋使劲往墙上撞，有可能会断一会电-_-
其次一点，就是怎么‘学习’？总的来讲，分两种，有教师的学习和无教师的学习，有教师的学习就像是一种训练，我想要这组人工神经网络（ANN）的功能是这样的，我就拿一堆的正确的[输入，输出]去训练它，拿输入数据得到真实的输出，再和理论输出比较，拿这个误差去修改‘弧’上的权值，最终使得它满足所有的‘学习资料’，就拿最简单的与逻辑门来说吧，输入神经元x1,x2（0,1），输出y=f(x1*w1+x2*w2-e)，测试数据是：0,0,00,1,01,0,01,1,1
初使w1,w2,e随机得到，假设是7,4,5吧，第三组数据训练有误差，结果是7-5=2输出是1，于是修正w1=w1+a(0-1)x1w2=w2+a(0-1)x2
其中a是(0,1)间的值，表示学习的增益因子，用于控制调整的速度，就取0.5吧，于是修正后的w1=6.5,w2=4，还是不满足，再修正几次，直到w1=4.5,w2=4,e=5就满足了，于是它就会做‘与’运算了。
这里教师的作用就是提供‘正确’的训练数据，这样做学得很快，跟人一样，我们在学校里学习就是这样。另外一种无教师的学习，就会慢很多，会在失败中学习，想起以前英语老师教我们学英语就是要"Make mistakes & try again!"，从错误中学习。而正确与错误与否是外界告......
[zjut-oj]密码截获(2006-08-20 01:22:00)
摘要：密码截获 Time Limit:1000MS Memory Limit:1024K
Description:Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化ABBA->12ABBA,ABA->ABAKK,123321->51233214 。因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？
Input:测试数据有若干行字符串，包括字母，数字，符号。（字母区分大小写）
Output:与输入相对应每一行输出一个整数，代表最长有效密码串的长度。
Sample Input:ABBA
12ABBA
A
ABAKK
51233214
abaaab
Sample Output:4
4
1
3
6
5
Source:Jin Qiwei
后来才发现只要80长就够了，所以测试数据很弱，不用DP也行。
/*#include<stdio.h>#include<string.h>#include<memory.h>#include<assert.h>#define MAX_LEN 80char szInput[MAX_LEN+1];unsigned char B[MAX_LEN+1][MAX_LEN];int length;int getcode(){ int i,j,notfound1,notfound2=0; if(length<2) return 1; memset(B,0,(length+1)*MAX_LEN); for(i=0;i<2;++i) { for(j=0;j<length;++j) B[i][j]=1; } for(i=2;i<=leng......
双截棍(程序员版) [转贴](2006-08-18 11:36:00)
摘要：软考室的烟味弥漫 坐满了程序员室里面的监考官 系分 已三年出上午试题的老师 练cpu 耍单片机 硬件功夫最擅长 还会逻辑门三极管 他们学生我习惯 从小就耳濡目染 什么软件跟网络我都耍的有摸有样 什么语言最喜欢 c++面向对象 想要去英伦美帝 学图灵诺伊曼 怎么编 怎么编 离散数学是关键 怎么编 怎么编 数值分析也较难 怎么编 怎么编 数据结构最重要 算法不学莫后悔 死的难看 一段代码写好 一个左子树 右子树 一句不会递归有危险 不停调用 一个优秀的库函 一用好多年 拷贝好带身边 怎么编 怎么编 我学会动态规划 怎么编怎么编 分支限界的难关 怎么编怎么编 已被我一脚踢开 哼 快使用c语言 哼哼哈兮 快使用c语言 哼哼哈兮 编程之人切记 np无敌 是谁在练汇编 背指令集 快使用c语言 哼哼哈兮 快使用c语言 哼哼哈兮 如果我会分治 快速解题 熟用堆栈队列 系统分析 快使用c语言 哼 我用vb描述 哼 万能的回溯法
夜班的程序员，鼠标敲的很响亮练java玩C++，Delphi功夫最擅长。编程语言我习惯，天天都耳濡目染，什么VC跟C#，我都耍得有模有样，什么工具最喜欢， 记事本物美价廉，想要去网吧CS，杀土匪的老板。怎么玩，怎么玩，任务繁重走不开。怎么玩，怎么玩，上班就把QQ开。怎么玩，怎么玩，程序全都是BUG，头晕脑胀莫奇怪，处处是错。一个空格向前，又把鼠标点，击键盘，使用我的程序的人有危险，一再重演。一本我不看的书，一放好多年，它一直在身边。怎么办，怎么办，我想破我的脑袋，怎么办，怎么办，已是凌晨２点半，怎么办，怎么办，错误已被我一脚踢开。快使用调试器，哼哼哈兮，快使用ATP，哼哼哈兮，编程之人须切记，基础无敌，是谁还练VB,骂声四起。快使用DEBUG，哼哼哈兮，快使用MASM，哼哼哈兮，只要我有能力，解决问题，老板就一定被我踢，一身正气。快使用调试器，哼，我除错排第一，哼，完美的牛皮！......
置换表与迭代加深(2006-08-02 16:13:00)
摘要：alpha-beta搜索是个很好的搜索方法，在这基础之上为了加快搜索速度，为了让程序搜索到更深的局面中去，才引入了置换表（实际上大部分棋类程序是离不开置换表的，像象棋，我可以让车左右重复走动，那相同的局面会一直出现，直接搜索真是费尽了力气）。
置换表实际上就是一个哈希表，它存储的是之前搜索过的局面，可以是一次搜索时遇到的相同局面，也可以是多次搜索时遇到的相同局面。它工作的时候，简单的来说，就是当搜索一个局面时，首先看是否在哈希表中，如果是直接取出来，而不进行搜索，同时每当完成一次搜索后，就把搜索出的结果存进哈希表。
这个表中要放些什么？首先是评价值，在alpha-beta搜索中，有三种不同类型的评价值，alpha型：它在搜索的子结点中没有找到比当前最好的更好，也就是说至多是那么多，beta型：它在搜索的子结点中有比当前最差的更差，也就是说至少是那么多（差），如果搜出的评价值落在alpha-beta之间，那就是exact型，精确型。其次要放搜索深度，如果当前要对局面进行d层搜索，而发现该局面在置换表中存在，且搜索过d'层（d'>=d），那就可以直接取出来不进行搜索了。最后还有最佳着法。
置换表如何哈希？比较常见的是使用Zobrist键值，这只是一种哈希方法，简单来看就是随机哈希。一个局面有哪些因素：当前谁走棋，每一格上有哪种类型棋，棋子的颜色，等等，我们把所有因素全部用随机数表示，然后将它们进行模2加得到的结果就看成是当前局面的一个key。拿黑白棋来说，可以这样表示Zobrist[pos][color]来表示局面上的棋子，pos取0~63,color取0~1，将局面上所有值模2加起来，然后如果是黑先就得到key，如果是白先就将它取反得到key，整个Zobrist[][]以64位的随机数填满。将得到的key再模上哈希表表长就得到了哈希值。哈希表最重要的是进行冲突处理，我看到一些程序根本没有冲突处理，想了好久不得其解，细细思来：冲突产生的原因在哪？可能是不同的局面得到了相同的key，也可能是不同的key存到了相同的哈希表位置，如果是前者，大可以不必担心，采用64位的Zobrist键值，随机性很大，如果随机数取得好，‘撞’到相同key的机率非常之低，如果是后者那就会产生非常严重的后果，当前局面分明没有搜索过，却和另外一个局面的哈希值一样，而误以为搜索过，而产生了......
估值函数与优化搜索(2006-07-30 00:21:00)
摘要：前面说了最小最大原理，为什么要最小最大原理？为什么要搜索？我们可以更简单的看对弈这件事儿，下棋的时候，从一开始到结束，每当我要走棋时，我会考虑怎么走？有N种可行走法，但只能选一种，换个方式想这问题，人工智能不过是作一种‘选择’，而这里的‘选择’要能促使你最终赢棋！
可以选择的前提是要能分出谁高谁低，哪步着法臭，哪步着法妙，于是就需要要一个估值函数Eval(p),p是局面，也就是由这个评价函数分出哪个局面（或者着法，着法可以看成下一个局面）更好，如果Eval(p1)<Eval(p2)，我们就有理由说，或者大胆地说，p2比p1更好！但是很多时候，你并不能断言，你做的决定是最好的，这在于棋类游戏的复杂程度，像一些高深的棋类游戏，棋的变化非常多非常复杂，那你能完全相信你的估值函数吗？不能，有可能，现在看来一步很臭的棋，在不久的将来将会使局面变得很好，这就是妙手，这是经常出现的。出现这样情况的原因是，我们找到的估值函数都是从一个局面来看的，它是静止的，它看不到未来的变化，所以它是非常粗糙的。而搜索的目的正是为了‘更好的’评价棋局，可以把搜索看成是动态的估值！
如何估值？
这和具体的棋类游戏有关，同时也和你最终打包的程序的棋力有关，估得好，棋力高，这是很显然的。不管什么棋类的估值，它都有一个共同点：对特定的局面估值要非常准确！特定的局面是那些‘胜负’非常明显的局面，你要为‘胜’打一个最高的分HScore，为‘负’打一个负最高的分-HScore，而‘平局’可以适中给分，可以给一个稍大于0的分，在不能获胜的局面里，会趋向于平局。
然后就是要有前瞻性，从一个局面分析，不搜索也不是不可以看得‘深刻’，也可以说是‘全局观’，估值函数要体现游戏的全局观，它是从整体上把握，从一个点看到了一条线！这样才是好的估值。
好了，下一个话题是‘优化搜索’，哦，这可难了，我现在还看不懂一些高级搜索算法。其实用负极大搜索算法编出来的程序是不能搜的，基本上不能搜。因为搜索量实在太大了！在一些规则简单的棋类游戏中，像黑白棋，平均分支因子都有10左右，直接去搜索，是搜不了几层的，这样的指数效应太明显了！最简单和最基本的优化方法是alpha-beta剪枝！
这是一种纯数学上的方法，是在不对搜索的结果影响的前提下剪枝，它可以使分支因子变为原来的开根号那么大（平均情况）！alpha是一个当前最好的值......
最小最大原理与搜索方法(2006-07-28 16:14:00)
摘要：我的黑白棋终于算是会走棋了，高兴了好一阵子，而且还能战胜我自己。我想把资料总结一下，以下所述的将从最简单的开始，与黑白棋无关，是广义的棋类博弈算法。网上有好多算法文章介绍，我只是简单概括一下。
最小最大原理
最小和最大是相反的矛盾的，正如下棋的两个人，他们是对手，他们在进行对抗，其中一个叫最小者，另一个叫最大者，最大者（想像成我）希望棋面对‘我’最好（最好是赢棋），最好就是最大，反过来，对手就希望棋面对‘我’最差，最差就是最小，最大就是对已最有利，最小就是对对方最有利。这里的最小最大，是有一个参照物的，不管以谁为参照物，它是固定的。最小和最大是对称的，平等的，就像两个重物挂在一杆称上，不断的在较劲。
而最小最大原理是说什么，它是说‘最大者’在选择最大（好）的棋走的时候，它要选对方在回应这步棋时最小（对对方最好）着法中的最大着法！（着法就是可以走的棋）这里涉及了一棵树，它叫博弈树，根在上面，倒长的一棵树。
根是当前局面，我要从当前局面的所有可行着法中选一个‘我认为’‘最佳’的着法走这步棋，这所有的可行着法，就对应着所有的子树，当走了某一步后，就到达了子树的根，同样的情况发生了，这时你是站在最小者的立场上想棋的，所以最小最大反了过来，孙子曰过‘知已知彼，百战不殆’，你不能站在对方的立场想问题，就无法取得胜利！
注意到，这其实是对博弈树的深度优先搜索，只是搜索的时候有两个对立的处理模块，最大搜索和最小搜索，最大的调用最小的，最小的调用最大的，是一个双递归。像这样：
int Max(int depth)//最大搜索{ int best = -INFINITY; if (depth <= 0)//depth是控制深度 { return Evaluate();//返回对当前局面的‘看法’，估值 } GenerateLegalMoves();//生成当前所有着法 while (MovesLeft())//遍历每一个着法 { MakeNextMove();//实施着法 val = Min(depth - 1);//反过来搜索，站在最小者一方 UnmakeMove();//撤销着法 if (val > best) { best = val; } } return be......
[2006/07/24]逼角棋(2006-07-24 13:58:00)
摘要：昨天和爷爷聊天，聊到我唯一的一个幺嗲嗲（我爷爷的弟弟），那年他仙逝我才三岁，农村里老人家过逝也是喜事，叫白喜事，要整顿酒，很多客人很热闹，那时我很聪明，我爸说的，刚教我走逼角棋，就在那一天，我赢了另外一个嗲嗲一盘棋，然后就不再下了，赢了就跑！
逼角棋的棋盘是这样的：
一方棋子是圈，一方是叉，可以随手用粉笔在地上画一个，然后用任何不同的东西做棋子，规则是棋子延着边线走，当已方的两个棋子将对方的一个棋子逼到一个角时，就吃了这颗子，直到全部吃光时胜。
呵呵，小时候的游戏啊！
今天我的黑白棋程序终于有点进展了，总算是界面部分做得差不多了，今天还做了位棋盘，我不会PS，棋盘和棋子是一个朋友帮画的，画得很棒，非常感谢！
......