了解了基本搜索算法，下面就来看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*是求这样一个和最短路径有关的问题，那单纯的最短路径问题当然可以用A*来算，对于g(n)就是[S,n]，在搜索过程中计算，而h(n)我想不出很好的办法，对于一个抽象的图搜索，很难找到很好的h(n)，因为h(n)和具体的问题有关。只好是h(n)=0，退为有序搜索，举一个小小的例子：

与结点写在一起的数值表示那个结点的价值f(n)，当OPEN表为空时CLOSE表中将求得从V0到其它所有结点的最短路径。考虑到算法性能，外循环中每次从OPEN表取一个元素，共取了n次（共n个结点），每次展开一个结点的后续结点时，需O(n)次，同时再对OPEN表做一次排序，OPEN表大小是O(n)量级的，若用快排就是O(nlogn)，乘以外循环总的复杂度是O(n^2logn)，如果每次不是对OPEN表进行排序，因为总是不断地有新的结点添加进来，所以不用进行排序，而是每次从OPEN表中求一个最小的，那只需要O(n)的复杂度，所以总的复杂度为O(n*n)，这相当于Dijkstra算法。在这个算法基础之上稍加改进就是Dijkstra算法。OPEN表中常出现这样的表项：(Vk,fk1)(Vk,fk2)(Vk,fk3)，而从算法上看，只有fk最小的一个才有用，于是可以将它们合并，整个OPEN表表示当前的从V0到其它各点的最短路径，定长为n，且初始时为V0可直接到达的权值（不能到达为INFINITY），于是就成了Dijkstra算法。

    另外一个问题就是八数码难题，一个A*的好例子。
问题描述为有这样一个3*3方阵格子：

格子上有1-8八个数字外加一个空格，每次只能把与空格相临的一个数字移到空格内，移动一次算作一步，给出初始状态和目标状态，求如何以最少的步数完成移动？

设计A*算法时，g(n)就取当前已移动的步数，h(n)取各个数字到目标状态中对应数字的位置的最短距离之和，这样选取的原因是，对于每一次移动，只能使一个数字改变一个相临位置，所以h(n)步是至少需要的，所以满足h(n)<=h*(n)。

   A*的成功之处就是在选择好的h(n)，如果实在没办法令它为0也是可以求得问题的解的。

                                                                                                                                                            算法驿站  (rickone 的 BLOG)

Fibonacci数列F(n)递归地定义为：

        1                n<=2
