马尔科夫链_马尔可夫过程
一、引言
1、马尔科夫链的数学背景 马尔可夫链，因安德烈•马尔可夫（A.A.Markov，1856－1922）得名，是数学中具有马尔可夫性质的离散时间随机过程。该过程中，在给定当前知识或信息的情况下，过去（即当期以前的历史状态）对于预测将来（即当期以后的未来状态）是无关的。
马尔可夫链是随机变量X_1,X_2,X_3...的一个数列。这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”，而X_n的值则是在时间n的状态。如果X_{n+1}对于过去状态的条件概率分布仅是X_n的一个函数，则
P(X_{n+1}=x|X_0, X_1, X_2, \ldots, X_n) = P(X_{n+1}=x|X_n). 这里x为过程中的某个状态。上面这个恒等式可以被看作是马尔可夫性质。
2、马尔科夫链的典型应用
①马尔科夫链在股指期货投资中的应用
马尔科夫链转移矩阵的有效状态以近时点动量策略原时点反转策略为主,有效抓住了上涨和下跌的中期和初期.从而准确的抓住了日内股指波动. ②马尔科夫链在天气预报中的应用
通过对马尔科夫链理论和切普曼-柯尔莫哥洛夫方程(方程)的探讨,,结合天气情况不确定等诸多特点,构想了天气情况预报的马尔科夫链预测模型,给出了马尔科夫链的初始概率和多重转移概率的计算方法,根据此算法可以预报短期天气情况,同时扩展到对未来天气情况趋势的预测。
③马尔科夫链在环境预测中的应用
鉴于目前环境质量预测在理论方法和实践上的缺乏，把马尔科夫链引入环境质量的预测中，将各种污染物的浓度变化过程视作马尔科夫过程，通过预测各种污染物的污染负荷系数来推知其浓度值/
④马尔科夫链在桥梁状态预测中的研究与应用
马尔科夫链以矩阵的形式来表达桥梁状况,通过求解状态转移矩阵,进一步预测桥梁未来数年内的基本状况。 综合考虑了桥梁检修的影响,给出了桥梁检修后不同状态的状态转移矩阵,为进一步引入实际数据做了充分的准备。
3、相关文献
《程序设计实践》作者 Brian W.Kernighan
程序设计实践并不是只是写代码。程序员必须评价各种折中方案，在许多可能性之中做出选择，排除错误，做测试和改进程序性能，还要维护自己和其他人写的软件。在满足规范的同时还必须关注许多问题，包括兼容性，坚固性和可靠性等等。
该书从排错，测试，性能，可移植性，设计，界面，风格和记法等方面，讨论了程序设计中的实际的同时又是非常深刻和具有广泛意义的思想，技术和方法。本书值得每个梦想并努力成为优秀程序员的人参考，值得每个计算机专业的学生和ＩＴ从业者阅读，也可作为程序设计高级课程的教材或参考书。
其他书籍：Matthew Austern 的《类属程序设计与S T L》(Generic Programming and the STL，Addison - Wesley，1998 )
对C++ 语言本身的参考文献当
然是Bjarne Stroustrup的《C + +程序设计语言》(C++ Programming Language第3版，Addison-Wesley，1997 ) ，Larry Wa l l、Tom Christiansen和Randal Schwartz的《Perl程序设计》(Programming Perl 第2版，O ’ Reilly ，1996 )等等。
4、国内外现状
自我国数学家教育家中科院王梓坤院士在上世纪中期将马尔科夫链引进入我国后，取得了很大的成就，尤其是在天气短期预测方面。
二、哈希表介绍
一般的线性表、树中，记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上，查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而查找时，只需根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此不需要进行比较便可直接取得所查记录。在此，称这个对应关系f为哈希函数，按这个思想建立的表为哈希表（又称为杂凑法或散列表）。
三﹑编写的C程序
⒈总体思路
解决马尔科夫链的思维 ，马尔科夫链是根据不同的前缀，随机选择后缀，从而生成句子，我们可以单独储存文章中的每个词，每个词后跟一个链表，当查询到这个词的时候，也能查询到与它关联的链表，从而从与它相关的链表中随机选取一个词输出，我们可以做一种哈希表，让前缀做关键字，它的值是与前缀相关联的所有词的集合。定义一个数据结构，由一个前缀和一个后缀链表组成。所有这些信息存在一个散列表里，前缀是关键码。每个前缀由两个组成。如果一个后缀在给定前缀下的出现
多于一次，则每个出现都单独包含在有关链表里。
⒉程序分析：
⑴程序开始，用的是宏定义和枚举类型，用typedef声明新类型State和Suffix，把每个词储存成独立的字符串。
⑵hash函数对数组里所有字符串的拼接做散列，lookup向 s p - > p r e f [ ]里存入一个指针。利用 s p r i n t f动态地建立格式串用来维护缓冲区导出的两个常数之间的关系。
⑶函数b u i l d有两个参数，一个是p r e f i x数组，用来保存前面的所有的输入词；一个是个F I L E指针。函数把p r e f i x和读入词的一个拷贝送给a d d，该函数在散列表里加入一个新项，并更新前缀数组：对m e m m o v e的调用是在数组里做删除。这个操作把前缀数组里从 1到N P R E F - 1的元素向下搬，移到从0到N P R E F - 2的位置。这也就删去了第一个前缀词，并为新来的一个在后面腾出了位置。函数a d d s u f f i x把一个新后缀加进去， a d d完成给有关前缀加入一个后缀的一般性工作，a d d s u f f i x做的是把一个词具体地加进后缀链表里。函数 a d d由b u i l d调用，而a d d s u f f i x只在a d d内部使用这就完成了输入。
⑷对于输出，如果输出非常长，我们可以在产生了一定数目的词之后终止程序；另一种情况是程序遇
到了后缀N O N W O R D。最终看哪个情况先出现。函数g e n e r a t e产生每行一个词的输出，用文字处理程序可以把它们汇成长的行。
⑸把所有东西放到一起，装进一个 m a i n函数里，它从标准输入流读入，生成至多有指定个数的词序列。
⑹程序结束。
⒊其他应用的知识：下程序还用到了链表，结构体以及处理动态链表的函数，特作说明。
malloc函数
其作用是在内存的动态存储区中分配一个长度size的连续空间。此函数的值（“即返回值”）是一个指向分配域其实地址的指针(类型为void)。如果此函数未能成功地执行，则返回空指针。
结构体：C语言允许用户自己指定这样一种结构，它相当于高级语言中的“记录”，struct用来声明结构体类型时所必须用到的关键字，它向编译系统声明这是一个“结构体类型”。
⒋程序源代码
#include 个
#include
#include
#include
#include
enum
{
NPREF = 2, /* 前缀中词的个数 */
NHASH = 4093, /* 散列表数组的大小 */
MAXGEN = 10000, /* 生成词数的上届 */
MULTIPLIER = 31
};
char NONWORD[] =
typedef struct State State; /*定义新类型State*/
typedef struct Suffix Suffix; /*定义新类型Suffix*/
struct State{ /* 前缀和后缀表 */
char *pref[NPREF]; /* 前缀单词 */
Suffix *suf; /* 后缀表 */
State *next;
};
struct Suffix { /* 后缀表 */
char *word; /* 后缀单词 */
Suffix *next;
};
State *statetab[NHASH];
unsigned int hash(char *s[NPREF]) /* hash函数对数组里所有字符串的拼接做散列*/
{
unsigned int h;
unsigned char *p;
int i;
h = 0;
for (i = 0; i
{
for (p = (unsigned char*)s[i]; *p !="\0"; p++) {
h = MULTIPLIER * h + *p;
}
}
return h % NHASH;
}
State* lookup(char *prefix[NPREF], int create) /*lookup函数向 s p - > p r e f [ ]里存入一个指针。*/
{
int i, h;
State *sp;
h = hash(prefix);
for (sp = statetab[h]; sp != NULL; sp = sp->next)
{
for (i = 0; i
{
if (strcmp(prefix[i], sp->pref[i]) != 0)
{
peak;
}
}
if (NPREF == i)
{
return sp;
}
}
if (create)
{
sp = (State*) malloc(sizeof(State));
if (NULL == sp)
{
perror(
return 0;
}
for (i = 0; i
{
sp->pref[i] = prefix[i];
}
sp->suf = NULL;
sp->next = statetab[h];
statetab[h] = sp;
}
return sp;
}
void addsuffix(State *sp, char* suffix) /*函数a d d s u f f i x把一个新后缀加进去*/
{
Suffix *suf;
suf = (Suffix*)malloc(sizeof(Suffix));
suf->word = suffix;
suf->next = sp->suf;
sp->suf = suf;
}
/* add: 增添后缀单词，更新前缀 */
void add(char *prefix[NPREF], char *suffix)
{
State *sp;
sp = lookup(prefix, 1);
if (NULL == sp)
{
return ;
}
addsuffix(sp, suffix);
memmove(prefix, prefix + 1, (NPREF-1) * sizeof(prefix[0]));
prefix[NPREF-1] = suffix;
}
/* build: 读取输入，建立后缀表 */
void build(char *prefix[NPREF], FILE* fp)
{
char buf[100], fmt[10];
sprintf(fmt,
while(fscanf(fp, fmt, buf) != EOF)
{
add(prefix, strdup(buf));
}
}
/* generate: 汇成行输出 */
void generate(int nwords)
{
State *sp;
Suffix *suf;
char *prefix[NPREF], *w;
int i, nmatch;
srand(time(NULL));
for (i = 0; i
{
prefix[i] = NONWORD;
}
for ( i = 0; i
{
sp = lookup(prefix, 0);
nmatch = 0;
for (suf = sp->suf; suf != NULL; suf = suf->next) {
if (rand()%++nmatch == 0)
w = suf->word;
}
if (strcmp(w, NONWORD) == 0)
peak;
printf(
memmove(prefix, prefix + 1, (NPREF-1) * sizeof(prefix[0])); prefix[NPREF-1] = w;
}
}
int main(int argc, char* argv[])
{
int i, nwords = MAXGEN;
char *prefix[NPREF];
for (i = 0; i
{
prefix[i] = NONWORD;
}
build(prefix,stdin);
add(prefix,NONWORD);
generate(nwords);
return 0;
}
四﹑调试出现的问题
（1） 在不该加分号的地方加了分号
for (i = 0; i
{
for (p = (unsigned char*)s[i]; *p !="\0"; p++) {
h = MULTIPLIER * h + *p;
}
}
由于在第一个for语句后加了分号，使循环体变成了空语句，运行没有成功，执行的是当i=2时的值，而不是i=0,1,2时的值。
（2） 括号不配对。再编写多重循环时，最后落下了一个大括号，一定要注
意括号的配对问题。
（3） 引用数组元素时误用了圆括号。prefix[i] = NONWORD时本来应该引
用方括号，结果引用了圆括号，导致编译错误。
（4）unsigned int h;
unsigned char *p;
int i;
一开始对h 定义的是带符号的整型数，不满足条件,改为不带符号数。 五﹑测试马尔科夫程序（参考《程序设计实践第六章的关于马尔科夫程序的测试》）
第一个测试集由几个很小的文件组成，用于测试边界条件，目标是保证程序对只包含几个词的输入能正确产生输出。对于前缀长度为2的情况，我们用了五个文件，它们分别包含第一个测试集由几个很小的文件组成，用于测试边界条件，目标是保证程序对只包含几个词的输入能正确产生输出。对于前缀长度为2的情况，我们用了五个文件，它们分别包含(一行是一个文件)： （空文件）
a
a b
a b c
a b c d
对于这里的每个文件，程序的输出都应该与输入完全相同。这些测试揭示出几个在表的初始化、生成程序的开始、结束等地方的“超出一个”错误。 第二项测试检验某些必须保持的特征。对于两词前缀的情况，一次运行中输出的每个词, 每个词对、以及每个三词序列都必然也出现在输入里。我们写了一个Aw k程序，用它把原始输入读进一个巨大的数组，构造出所有两个词和三个词的序列的数组，再把马尔可夫程序的输出读入另一个数组，然后对它们做比较。
第三步测试是统计性的，输入由下面的序列构成：
a b c a b c„a b d„
这里每十个a b c有一个a b d。如果随机选择部分工作得很好，那么在输出中c的数目大约应该是d的十倍。我们用freq检验这个性质.
六、C的测试结果
编译成功后，
输入原始文本：Show me your flowchars and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious.
编译后输出文本：Show me your tables,and I shall continue to be mystified.Show me your tables,and I shall continue to be
mystified.Show me your flowchars and conceal your tables,and I won"t usually need your flowcharts;they"ll be obvious.
七﹑编写的C++程序
⒈C++、STL简介
C++是一种使用非常广泛的计算机编程语言。它是一种静态数据类型检查的，支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。
STL STL = Standard Template Lipary，标准模板库. 在C++标准中，STL
被组织为下面的13个头文件：、、、、、、、、、、、和。 STL容器允许我们重复利用已有的实现构造自己的特定类型下的数据结构，通过设置一些模版类，STL容器对最常用的数据结构提供了支持，这些模板的参数允许我们指定容器中元素的数据类型，可以将我们许多重复而乏味的工作简化。
容器部分主要由头文件
,,,,,和组成。对于常用的一些容器和容器适配器（可以看作由其它容器实现的容器），可以通过下表总结一下它们和相应头文件的对应关系。
数据结构 描述 实现头文件
向量(vector) 连续存储的元素
列表(list) 由节点组成的双向链表，每个结点包含着一个元素
双队列(deque) 连续存储的指向不同元素的指针所组成的数组
集合(set) 由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序
多重集合(multiset) 允许存在两个次序相等的元素的集合 栈(stack) 后进先出的值的排列
队列(queue) 先进先出的值的排列
优先队列(priority_queue) 元素的次序是由作用于所存储的值对上的某种谓词决定的的一种队列
映射(map) 由{键，值}对组成的集合，以某种作用于键对上的谓词排列
多重映射(multimap) 允许键对有相等的次序的映射
⒊deque容器，map容器的简介
deque是个动态数组，随机存取任何元素都能在常数时间完成(但次vector)，有在两端增删元素具有较佳的性能，和vector的区别多push_front()
pop_front()，少了capacity() reserve()。实现时，deque是动态的以分段
连续空间组合而成，随时可以增加一段新的空间并连接起来，从而导致reserve没有意义。
S T L还提供了一个map容器，其内部实现基于平衡的树。在map中可以存储关键码—值对。map的实现方式保证，从任何关键码出发提取相关值的操作都是O( logn)。虽然map可能不如O( 1 )的散列表效率高，但是,直接使用它就可以不必写任何代码。
⒋程序分析
S T L提供了deque的模板，记法deque将它指定为以字符串为元素的deque。由于这个类型将在程序里多次出现，在这里用一个typedef声明，将它另外命名为Prefix。声明了一个map类型的变量statetab，它是从前缀到后缀向量的映射。add函数添加单词到后缀序列，更新前缀。函数build使用iostre am库，一次读入一个词。函数generate的作用是成行输出。把所有东西放到一起，装进一个main函数里，它从标准输入流读入，生成至多有指定个数的词序列。程序结束。
⒌C++源程序
//Function: 包含头文件和函数声明
#include //deque
#include //map > #include //vector
#include
#include
#include //rand()
#include //time(NULL)
#include //fin
using namespace std;
const int NPREF = 2; //前缀数
const string NONWORD =
const int MAXGEN = 10000; //最大输出单词数
typedef deque Prefix;
map > statetab; /
void add(Prefix& prefix, const string& s) //添加单词到后缀序列，更新前缀
{
if (prefix.size() == NPREF)
{
statetab[prefix].push_back(s);
prefix.pop_front();
}
prefix.push_back(s);
}
void build(Prefix& prefix, istream& in)
{
string buf;
while (in >> buf)
{
add(prefix, buf);
}
}
void generate(int nwords)
{
srand((unsigned)time(NULL));
Prefix prefix;
for (int i = 0; i
{
add(prefix, NONWORD); //读取单词 //成行输出
}
for (i = 0; i & suf = statetab[prefix]; const string& w = suf[rand() % suf.size()]; if (w == NONWORD) { } peak; } cout
int main() // main函数，从标准输入流读入，生成至多有指定个数的词序列。
{
for (int i = 0; i
} } build(prefix, fin); add(prefix, NONWORD); generate(nwords); fin.close(); statetab.clear(); return 0;
八﹑调试C++出现的问题
⑴在需要加头文件时没有用#include命令去包含文件。一开始把#include 这个引用给落下了。
⑵在需要加分号的地方没加分号。const int MAXGEN = 10000; 是句完整语句，语句后面应该加分号。
⑶编译系统将大写字母和小写字母认为是两个不同的字符。因此，i和I是两个文件名，注意区分。
⑷类的声明应当只包含函数的声明,永远不要进行函数定义(实现)。因为C++不熟悉，我在前面类声明的时候顺便定义了函数，后来编译出现问题。改在后面定义函数。
九﹑C++测试结果
编译成功后，
输入原始文本：Show me your flowchars and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious.
编译后输出文本：Show me your tables,and I won"t usually need your flowcharts;they"ll be obvious.
十﹑两种语言对比
①编程思想C++与C语言最大的区别在于编程思想的截然不同，前者是面向对象（OOP）
的编程语言，而后者则是面向过程的结构化的编程语言。
C语言是结构化和模块化的语言，它是面向过程的。在处理较小规模程序时，程序员用C语言较得心应手。但是当问题比较复杂、程序的规模比较大时，结构化程序设计方法就显出它的不足。C程序的设计者必须细致到设计程序中的每一个细节，准确地考虑到程序运行时每一时刻发生的事情，例如各个变量的值是如何变化的，什么时候应该进行哪些输入，在屏幕上应该输入什么等。这对程序员的要求是比较高的，如果面对的是一个复杂的问题。程序员往往感到力不从心。当初提出结构化程序设计的目的是解决软件设计危机，但是这个目标并没有完全实现。为了解决软件设计危机，在20世纪80年代提出了面向对象的程序设计（Object-Oriented Programming,简称OOP)，在这种形势下，C++应运而生。C++是由贝尔实验室的Bjarne Stroustrup博士及其同事在C语言的基础上开发成功的。C++保留C语言的所有优点，增加了面向对象的机制。C++与C完全兼容，用C语言编写的程序可以不加修改到用于C++。从C++名字可以看出它是对C的扩大，是C的超集。它既可以用于结构化程序设计，又可用于面向对象的程序的设计，因此它是一个功能强大的混合型的程序设计语言。
C++对C的“增强”，表现在两个方面：
（1）在原来面向过程的机制基础上，对C语言的功能做了不少补充。
（2）增加了面向对象的机制。
②关于运行速度
C和C++程序都用带优化的编译器完成编译。C版本的程序是最快的，比C++程序快。C的源代码行数188行，C++的源代码行数91行。C语言最强的地方就是给了程序员对实现方式的完全控制，用它写出的程序趋向于快速。但是这 也有代价，这就是C程序员必须做更多的工作，包括分配和释放存储，建立散列表和链接表，以及其他许多类似的事项。
十一﹑课程设计体会
因为我只学过C语言，所以面对这个马尔科夫链的题目，感到很棘手和困难。我反复仔细阅读了温老师给的实例，后来和同学们讨论了下，才明白是一个什么样的问题。后来上网查询了资料，确定了除了用C和C++编的思路，因为C++跟C有一些相似的地方。后来又看了上学期的课本《C程序设计》（第三章）的后面几章，包括“指针”“结构体与共用体”“文件”等，学习了
散列表，参考了《程序设计实践》，编了C程序，经过多次修改，终于调试成功了。至于C++，学一门语言很困难，尤其还要用它编程序，找了我的一个精通C++的同学给我讲了大概用到的容器，说实话，只准备了半月，时间仓促，C++的大多不会，只能理解这个结构。
我深刻的感受到学一门语言的不易。我深知自己的无知和浅薄。我将继续学习C++，多练习C语言，在编程的路上再接再厉，好好努力。我资质很平庸，很多东西看不懂，就上机试一下，然后再看。笨鸟先飞呗。以前从没听说过马尔科夫链，现在懂了很多这方面的知识。很感谢老师给我们这个题目，虽然很棘手，但是当完成后发现自己学到了东西。