博文
八数码问题（一）(2006-09-12 22:55:00)
摘要：原来粗略的考虑，h函数选各个数码离目标位置的最短距离的和，原则上是可行的，但启发性不大，举个简单例子：
{2,1,3,
8,0,4,
7,6,5}
和目标状态只差1和2的位置交换一下就对了，h函数给出的估计值只有2，实际上却差得太远，如果你小时候有玩过这样的‘数字拼盘’游戏，就会知道，像这样的是没有解的，至少那时候的感觉是这样，就算有解，也需要移很多次。
基于这样的h函数，感觉启发性不够，在海量搜索的时候效果不是很好，像有的CASE，搜到OPEN表+CLOSE表共好几万的结点了还在不停的搜。可见八数码问题有难有易，虽然9!只有三十多万，也比较难搜。
今天写的程序：
#include <iostream.h>
struct Snode
{
int key;
int map[9];
int g,f;
int last;
public:
Snode(){key=0;}
void TransformIn(const int *d);
void TransformOut(int *d);
};
void Snode::TransformIn(const int *d)
{
key=0;
for(int i=0;i<9;++i)
key=key*9+(map[i]=d[i]);
}
void Snode::TransformOut(int *d)
{
for(int i=0;i<9;++i)
{
d[i]=map[i];
}
}
int spath[9][9]=
{{0},
{0,1,2,1,2,3,2,3,4},
{1,0,1,2,1,2,3,2,3},
{2,1,0,3,2,1,4,3,2},
{3,2,1,2,1,0,3,2,1},
{4,3,2,3,2,1,2,1,0},
{3,2,3,2,1,2,1,0,1},
{2,3,4,1,2,3......
A*高效搜索算法(2006-09-11 17:31:00)
摘要：A*高效搜索算法 2006/09/11 rickone
了解了基本搜索算法，下面就来看A*，神奇的A*。（--->搜索方法小结）
A*是一种启发式搜索，一种有序搜索，它之所以特殊完全是在它的估价函数上，如果我要求的是从初始结点到目的结点的一个最短路径（或加权代价）的可行解，那对于一个还不是目标结点的结点，我对它的评价就要从两个方面评价：第一，离目标结点有多近，越近越好；第二，离起始结点有多远，越近越好。记号[a,b]是表示结点a到结点b的实际最短路径代价。设起始结点为S，当前结点为n，目标结点为G，于是n的实际代价应该是f*(n)=g*(n)+h*(n)，其中g*(n)=[S,n],h*(n)=[n,G]，对于是g*(n)是比较容易得到的，在搜索的过程中我们可以按搜索的顺序对它进行累积计算，当然按BFS和DFS的不同，我们对它的估价g(n)可以满足g(n)>=g*(n)，大多可以是相等的。但是对于h*(n)我们却了解得非常少，目标结点正是要搜索的目的，我们是不知道在哪，就更不知道从n到目标结点的路径代价，但是或多或少我们还是可以估计的，记估价函数f(n)=g(n)+h(n)。
我们说如果在一般的图搜索算法中应用了上面的估价函数对OPEN表进行排序的，就称A算法。在A算法之上，如果加上一个条件，对于所有的结点x，都有h(x)<=h*(x)，那就称为A*算法。如果取h(n)=0同样是A*算法，这样它就退化成了有序算法。
A*算法是否成功，也就是说是否在效率上胜过蛮力搜索算法，就在于h(n)的选取，它不能大于实际的h*(n)，要保守一点，但越接近h*(n)给我们的启发性就越大，是一个难把握的东西。
A*算法流程：
首先将起始结点S放入OPEN表，CLOSE表置空，算法开始时：
1、如果OPEN表不为空，从表头取一个结点n，如果为空算法失败
2、n是目标解吗？是，找到一个解（继续寻找，或终止算法）；不是到3
3、将n的所有后继结点展开，就是从n可以直接关联的结点（子结点），如果不在CLOSE表中，就将它们放入OPEN表，并把S放入CLOSE表，同时计算每一个后继结点的估价值f(n)，将OPEN表按f(x)排序，最小的放在表头，重复算法到1
最短路径问题，Dijkstra算法与A*
A*是求这样一个和最短路径有关的问......
搜索方法小结(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是目标解吗？是，找到一个解（继续寻找，或终止算法）；不是到3
3、将S的所有后继结点展开，就是从S可以直接关联的结点（子结点），如果不在CLOSE表中，就将它们放入OPEN表末尾，并把S放入CLOSE表，重复算法到1
DFS（Depth-First-Search 深度优先搜索）
首先将起始结点放入OPEN表，CLOSE表置空，算法开始时：
1、如果OPEN表不为空，从表中开始取一个结点S，如果为空算法失败
2、S是目标解吗？是，找到一个解（继续寻找，或终止算法）；不是到3
3、将S的所有后继结点展开，就是从S可以直接关联的结点（子结点），如果不在CLOSE表中，就将它们放入OPEN表开始，并把S放入CLOSE表，重复算法到1
没看出有什么不同？擦干净了眼镜再看一遍吧。
知道BFS和DFS有什么不同吗？B和D嘛。-_-!
仔细观察OPEN表中待访问的结点的组织形式，BFS是从表头取结点，从表尾添加结点，也就是说OPEN表是一个队列，没错，BFS首先就要让你想到‘队列’；而DFS，它是从OPEN表头取结点，也从表头添加结点，也就是说OPEN表是一个栈！
DFS用到了栈，所以有一个很好的实现方法，那就是递归，系统栈是计算机程序中极重要的部分之一，你不想递归？怕它用完了？放那儿也是浪费。而且用递归也有个好处就是，在系统栈中只需要存结点最大深度那么大的空间，也就是在展开一个结点的后续结点时可以不用一次全部展开，用一些环境变量记录......
模式匹配的KMP算法详解(2006-06-12 16:33:00)
摘要：模式匹配的KMP算法详解
这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。
注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法：
int Index(String S,String T,int pos)//参考《数据结构》中的程序
{
i=pos;j=1;//这里的串的第1个元素下标是1
while(i<=S.Length && j<=T.Length)
{
if(S[i]==T[j]){++i;++j;}
else{i=i-j+2;j=1;}//**************(1)
}
if(j>T.Length) return i-T.Length;//匹配成功
else return 0;
}
匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子：
S:aaaaabababcaaa T:ababc
aaaaabababcaaa
ababc.(.表示前一个已经失配)
回溯的结果就是
aaaaabababcaaa
a.(babc)
如果不回溯就是
aaaaabababcaaa
aba.bc
这样就漏了一个可能匹配成功的情况
aaaaabababcaaa
ababc
为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。
改进的地方也就是这里，我们从T串本身出发，事先......
多线程可否应用在搜索算法上？(2006-03-29 23:10:00)
摘要：书上看到一个多线程文件搜索器的例程，如果说这是算法的法，那在WINDOWS里早就用过了，想想用WINDOWS在硬盘上搜索文件，是不是很快？
简单的说，搜索算法有两种，深度优先和广度优先。优先就是说搜索的时候是单线程的，于是就有线程到达结点的先后，根据算法固有的侧重方向不同而分为深度优先和广度优先。深度优先就是递归式，在子结点延伸的结点中搜索的时候，前一搜索器在那里等待它的回溯，回溯后再进行下一枝的搜索，这里的等待是不是在浪费时间？广度优先就是层次式，把同一层次（相同父结点的子结点）的结点一齐压入队列，从外面看就像是一层一层按广度从上往下‘铺’开来搜索的，但事实上处于同一层的结点往下‘铺’的时候，并不是同时的，虽然处于同一层，但入队的时机不同，因此也可以看成是有时间停滞。
如果在这里应用多线程的思想，那情况会不会更好呢？在每一个非叶子结点上都启动一个线程，该线程负责往下搜索，原线程处于等待状态，当下一级的搜索线程完成后，回调搜索的结果。整体思路是这样的，感觉有点像深搜也有点像广搜，如果不考虑创建线程的时间，认为线程是同步启动的话，那整个程序将会在最快的时间内到达全部结点。
呵呵~只是一种想法，不知道这样做会不会时间重叠，这样的东西我也不好说时间复杂度了，如果有重叠那会是有所提高的，如果没有，算法就没有提高，同样是O（n）。只是笔者的设想而已。......
CRC循环冗余校验码(2006-03-16 11:17:00)
摘要：CRC（Cyclic Redundancy Check)循环冗余校验码
是常用的校验码，在早期的通信中运用广泛，因为早期的通信技术不够可靠（不可靠性的来源是通信技术决定的，比如电磁波通信时受雷电等因素的影响），不可靠的通信就会带来‘确认信息’的困惑，书上提到红军和蓝军通信联合进攻山下的敌军的例子，第一天红军发了条信息要蓝军第二天一起进攻，蓝军收到之后，发一条确认信息，但是蓝军担心的是‘确认信息’如果也不可靠而没有成功到达红军那里，那自己不是很危险？于是红军再发一条‘对确认的确认信息’，但同样的问题还是不能解决，红军仍然不敢冒然行动。
对通信的可靠性检查就需要‘校验’，校验是从数据本身进行检查，它依靠某种数学上约定的形式进行检查，校验的结果是可靠或不可靠，如果可靠就对数据进行处理，如果不可靠，就丢弃重发或者进行修复。
CRC码是由两部分组成，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码共长n个bit，信息码长k个bit，就称为(n,k)码。 它的编码规则是：
1、首先将原信息码(kbit)左移r位(k+r=n)
2、运用一个生成多项式g(x)（也可看成二进制数）用模2除上面的式子，得到的余数就是校验码。
非常简单，要说明的：模2除就是在除的过程中用模2加，模2加实际上就是我们熟悉的异或运算，就是加法不考虑进位，公式是：
0+0=1+1=0,1+0=0+1=1
即‘异’则真，‘非异’则假。
由此得到定理：a+b+b=a 也就是‘模2减’和‘模2加’直值表完全相同。
有了加减法就可以用来定义模2除法，于是就可以用生成多项式g(x)生成CRC校验码。
例如： g(x)=x4+x3+x2+1,(7,3)码,信息码110产生的CRC码就是：
&n......
[代码]搬运工1(2006-02-08 18:25:00)
摘要：//: PORTER.H - PORTER HEADER - 2006.2 rickone
#include<iostream.h>
#ifndef _PORTER_HEADERFILE
#define _PORTER_HEADERFILE
class PorterMap
{
int width,height;
int *data;/* map data means :
0 - empty place
1 - goal place without box
2 - box on empty place
3 - box on goal place
4 - wall
0,1 r reachable
2,3,4 r unreachable
*/
int px,py;//porter place
int *reach;//mark the place where the porter now can reach
int boxnumber;
void dfsreach(int,int);
void reachmap(int,int);
public:
PorterMap(istream&);/*map data loaded from std input stream & its format(ascii) :
first line two integers for width & height -
&nb......
散列排序法(2006-01-27 18:51:00)
摘要：原来写过一篇文章在笔记本里，后来中病毒我把它格了，也没上网没机会发表出来，主要内容是关于一种比较另类的排序方法的，我叫它散列排序法。凭我的记忆把算法的主要思想写下来。
排序法总体上可以分两大类，一类是基于‘比较’的，主要有大家非常熟悉的：选择排序，交换排序，插入排序，归并排序等，其算法的复杂度也是用‘比较’的次数衡量的，其中有非常高效和优秀的‘快速排序’，可以说是他们中间的佼佼者，无论从时间还是空间上说都有很好的性能；另外一类也就自然是不基于‘比较’的，《数据结构》上介绍过一种叫‘基数排序’，我觉得也很经典，今天我要向大家介绍的跟基数排序很类似，原理也非常简单。
和基数排序的方法非常类似，也是采用分配和收集，而我管它叫‘散列’，因为就和hash散列表一样，而且我可以说当数据比较均匀的离散分布的时候，效率是非常高的，可以花很少的几次散列就得到有序结果。
[写在前面，也跟基数排序一样只适用于整数排序，因为不基于比较就只能从元素，即数的本身出发了。]
先举个例子，设待排序的数是：
4,2,5,1,3
我们排序的任务就是让上面一列数有序，看看我们要做的结果是什么：
1,2,3,4,5
于是我们的任务就是，把前面一列数各位数放到‘正确’的位置上去，使得它有序。而一个数和它的正确位置就是一个映射关系，于是我们就是要找到一个函数f(x)，使f(x)->‘x的正确位置’！
上面的例子非常简单，f(x)=x，但实际情况非常复杂，其实像这样的f(x)是不可能有很好的数学表达式的，别指望在这里做更多的努力。于是我着手找近似的f(x)，我的想法是，只要让它不会错太多就行了，不完善的可以慢慢做得完善。
实际上f(x)就是一个散列函数，只不过它不是用来检索而是用来排序，我给出一个f(x)=[(x-min)*(n-1)/(max-min)]，其中min是这列数的最小值，max是这列数的最大值，n是这列数的个数，那值域就会在[0,n-1]，再用这些值找散列存储位置。
在这样一个近似的f(x)函数下，会出些‘意外’的情况，首先可能会有两个元素得到相同的f(x)值，也就是‘冲突’，冲突如何解决？可以采用拉链法，类似于hash表的冲突处理。
为什么要用拉链法，其实可以从集合的角度看这个算法，实际上我是把整个数列看成一个集合，然后我着手把它分成更小一些的子集，......
规格化的随机变量(2005-12-18 15:00:00)
摘要：规格化就是把随机变量的取值限制在[0,1)之间。
尝试过从双精的标准出发得到随机数，但那样很难保证其等概率性，于是还是从rand()的标准出发吧。
ANSI C给出了标准的随机变量计算方法和函数。其算法可以查相关资料，现只给出函数原型：
int rand(void);
返回值为int型，在WIN32里是4个字节，但实际上有用部分只有前15bit，生成的随机数是一个0~0x7FFF（十进制32767）的随机正整数。这里假设由标准算法生成的随机数的这15个bit是等概率得到0或1的，那么就用它‘拼’成更高一些位数的随机数，于是给出下面的算法：
double drand(void)
{
return (double)(
rand()<<15 | rand()
) /
(double)0x40000000;
}
rand()<<15 | rand() 将拼成一个30bit的随机整数，取值0~3FFFFFFF，于是相除之后将得到大于等于0小于1的小数。
使用
得到任意范围[a,b)内的随机浮点数：
double i=a+drand()*(b-a);
float j=a+(float)(drand()*(b-a));
得到任意范围[a,b]内的随机整数：
int i=a+(int)(drand()*(1+b-a));
测试
接合前面的算法，给出如下的测试用例：
double frand(double (*p)(double),double h)
{
double x=drand(),y=drand()*h;
if(y<p(x))return x;
return frand(p,h);......
满足任意概率密度函数分布的随机变量生成算法(2005-12-18 15:03:00)
摘要：概率密度的定义
概率简单地说就是在空间某处附近一确定的范围内发生某事件的可能性，而概率密度则是概率与空间范围之比的极限。在讨论更复杂一些的空间之前，可以从一维的线性空间出发定义它们。
在一维空间中，用数轴表示所有的点，定义Ф(x)为：随机变量i，当i<x时的概率，因此得Ф(-∞)=0，Ф(+∞)=1（因为全概率为1），这个条件是直接由定义得出，称为归一化条件。
由此当x取数轴上的点时，随机变量i取到[x,x+△x](△x>0)中时的概率应该为Ф(x+△x)-Ф(x)，则定义i取到这个区间的平均概率密度p^=(Ф(x+△x)-Ф(x))/ △x，此时如果极限:
lim(Ф(x+△x)-Ф(x))/ △x=p(x) 存在
△ x->0
则称极限值为这一点的概率密度，由数学知识这正是导数的定义，于是有p(x)=dФ/dx，于是有△Ф=∫p(x)dx，积分区域为△，虽然这是从一维情况推出，这是概率的一般形式定义。于是归一化条件就相应为∫p(v)dv=1，积分区域为全空间。
由此概率密度函数就唯一决定了随机变量的分布，反过来我们也说随机变量服从某种概率密度函数的分布。
如何由p函数模拟随机变量的生成
首先我们要有一个这样的随机函数，Ｃ的原型如下：
double random();/*返回一个大于等于0，小于1之间的等概率随机双精度小数*/
-->规格化的随机变量<--
这个算法的实现将在以后给出算法，事实上笔者最开始学习编程时就是学的这种随机函数，它是BASIC里的标准函数，这里只是为了讨论的需要，因为由它可以非常方便的得到任意范围内的随机数，包括浮点数或整数。
然后我们再拿来这样一个任意的概率密度函数p(x)，且满足归一化条件∫p(x)dx=1，积分区域为[0,1)。最后再给出这个函数在[0,1)上的上限（最大值）h。然后用下面的方法生成服从该分布的随机变量。
首先得到一个等概率的随机的二维的点(x,y)，它落在矩形区域[0,1;0,h]内，同时我们还要求这样一个条件y<p(x)，如果得到的点不满足这个条件则重新取点，也就是说把那些不满足此条件的点‘去掉’。最后我说这里的x满足p(x)的分布。证明如下：
......