考古中的应用运筹学.docx_第1页
考古中的应用运筹学.docx_第2页
考古中的应用运筹学.docx_第3页
考古中的应用运筹学.docx_第4页
考古中的应用运筹学.docx_第5页
免费预览已结束,剩余1页可下载查看

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

考古中的应用运筹学 6考古中的应用运筹学阅读Flinders Petrie, the Travelling Salesman Problem, and the Beginning of Mathematical Modeling一文有感求是楠1. 弗林德斯皮特里简介威廉马太弗林德斯皮特里,生于1853年,于1942年卒。是一名英国籍的考古学家,埃及学家,文物保护专家,与考古系统方法论先驱者。在考古学界,他被看做是埃及学第一人,他曾在埃及发掘过许多重点考古遗址。他在关于麦伦普塔赫石碑研究以及墓穴断代算法方面有着极其杰出的贡献。本文将着重介绍他在埃及墓穴断代问题上的杰出贡献,他打破了当时完全以考古知识以及文献参考来进行遗址断代的传统思路,将运筹学与统计学的知识巧妙地运用到了考古工作中,从而解决了近千于墓穴年代的排序,这在当时靠传统考古学思路几乎不可能解决的问题。在解决问题中,他主要利用到了运筹学中的旅行商(TSP)问题与海明距离,下面将简单介绍这两个知识点。2.知识概要2.1.旅行商问题(TSP)简介旅行商问题(Traveling Salesman Problem,TSP)又译为旅行推销员问题、货郎担问题,属于NP-Complete问题,也是最基本的路线问题。该问题是在寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig(1959)等人提出。TSP问题规则虽然简单,但在地点数目增多后求解却极为复杂。因其穷举时间杂度按N!增加,当城市数量达到一定时用穷举法很难得出结论。多年来,有许多知名运筹学家在TSP问题上进行了深入的研究,试图找到一个高效的算法来解决TSP问题。 此部分有参考Wikipedia维基百科TSP词条。对于N较小的TSP问题,我们可以适当使用枚举算法,通过计算机搜索来解决,或者利用贪心算法来取最优解。然而当数据数量增加,需要过多运算,从而相对“暴力”的算法并不能解决问题。在这种情况下,可以试图使用途程建构法、途程改善法、合成启发法、遗传算法等方法来解决。2.2.海明距离简介从数学的角度来看,海明距离即两个相同维度的向量中,数字不同的维度数。如(1,1,0,0,1)与(1,0,1,1,1)其中第二,三,四维度数字不同,故这两个向量的海明距离为3。在计算机科学界,两个码字的对应比特取值不同的比特数称为这两个码字的海明距离。在一个有效编码集中,任意两个码字的海明距离的最小值称为该编码集的海明距离。例如,10101和00110从第一位开始依次有第一位、第二、第五位不同,则海明距离为3。用通俗的语言来讲海明距离就是一个描述两个或多个n维向量的“近似度”的量化值,后文中考古学家皮特里在稀疏矩阵中使用到的海明距离也是用于描述各个墓穴间的相似程度,从而进一步推出时间的先后关系。3.皮特里墓穴断代算法介绍弗林德斯皮特里(Flinders Petrie)利用了上述的两个基本算法以及数学建模的思想巧妙地解决了墓室年代测序这一考古学的难题。这个问题的出现于埃及的尼阔达地区(Naqada in Upper Egypt),当时在该地区挖掘出了多达近一千的古埃及墓穴,如何将这些墓穴分类并得到一个较为准确的历史年代顺序变为了一个困扰历史学家与考古学家的难题。按照传统的考古学分析依次来分类并断代这些墓穴在各方面的耗费都是极大的,也就是说这个问题几乎不可能被之前的一些传统考古学方法解决。也是在这时皮特里将运筹学与数学建模的知识应用在了考古中并获得了显著的成效。他的方法基于这样一个考古学常识:在考古学工作中,经常要分析某个房间曾经的居住者是谁这样的问题,比如有三个房间,分别属于英国的三位女王伊丽莎白,玛丽与安娜。单从房间地理位置与房间结构很难得到结论,但如果从房间里面的家具入手来分析将使问题变得简单很多。对于墓穴分析也和分析房间相似,由于不同时期的陶器有着显著区别,皮特里将着重点放到了分析墓穴内的陶器上。皮特里第一步做的就是把陶器分类B,P,F,C,N,W,D,R,L九类,每类有一显著的某一时代特征,比如B类是顶部为黑色的陶器,P类为打磨过的红陶等。在原文中也给出了如下的分类图(见尾页附图.01)。他的第二步是把每个墓穴的陶器分类情况记在一张纸条上,纸条呈长方形,分为10列,每列第一项为墓穴编号,下面9列依次为该墓穴每类陶瓷的情况(见附图.02)。之后把这些纸条按列对齐排布,制成表格(见附图.03)。在完成了上述工作后,将表格抽象为稀疏矩阵A,在该矩阵中每一行代表一个相应的墓穴,每一列则有相应拓展,例如B类陶瓷还具体分为B-22a,B-25c,B-26c,B-57a等具体类型的陶瓷,拿墓穴U-115为例,纸条上B类里的26c,57a,74b分别对应了矩阵中B-26c,B-57a,B-74B这些列,在抽象为矩阵时,U-115行的上述几列记为“1”,剩下没有的行则记为“0”。在稀疏矩阵构建完毕后,用海明距离的思想可以分别计算出出不同墓室间陶瓷的“相似程度”,由于考古学假定陶瓷的“相似程度”与年代的“相近程度”间有正比关系,即两个墓穴里面陶瓷的种类如果越相似,则连个墓穴的年代就越相近。通过稀疏矩阵与海明距离可以得到任意两个墓穴间的“年代距离”,如果把墓穴看做TSP问题中的“城市”,“年代距离”看做城市间距,则断代排序问题便成为了一个TSP问题。与此同时,通过一些考古学知识可以先对数据进行一个预处理排序,例如一个墓穴在考古学中“显然”早于另一个墓穴,则在路径问题中先“游历”早的墓室而后“游历”之后的墓室。在预处理过后,应用旅行商问题(TSP)求解出的最佳路径则就是近似的墓穴年代顺序。虽然当时皮特里也意识到这种方法得到的结论是一个近似(Approximate)结论,进一步的准确结论还需要更进一步的考古研究证明,但是对于当时的考古界来说,把数学应用到考古学并取得巨大成就是一场考古学革命,也因此有人评价他是“现代考古学和埃及学的先驱”甚至有人评价他为“现代考古学之父”。4.心得体会一共12页的PDF翻来覆去的看了一整个下午,也许因为之前接触数学学术性的英文文章并不多,所以在刚开始读的时候比较吃力,许多单词得查,看到不懂的概念还得用Google或者维基百科查找并试图理解。在第一遍读完计划开始写论文时,发现有些细节的方面还是不太理解,因此又读了一遍,不过几个小时的时间可以算是把文章较为清楚地读了下来,对内容也有了理解。本文主要讲述运筹学在考古学中的应用,突然想到曾经高中数学竞赛时竞赛老师闲的时候提到每个学科都可以应用到数学,哪怕是文学与考古学等,记得当时老师提到利用统计与概率分析红楼梦前后并非同一作者所写。当时的我十分惊讶,今天的这篇文章又让我领略到了数学在考古学中的应用,皮特里把运筹学里面的TSP问题应用到考古断代的事例让我感受颇深,数学的巧妙在于它高度的抽象性与普遍性,不论任何领域,用好数学这个强大的工具就会如虎添翼,不论现实世界表面如何复杂,在内部总有一套严密的逻辑关系,就像考古中,表面看似无关联的瓶瓶罐罐,在巧妙的数学建模后竟可以推得近千古墓之间的年代顺序,真的可以用叹为观止形容。我也在想,虽然我并不是数学系的学生,但是在之后的工作中也应该像皮特里一样多加用运筹学的数学观点来看问题,也许会取得事半功倍的效果。最后因为个人翻译水平和数学知识的一些限制文中某些句子并没有深刻理解,如文中有不足之处还望老师海涵。参考文献: 1 Flinders Petrie, the Travelling Salesman Problem, and the B

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论