logo资料库

计算机程序设计编程课程设计-马尔可夫链.doc

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.16M 资料格式：doc 举报 版权申诉
第1页 / 共25页
第2页 / 共25页
第3页 / 共25页
第4页 / 共25页
第5页 / 共25页
第6页 / 共25页
第7页 / 共25页
第8页 / 共25页
资料共25页，剩余部分请下载后查看
    计算机程序编程课程设计报告
    引言
    数据结构设计
    程序框架介绍
    程序调试
    程序测试
    两种语言对比
    完整程序源代码：
    计算机程序编程课程设计 (2009-2010-3)  题  学 目：马尔可夫链算法生成随机可读的文本 号：  姓 名：
    计算机程序编程课程设计报告 引言 马尔可夫链，因安德烈·马尔可夫得名，是数学中具有马尔可夫性质的离散 时间随机过程。该过程中，在给定当前知识或信息的情况下，只有当前的状态用 来预测将来，过去（即当前以前的历史状态）对于预测将来（即当前以后的未来 状态）是无关的。 在马尔可夫链的每一步，系统根据概率分布，可以从一个状态变到另一个状 态,也可以保持当前状态。状态的改变叫做过渡，与不同的状态改变相关的概率 叫做过渡概率。随机漫步就是马尔可夫链的例子。随机漫步中每一步的状态是在 图形中的点，每一步可以移动到任何一个相邻的点，在这里移动到每一个点的概 率都是相同的(无论之前漫步路径是如何的)。 马尔可夫在 1906 年首先做出了这类过程。而将此一般化到可数无限状态空 间是由柯尔莫果洛夫在 1936 年给出的。马尔可夫链与布朗运动以及遍历假说这 两个二十世纪初期物理学重要课题是相联系的，但马尔可夫寻求的似乎不仅于数 学动机，名义上是对于纵属事件大数法则的扩张。 物理马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为信号模 型用于熵编码技术，如算术编码（著名的 LZMA 数据压缩算法就使用了马尔可 夫链与类似于算术编码的区间编码）。马尔可夫链也有众多的生物学应用，特别 是人口过程，可以帮助模拟生物人口过程的建模。隐蔽马尔可夫模型还被用于生 物信息学，用以编码区域或基因预测。 马尔可夫链最近的应用是在地理统 计学（geostatistics）中。其中，马尔可夫链用在基于观察数据的二到三维离散变 量的随机模拟。这一应用类似于“克里金”地理统计学（Kriging geostatistics），被 称为是“马尔可夫链地理统计学”。这一马尔可夫链地理统计学方法仍在发展过程 中。 马尔可夫链模型的性质：马尔可夫链是由一个条件分布来表示的 P(Xn + 1 | Xn) 这被称为是随机过程中的“转移概率”。这有时也被称作是“一步转移概率”。 二、三，以及更多步的转移概率可以导自一步转移概率和马尔可夫性质：同样： 这些式子可以通过乘以转移概率并求 k−1 次积分来一般化到任意的将来时间 1
    n+k。边际分布 P(Xn)是在时间为 n 时的状态的分布。初始分布为 P(X0)。该过程 的变化可以用以下的一个时间步幅来描述：这是 Frobenius-Perron equation 的一 个版本。这时可能存在一个或多个状态分布π满足：其中 Y 只是为了便于对变量 积分的一个名义。这样的分布π被称作是“平稳分布”（Stationary Distribution）或 者“稳态分布”（Steady-state Distribution）。一个平稳分布是一个对应于特征根为 1 的条件分布函数的特征方程。平稳分布是否存在，以及如果存在是否唯一，这 是由过程的特定性质决定的。“不可约”是指每一个状态都可来自任意的其它状 态。当存在至少一个状态经过一个固定的时间段后连续返回，则这个过程被称为 是“周期的”。 离散状态空间中的马尔可夫链模型：如果状态空间是有限的，则转移概率分 布可以表示为一个具有(i,j)元素的矩阵，称之为“转移矩阵”：Pij = P(Xn + 1 = i | Xn = j) 对于一个离散状态空间，k 步转移概率的积分即为求和，可以对转移矩阵 求 k 次幂来求得。就是说，如果是一步转移矩阵，就是 k 步转移后的转移矩阵。 平稳分布是一个满足以下方程的向量：在此情况下，稳态分布π*是一个对应于特 征根为 1 的、该转移矩阵的特征向量。如果转移矩阵不可约，并且是非周期的， 则收敛到一个每一列都是不同的平稳分布π*，并且独立于初始分布π。这是由 Perron-Frobenius theorem 所指出的。正的转移矩阵（即矩阵的每一个元素都是正 的）是不可约和非周期的。矩阵被称为是一个随机矩阵，当且仅当这是某个马尔 可夫链中转移概率的矩阵。注意：在上面的定式化中，元素(i,j)是由 j 转移到 i 的概率。有时候一个由元素(i,j)给出的等价的定式化等于由 i 转移到 j 的概率。在 此情况下，转移矩阵仅是这里所给出的转移矩阵的转置。另外，一个系统的平稳 分布是由该转移矩阵的左特征向量给出的，而不是右特征向量。转移概率独立于 过去的特殊况为熟知的 Bernoulli scheme。仅有两个可能状态的 Bernoulli scheme 被熟知为贝努利过程。 现实应用：马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为 信号模型用于熵编码技术，如算法编码。马尔可夫链也有众多的生物学应用，特 别是人口过程，可以帮助模拟生物人口过程的建模。隐蔽马尔可夫模型还被用于 生物信息学，用以编码区域或基因预测。 马尔可夫链最近的应用是在地理统计 学（geostatistics）中。其中，马尔可夫链用在基于观察数据的二到三维离散变量 2
    的随机模拟。这一应用类似于“克里金”地理统计学（Kriging geostatistics），被称 为是“马尔可夫链地理统计学”。这一马尔可夫链地理统计学方法仍在发展过程 中。人力资源中的应用：马尔可夫链模型主要是分析一个人在某一阶段内由一个 职位调到另一个职位的可能性，即调动的概率。该模型的一个基本假设就是，过 去的内部人事变动的模式和概率与未来的趋势大体相一致。实际上，这种方法是 要分析企业内部人力资源的流动趋势和概率，如升迁、转职、调配或离职等方面 的情况，以便为内部的人力资源的调配提供依据。 它的基本思想是：通过发现 过去组织人事变动的规律，以推测组织在未来人员的供给情况。马尔可夫链模型 通常是分几个时期收集数据，然后再得出平均值，用这些数据代表每一种职位中 人员变动的频率，就可以推测出人员变动情况。具体做法是：将计划初期每一种 工作的人数量与每一种工作的人员变动概率相乘，然后纵向相加，即得到组织内 部未来劳动力的净供给量。其基本表达式为：Ni(t)：t 时间内 I 类人员数量； Pji：人员从 j 类向 I 类转移的转移率；Vi(t)：在时间（t-1,t）I 类所补充的人员数。 企业人员的变动有调出、调入、平调、晋升与降级五种。表 3 假设一家零售公 司在 1999 至 2000 年间各类人员的变动情况。年初商店经理有 12 人，在当年期 间平均 90％的商店经理仍在商店内，10％的商店经理离职，期初 36 位经理助理 有 11％晋升到经理，83％留在原来的职务，6％离职；如果人员的变动频率是相 对稳定的，那么在 2000 年留在经理职位上有 11 人（12×90％），另外，经理助理 中有 4 人（36×83％）晋升到经理职位，最后经理的总数是 15 人（11＋4）。可以 根据这一矩阵得到其他人员的供给情况，也可以计算出其后各个时期的预测结 果。 主要参考文献： A.A. Markov. "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom drug ot druga". universitete, 2-ya seriya, tom 15, pp 135-156, 1906. A.A. Markov. "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons, 1971. Leo Breiman. Probability. Original edition published by Addison-Wesley, 1968; ISBN Industrial and Applied Mathematics, 1992. reprinted by Society for 3
    0-89871-296-3. (See Chapter 7.) J.L. Doob. Stochastic Processes. New York: John Wiley and Sons, 1953. ISBN 0-471-52369-0. 数据结构设计 这里的数据结构主要是处理每次查找字符串的过程，在 C 程序中采用了 hashtable，在 C++中采用了 C++的 map 容器，即 RB-TREE（因为 SGI-STL 的 map 底层实现是 RB-TREE）。 Hashtable 是根据关键码值(Key value)而直接进行访问的数据结构。也就是 说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这 个映射函数叫做散列函数，存放记录的数组叫做散列表。Knuth 在 TAOCP 第三 卷查找与排序中专门对其数学性能做了大量的分析。 基本概念：  若结构中存在关键字和 K 相等的记录，则必定在 f(K)的存储位置上。由 此，不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数(Hash function)，按这个思想建立的表为散列表。  对不同的关键字可能得到同一散列地址，即 key1≠key2，而 f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函 数来说称做同义词。综上所述，根据散列函数 H(key)和处理冲突的方法将 一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地 址集中的“象”作为记录在表中的存储位置，这种表便称为散列表，这一映 象过程称为散列造表或散列，所得的存储位置称散列地址。  若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何 一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从 而减少冲突。 常用的构造散列函数的方法： 散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元 素将被更快地定位 1. 直接定址法：取关键字或关键字的某个线性函数值为散列地址。即 H(key)=key 或 H(key) = a·key + b，其中 a 和 b 为常数（这种散列函数叫做 自身函数） 2. 数字分析法 3. 平方取中法 4
    4. 折叠法 5. 随机数法 6. 除留余数法：取关键字被某个不大于散列表表长 m 的数 p 除后所得的余 数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取 模，也可在折叠、平方取中等运算之后取模。对 p 的选择很重要，一般取 素数或 m，若 p 选的不好，容易产生同义词。 处理冲突的方法 1. 开放定址法；Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中 H(key) 为散列函数，m 为散列表长，di 为增量序列，可有下列三种取法： 1. di=1,2,3,…, m-1，称线性探测再散列； 2. di=1^2, (-1)^2, 2^2,(-2)^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再 散列; 3. di=伪随机数序列，称伪随机探测再散列。 == 2. 再散列法：Hi=RHi(key), i=1,2,…,k RHi 均是不同的散列函数，即在同义词 产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法 不易产生“聚集”，但增加了计算时间。 3. 链地址法（拉链法） 4. 建立一个公共溢出区 查找的性能分析 散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地 址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲 突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是 给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均 查找长度来衡量。 查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找 效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也 就是影响查找效率的因素。影响产生冲突多少有以下三个因素： 1. 散列函数是否均匀； 2. 处理冲突的方法； 3. 散列表的装填因子。 散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度，α是散列 表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比， 所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表 中的元素较少，产生冲突的可能性就越小。 实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法 有不同的函数。 5
    有关 hashtable 的经典参考文献： 1.Charles E. Leiserson, Amortized Algorithms, Table Doubling, Potential Method Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms - Fall 2005 2. Donald Knuth (1998). The Art of Computer Programming'. 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 513–558. ISBN 0-201-89685-0. 3. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (second ed.). MIT Press and McGraw-Hill. 221–252. ISBN 978-0-262-53196-2. 4. Bret Mulvey, Hash Functions. Accessed April 11, 2009 5. Thomas Wang (1997), Prime Double Hash Table. Accessed April 11, 2009 6. Askitis, Nikolas; Zobel, Justin (2005). Cache-conscious Collision Resolution in String Hash Tables. 3772. 91–102. doi:10.1007/11575832_11. ISBN 1721172558. http://www.springerlink.com/content/b61721172558qt03/. 7. Askitis, Nikolas; Sinha, Ranjan (2010). Engineering scalable, cache and space efficient tries for strings. doi:10.1007/s00778-010-0183-9. ISBN 1066-8888 (Print) 0949-877X (Online). http://www.springerlink.com/content/86574173183j6565/. 8. Askitis, Nikolas (2009). Fast and Compact Hash Tables for Integer Keys. 91. 113–122. ISBN 978-1-920682-72-9. http://crpit.com/confpapers/CRPITV91Askitis.pdf. 9.Erik Demaine, Jeff Lind. 6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003. http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf 10. Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990). Data Structures Using C. Prentice Hall. pp. 456–461, pp. 472. ISBN 0-13-199746-7. 11.Celis, Pedro (1986). Robin Hood hashing. Technical Report Computer Science Department, University of Waterloo CS-86-14. 12. Viola, Alfredo (October 2005). "Exact distribution of individual displacements in linear probing hashing". Transactions on Algorithms (TALG) (ACM) 1 (2,): 214–242. doi:10.1145/1103963.1103965. ISSN:1549-6325. 13. Celis, Pedro (March, 1988). External Robin Hood Hashing. Technical Report Computer Science Department, Indiana University TR246. 14. Herlihy, Maurice and Shavit, Nir and Tzafrir, Moran (2008). "Hopscotch Hashing". DISC '08: Proceedings of the 22nd international symposium on Distributed Computing. Arcachon, France: Springer-Verlag. pp. 350–364. 6
    15. Litwin, Witold (1980). "Linear hashing: A new tool for file and table addressing". Proc. 6th Conference on Very Large Databases. pp. 212–223. 16. Doug Dunham. CS 4521 Lecture Notes. University of Minnesota Duluth. Theorems 11.2, 11.6. Last modified 21 April 2009. 17. Crosby and Wallach's Denial of Service via Algorithmic Complexity Attacks. 18. Mehta, Dinesh P.; Sahni, Sartaj. Handbook of Datastructures and Applications. pp. 9–15. ISBN 1584884355. RB-TREE（又叫红黑树）红黑树是一种自平衡二叉查找树，是在计算器科 学中用到的一种数据结构，典型的用途是实现关联数组。它是在 1972 年由鲁道 夫•贝尔发明的，他称之为"对称二叉 B 树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于 1978 年写的一篇论文中获得的。它是复杂的，但它的操作 有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在 O(log n)时间 内做查找，插入和删除，这里的 n 是树中元素的数目。红黑树和 AVL 树一样都 对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使 它们在时间敏感的应用如实时应用(real time application)中有价值，而且使它们有 在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何 中使用的很多数据结构都可以基于红黑树。红黑树在函数式编程中也特别有用， 在这里它们是最常用的持久数据结构之一，它们用来构造关联数组和集合，在突 变之后它们能保持为以前的版本。除了 O(log n)的时间之外，红黑树的持久版本 对每次插入或删除需要 O(log n)的空间。红黑树是 2-3-4 树的一种等同。换句话 说，对于每个 2-3-4 树，都存在至少一个数据元素是同样次序的红黑树。在 2-3-4 树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得 2-3-4 树 成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树 之前介绍 2-3-4 树的原因，尽管 2-3-4 树在实践中不经常使用。 RB-TREE 的主要参看文献（最好的是 Princeton 的 pdf 课件）： 1. Rudolf Bayer (1972). "Symmetric binary B-Trees: Data structure and maintenance algorithms". Acta Informatica 1 (4): 290--306. doi:10.1007/BF00289509. http://www.springerlink.com/content/qh51m2014673513j/. 2. Leonidas J. Guibas and Robert Sedgewick (1978). "A Dichromatic Framework for Balanced Trees". Proceedings of the 19th Annual Symposium on Foundations of 7
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料