博文
关于动态规划算法的研究(2006-05-19 22:22:00)
摘要：关于动态规划算法的研究
原创：怒火之袍 2003年2月25日
一、动态规划的基本思想
在比较基本的算法设计思想里，动态规划是比较难于理解，难于抽象的一种，但是却又十分重要。动态规划的实质是分治思想和解决冗余，因此它与分治法和贪心法类似，它们都是将问题的实例分解为更小的、相似的子问题，但是动态规划又有自己的特点。
贪心法的当前选择可能要依赖于已经作出的选择，但不依赖于还未做出的选择和子问题，因此它的特征是由顶向下，一步一步地做出贪心选择，但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解。相比而言，动态规划则可以处理不具有贪心实质的问题。
在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。
比较感性的说，其实动态规划的思想是对贪心算法和分治法的一种折衷，它所解决的问题往往不具有可爱的贪心实质，但是各个子问题又不是完全零散的，这时候我们用一定的空间来换取时间，就可以提高解题的效率。
二、动态规划的基本步骤
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可以按以下几个步骤进行：
（1）找出最优解的性质，并刻画其结构特征。
（2）递归地定义最优值。
（3）以自底向上的方式计算出最优值。
（4）根据计算最优值时得到的信息，构造一个最优解。
其中（1）——（3）步是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（4）可以省去。若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（3）中计算最优值时，通常需记录更多的信息，以便在步骤（4）中，根据所记录的信息，快速构造出一个最优解。
三、典型的动态规划举例——矩阵连乘问题
作为经典的动态规划算法举例，矩阵连乘问......
小鼠迷宫问题(2006-03-29 18:36:00)
摘要：Description
小鼠a与小鼠b身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这 m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿上，下，左，右4个方向进入未封闭的房间。小鼠a位于迷宫的(p，q)方格中，它必须找出一条通向小鼠b所在的(r，s)方格的路。请帮助小鼠a找出所有通向小鼠b的最短道路。
对于给定的小鼠的迷宫，编程计算小鼠a通向小鼠b的所有最短道路。
Input
第一行有3个正整数n，m，k，分别表示迷宫的行数，列数和封闭的房间数。接下来的k行中，每行2个正整数，表示被封闭的房间所在的行号和列号。最后的2行，每行也有2个正整数，分别表示小鼠a所处的方格(p，q)和小鼠b所处的方格(r，s)。
Output
输出小鼠a通向小鼠b的最短路长度和有多少条不同的最短路。
第一行是最短路长度,第2行是不同的最短路数。
如果小鼠a无法通向小鼠b则输出“No Solution!”。
Sample Input
8 8 3
3 3
4 5
6 6
2 1
7 7
Sample Output
11
96
Source
Fujian OI -- 2005
#include
#include
#include
#define MAX 8000
struct Position{
int row;
int col;
};
typedef struct Position position;
struct Queue{
position queue[MAX];
int top;
int rear;
};
typedef struct Queue q;
position start,end;
int num=0;
position offset[4];
int grid[MAX][MAX];
void init_q(q *p)
{
p->top=-1;
p->rear=-1;
}
void enqueue(q *p,position x)
{
p->rear++;
p->queue[p->rear].col=x.col;
p->queue[p->rear......
栈与队列的例程(2006-03-29 18:19:00)
摘要：栈与队列，是很多学习算法的同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。所以，理解栈与队列，是走向算法高手的一条必由之路。栈与队列的题目涉及面很广，也很灵活。但是也是很实用的呢。
1.用队列来走一个4X4的迷宫，具体严本上有算法，这里只是实现。
#include
#define m 4
#define n 4
int mg[m+1][n+1];
struct mgque
{
int x,y,pre;
}mgque[25];/*队列：用来存路径*/
struct zl
{
int x,y;
}zl[5];/*四个方向的增量*/
int outlj(struct mgque mgque[],int rear)
{ int i;
i=rear;
do{
printf("(%d,%d)",mgque[i].x,mgque[i].y);
i=mgque[i].pre;
}while(i!=0);
}/*输出用rear反方向输出*/
int mglj()
{
int x,y,i=1,j=1,d,find;/*d是用来循环的增量*/
int rear=0,front=0;
mgque[0].x=1;mgque[0].y=1;mgque[0].pre=-1;
mg[1][1]=-1;/*迷宫左上第一个，若为0可通，标志为-1防止重复*/
find=0;
while(fronttop--;
return x;
}
EmptyS(Stack *s) /*判断空栈*/
{
return s->top==-1;
}
main()
{
int N=1348;
Stack *s;
s=(Stack *)malloc(sizeof(Stack));
s->top=-1;
while(N)
{
push(s,N%8);
N=N/8;
}
while(EmptyS)
{
printf("%d",pop(s));
......