F(n)={
        F(n-1)+F(n-2)     n>2

列出前几项：1，1，2，3，5，8，13，21，34。。。

    注意到这些数字没有，很多都是在大自然中出现的，我知道的少，不过你可以在互联网上搜一下，关键词：黄金分割。

没错，这个数列中体现了黄金分割，用数学方法很容易证明。首先它是发散的，但是不妨假设F(n+1)/F(n)是可以收敛的，设e=limF(n+1)/F(n)，由递推方程：F(n)=F(n-1)+F(n-2)，两边同除F(n-1)得（在极限情况下）：e=1+1/e，解出来就得e=1.618…，同时也得知它近似地相当于指数数列1.618^n，至少会以这样的增涨率增涨。

    以下总结一下Fibonacci数列的计算方法。

1，直接递归计算。

int fibonacci(int n)
{
            if(n<=2)
                        return 1;
            return fibonacci(n-1)+fibonacci(n-2);
}

    它的计算效率同它的数值增涨效率一样是指数型的（O(1.618^n)），因为它会在递归中重复计算子问题，改进的方法就是‘打表’，把已经计算过的F(n)记录下来，在以后的计算中只管用就是了，也叫备忘录方法，也是DP算法的一个组成部分。

    2、备忘录方法。

int fibonacci(int n)
{
            if(mem(n)>0)
                        return mem(n);
            return mem(n)=fibonacci(n-1)+fibonacci(n-1);
}

    也可以直接用递推法，先开一个表f(n)，然后由f(1)=f(2)=1开始计算。

inf fibonacci(int n)
{
            if(n<=2)
                        return 1;
            int *f=new int[n+1];
            f[1]=f[2]=1;
            for(int i=3;i<=n;++i)
                        f[i]=f[i-1]+f[i-2];
            int result=f[n];
            delete[] f;
            return result;
}

    前者是自顶向下，后者是自底向上，其效率是一样的，都是O(n)。从指数型复杂度到线性复杂度，是多大的提高啊。然而效率还可以提高。

    3、矩阵的方法。

思想来源上上次PKU的acm warmup
http://acm.pku.edu.cn/JudgeOnline/problem?id=3070

{{F(n+1),F(n)},
{F(n),F(n-1)}}

=

{{1,1}      ^n
{1,0}}

    我当时就想，用加法算都只能是O(n)的，换成n个矩阵的连乘不是更废劲吗？其实不然，乘法方法有比加法更好的性质，用加法只能利用前两个的值，而乘法却不同，因为乘法有结合律，可以大幅度下降算法的耗时。

令A(n)表示一个矩阵序列

A(n)=

{{F(n),F(n-1)},
{F(n-1),F(n-2)}

那么A(2)={{1,1},{1,0}}，由那个表达式得到：

A(n)=A(2)^(n-1)，A(2)是己知的2*2矩阵，现在的问题就是如何求

A(2)^n

   因为方阵的乘法有结合律，所以

A(2)^n=A(2)^(n/2)*A(2)^(n/2)，不妨设n是偶数

    所以求A(n)就可以化成求A(n/2)并作一次乘法，所以递归方程是：

T(n)=T(n/2)+O(1)

它的解是O(lbn)，不可思议吧。

这是我AC的代码：
#include <iostream>
using namespace std;

struct Matrix22
{
 int a,b,c;
 void operator*=(const Matrix22 &m);
 void display();
};

void Matrix22::operator *=(const Matrix22 &m)
{
 int p=b*m.b;
 int aa=a*m.a+p;
 int bb=a*m.b+b*m.c;
 int cc=p+c*m.c;
 a=aa%10000;
 b=bb%10000;
 c=cc%10000;
}

void Matrix22::display()
{
 printf("{%d,%d,%d},\n",a,b,c);
}
int main(void)
{
 Matrix22 base[31]={
{1,1,0},{2,1,1},{5,3,2},
{34,21,13},{1597,987,610},{4578,8309,6269},
{7565,7723,9842},{3954,4261,9693},{237,9867,370},
{3858,9269,4589},{8525,5243,3282},{4674,4101,573},
{4477,7947,6530},{8338,2629,5709},{3885,9563,4322},
{4194,3541,653},{8317,3227,5090},{6018,4389,1629},
{9645,2683,6962},{4514,6581,7933},{5757,3707,2050},
{4898,549,4349},{1805,6603,5202},{7634,7221,413},
{797,7387,3410},{2978,7109,5869},{6365,3323,3042},
{5554,9461,6093},{7437,2267,5170},{8258,69,8189},
{9325,4843,4482}
 };
 int n;
 while(1)
 {
  scanf("%d",&n);
  if(n==-1)
   break;
  if(n<2)
   printf("%d\n",n);
  else
  {
   Matrix22 x={1,0,1};
   –n;
   for(int i=0;n;++i,n>>=1)
   {
    if(n & 0×1)
     x*=base[i];
   }
   printf("%d\n",x.a);
  }

 }
 return 0;
}

    最后我们要观察这样的矩阵方法可否推广到一般情形，我们暂且称这样的递推序列为‘c阶线性递推方程’吧，它的意思就是说F(n)由与n相距c远的前面的一些F(m)组成的线性组合，比如Fibonacci数列的最大距离就是2，所以这样的递推式需要确定一个序列至少要知道最初的c个己知初值，我们的目的就是要求这样的递归式的一般算法：

F(n)={F(n-1),F(n-2),…F(n-c)}*K
{F(1),F(2),,,F(c)}^T=C

其中K={x1,x2,…xc}^T，C={c1,c2,…cc}^T都是非0的常向量。

我们构造A(n)表示一个c*c的矩阵序列，且形式为

A(n)=

{{F(n),F(n-1),F(n-2),…F(n-c+1)},
{F(n-1),F(n-2),F(n-3),…F(n-c)},
……
{F(n-c+1),F(n-c),F(n-c-c),…F(n-2c+2)}}

为了使它有意义，n-2c+2>=1，所以n>=2c-1，所以A(n)的初始矩阵是A(2c-1)，可以按递归式直接构造它，然后我们考虑A(n)的生成矩阵会是什么样子，设为G，于是应满足：

A(n)=A(n-1)G

观察A(n-1)的第一行，它刚好就是{F(n-1),F(n-2),…F(n-c)}，由递推式，知G的第一列应为K，而第二列设为x，则要满足{F(n-1),F(n-2),…F(n-c)}x=F(n-1)，很简单，x={1,0,0,…}，同样第三列是{0,1,0,0,…}，所以右边应该是一个(c-1)*(c-1)的单位矩阵I再在最下面补上一行0，于是G可以表示为：

G={K,{I,0}^T}

于是A(n)的通项就是

A(n)=A(2c-1)*G^(n-2c+1)

比如Fibonacci数列的K={1,1}^T，所以
G={K,{I,0}^T}=
{{1,1},
 {1,0}}

    再举一个例子，也是以前做过的一个题，母牛生小牛的题，在一个农场上有很多母牛，第1年有一只母牛，而且每过4年，母牛会开始生小母牛，小母牛过4年后也会开始生，此后就每年生一只小母年，问第n年时有多少只母牛？

简单例出前几个数字：1，1，1，2，3，4，6，。。。会发现一个规律，就是第n年的母牛数F(n)恰等于前一年的母牛数F(n-1)，以及前三年的母牛数F(n-3)之和，其实直接得到这个递推式也不难，因为F(n-3)到F(n)刚好4年（第4年），所以F(n-3)都是一些可以生仔的牛数，它们会添加F(n-3)个小牛，同时F(n-1)是所有的牛妈妈，那当然有F(n)=F(n-1)+F(n-3)。

它的K={1,0,1},c=3，生成矩阵G=
{{1,1,0},
 {0,0,1},
 {1,0,0}}

所以有A(n)=A(3)*G^(n-2)

A(3)=
{{1,1,1},
 {1,1,0},
 {1,0,0}}

    从O(2^n)到O(n)，再到O(lbn)，效率提高得也太猛烈了，不过一点要提出来，不管什么样的算法，Fiboacci数列本身数值的递增是指数型的，所以要想算很高阶的结果，也近乎不太可能，所以经常会在一个模数范围内考虑。

                                                                                                                                              rickone 2006/11/06 算法驿站  (rickone 的 BLOG)

    原来写过一篇文章在笔记本里，后来中病毒我把它格了，也没上网没机会发表出来，主要内容是关于一种比较另类的排序方法的，我叫它散列排序法。凭我的记忆把算法的主要思想写下来。

    排序法总体上可以分两大类，一类是基于‘比较’的，主要有大家非常熟悉的：选择排序，交换排序，插入排序，归并排序等，其算法的复杂度也是用‘比较’的次数衡量的，其中有非常高效和优秀的‘快速排序’，可以说是他们中间的佼佼者，无论从时间还是空间上说都有很好的性能；另外一类也就自然是不基于‘比较’的，《数据结构》上介绍过一种叫‘基数排序’，我觉得也很经典，今天我要向大家介绍的跟基数排序很类似，原理也非常简单。

    和基数排序的方法非常类似，也是采用分配和收集，而我管它叫‘散列’，因为就和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表的冲突处理。

为什么要用拉链法，其实可以从集合的角度看这个算法，实际上我是把整个数列看成一个集合，然后我着手把它分成更小一些的子集，同时使这些子集‘集合间有序’，所谓集合间有序是指：
如果 集合A<集合B
那么 对于任意的x,x属于A，又对于任意的y,y属于B，都成立x<y

然后不断往下分，直到被分的集合中只含有一个元素为止，排序工作就完成了。

再来个例子：
1,4,3,7,3,2
于是
min=1,max=7,n=6
f(x)=[(x-1)*5/6]
第一次划分的结果是：
收集链表ID：0 1 2 3 4 5
[元素]      1 3 4     7
            2 3
就得到了四个子集，设对应ID的子集记为[ID]，那么它们是
{[0],[1],[2],[5]}   （它们也是第一次划分f(x)的值域）
它们是‘集合间有序’的。

算法到此全部描述完了，另外我还想说点具体实现的过程，虽然没源代码了，还有些细节问题。

1、f中的min,max该如何求？
给我们的排序任务，只给出数据地址和数据元素，并没有给出min和max，是不是需要先求一下呢？如果要求一下，又回到了比较的方法，于是整个算法就不是很好的不基于比较的算法。我的看法是，具体排序的时候如果能给出来可以尽量给出（比如，按一个城市所有人的年龄排序，范围可以是0~150），如果真给不出来，没关系，我们取那种类型的数据的最小值和最大值。但是这不会影响到效率吗？后面再讨论效率。
另外再提出个概念，叫‘区分度’，区分度就是指一次划分的时候，得到的子集内的元素的最大值和最小值之差的最大值；这样吧，可能不好理解。这样记，我记一次划分为：
div(min,max):（这样记是因为，一次划分是跟min和max分不开的，确定了min和max才能划分）
{parent} –> {[i]}
那这次划分的区分度就是
max{elem1-elem2|elem1,elem2属于[i]}
在前面的例子中就是1，因为[0]中2-1最大。
为什么要提这个概念，在你划分一次后如果没有得到结果，那必须再对子集进行划分，这时的子划分中的max-min正是前一次的区分度。如果还知道min，那子划分就确定了。而min是可以线性求出来的，于是子划分就完全确定下来了。
区分度约为(max-min)/n *

2、这个算法的效率如何？
首先从时间上考虑。整个排序的过程可以看成是把一个有n个元素的集合分成n个只有一个元素的子集的过程。而就以划分的次数来衡量的话，最差的情况是，连续几次划分都没有分成功，原有集合本身做为子集，但是这样的情况不会持续很久，随着更加细致的划分，区分度会不断变小，区分度的迭代递推式是：d'=d/n，实际上是非常快速的收敛。其次，如果每一次划分只能分成两个子集，效率会如何呢？注意到划分出的子集是集合间有序的，这会联想到快速排序的一次划分，没错快速排序的一次划分能且只能将元素划分成两个部分，这两个部分有序，所以应该和快速排序的效率相当。最后，如果每一次划分能分成两个子集以上，效率会更高吗？不用我说了，应该会更高吧~~
实际上对于离散分布比较均匀（等概率分布）的无序数，排起序来是非常高效的~！
另外从空间上考虑。这就比快速排序差太多了，整个辅助空间需要得很大，基本上需要和原有数据量一样多的空间，应该是O(n)，当n很大时，运行的实际耗时基本上都花在内存空间分配和回收上了。

                                                                                                                                                       算法驿站  (rickone 的 BLOG)