动态规划的深入讨论论文

动态规划的深入讨论【关键字】动态规划、状态【摘要】本文讨论了一种解决问题十分有效的技术“动态规划”。它较高的解题效率一直受到很大的关注。本文首先对“动态规划”的理论基础进行了讨论。给出了一个用“动态规划”可以解决的问题的两个先决条件“最优子结构”与“无后效性”。接着，讨论了在实际应用中的两个比较常见的问题“动态规划”中状态的选定与存储。再通过以上问题的讨论，引出了“动态规划”的基本思维方法“不做已经做过的工作”以及“动态规划”技术在解决问题中速度惊人的原因“解决了查看中的冗余，达到了速度的极限”。最后，阐述了解决“动态规划”问题的一般步骤，即“思考，计划，应用”。【正文】一引论在信息学竞赛中，特别是最近几年，“动态规划”作为一种解题工具，经常被提及。其应用范围愈来愈广，应用程度也愈来愈深。那么，“动态规划”究竟与其它的算法有什么差别它有什么具体的应用价值呢本文将对此进行讨论。我们先通过一个具体问题认识一下“动态规划”。例1图1中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，我们想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少假设DISX为城市X到E的最短路线的长度；（X表示任意一个城市）MAPI,J表示I，J两个城市间的距离，若MAPI，J0，则两个城市不连通。这个问题我们可以用搜索法来做，程序很容易写出来VARSE未访问的城市集合；FUNCTIONLONGWHO当前访问城市INTEGER求当前访问城市与城市E的最短距离。BEGINIFWHOETHENSEARCH0ELSEBEGINMINMAXINTFORI取遍所有城市DOIF（MAPWHO,I0）ANDIINSETHENBEGINSESEIJMAPWHO,ILONGISESEIIFJMINTHENEXIT砍枝条件IFQIUDEP1NTHEN如果比当前还小，记录BEGINMINALPRQIULPDEP1ENDELSEFORI2TONDO访问所有没访问过的城市IFIINSEANDMAPQIUDEP1I0THENBEGINEXCLUDESE,IQIUDEPISEARCHDEP1,ALMAPQIUDEP1QIUDEPINCLUDESE,IENDENDPROCEDUREPRINT输出数据VARIINTEGERBEGINASSIGNF,OUTPUTFILEREWRITEFWRITELNF,MINFORI1TOLPDOWRITEPRI,CLOSEFENDBEGININIT输入数据SE2N各项值初始化QIU11MINBIGSEARCH2,0寻找最短路径PRINT输出ENDPROGRAMPRO_1_2用“动态规划”的方法解决例1CONSTMAX300最多的城市数INPUTFILEINPUTTXT输入文件名OUTPUTFILEOUTPUTTXT输出文件名BIG1000000最大整数TYPEMAPSARRAY1MAXOFINTEGER地图类型说明VARSESETOFBYTE未访问过的城市集合MAPARRAY1MAXOFMAPS地图变量DISARRAY1MAXOFLONGINT某城市到终点城市的最短距离FRARRAY1MAXOFBYTE动态规划的标识数组BOARRAY1MAXOFBOOLEAN访问过城市标识N,MINTEGER输入数据FTEXT文件变量PROCEDUREINIT初始化过程VARI,J,K,WINTEGERBEGINASSIGNF,INPUTFILE读入数据RESETFREADLNF,N,MFORI1TONDOBEGINNEWMAPIFILLCHARMAPI,SIZEOFMAPI,0ENDFORI1TOMDOBEGINREADLNF,J,K,WMAPJKWENDCLOSEFENDPROCEDUREMAIN“动态规划”递推过程VARI,J,WHOINTEGERMINLONGINT当前最小值BEGINDISN0初始化动态规划数组WHONFILLCHARFR,SIZEOFFR,0FILLCHARBO,SIZEOFBO,TRUEBONFALSEWHILEWHO1DOBEGINFORI1TONDO利用“状态转移方程”递推结果IFMAPIWHO0THENIFFRI0ORDISIDISWHOMAPIWHOTHENBEGINDISIDISWHOMAPIWHOFRIWHOENDMINBIGFORI1TONDOIFBOIANDFRI0ANDDISINDOBEGINWRITEF,I,IFRIENDWRITELNF,NCLOSEFENDBEGININIT输入MAIN求解PRINT输出END例2题目有4个点，他们分别是A、B、C、D，如图4所示，相邻两点有两条连线C2K,C2K11K3表示两条通行的道路，连线上的数字表示道路的长度。我们定义从A到D的所有路径中，长度除以4所得的余数最小的路径是最优路径。说明本题目出自信息学奥林匹克杂志1998年12期。例3题目欧几里德货郎担问题是对平面上的给定的N个点确定一条连结各点的、闭合的游历路线的问题。图5A给出了七个点问题的解。这个问题的一般形式是NP完全的，故其解需要多于多项式的时间JLBENTILEY建议通过只考虑BITONIC旅行路线来简化问题。这种旅行路线即从最左点开始，严格地由左至右直到最右点，然后严格地由右至左直至出发点。图5B示出了同样七个点的最短BITONIC游历。在这个例子中，一个多项式时间的算法是可能的。请描述一个确定最优BITONIC游历的时间的算法。你可以假设任何两2NO个节点的X坐标都不相同。说明本问题出自计算机数据结构和实用算法大全。本文中阐述了这个问题的两个解法“动态规划”解法与搜索解法，程序如下程序PROGRAMPRO_3_1例3的动态规划解法CONSTINPUTFILEINPUTTXT输入文件名OUTPUTFILEOUTPUTTXT输出文件名MAX100最多点的数目BIG10000最大整数值VARFTEXT文件变量POARRAY1MAX,12OFINTEGER记录每个点坐标的数组DISARRAY1MAX,1MAXOFREAL记录动态规划中状态的权值NINTEGER点的总数PROCEDUREINIT初始化过程VARIINTEGERBEGINASSIGNF,INPUTFILE读入数据RESETFREADLNF,NFORI1TONDOREADLNF,POI,1,POI,2CLOSEFENDFUNCTIONLENP1,P2INTEGERREAL求两个点之间的距离BEGINLENSQRTSQRPOP1,1POP2,1SQRPOP1,2POP2,2ENDPROCEDUREMAIN动态规划过程VARI,J,KINTEGERNOWREAL当前最小值BEGINDISN,N0初始化动态规划数组FORIN1DOWNTO1DOBEGINDISI,NLENI,I1DISI1,NDISN,IDISI,NENDFORIN2DOWNTO1DO递推最小值FORJN1DOWNTOI1DOBEGINIFI1NANDX2NDOBEGINOKTRUE根据动态规划递推规则构造打印数组IFX11DISX1,X2DOINCIIFIDISX1,X2DOINCIX2IINCP3DPR3D,P3DX2ENDENDWHILEPRD,PDNDOBEGININCPDPRD,PDPRD,PD11ENDFORI1TOP1DO输出打印数组WRITEF,PR1,I,WRITELNFFORI1TOP2DOWRITEF,PR2,I,CLOSEFENDBEGININIT初始化MAIN动态规划递推最短路径PRINT输出结果ENDPROGRAMPRO_3_2例3的搜索解法CONSTINPUTFILEINPUTTXT输入文件名OUTPUTFILEOUTPUTTXT输出文件名MAX100最多点的数目BIG10000最大整数值VARFTEXT文件变量POARRAY1MAX,12OFINTEGER记录各个点的坐标QIU,PRARRAY1MAXOFBYTE记录搜索过程的数组LPRINTEGER打印数组的长度NINTEGER点的数目MINREAL最短路径的长度PROCEDUREINIT初始化过程VARIINTEGERBEGINASSIGNF,INPUTFILERESETF读入数据READLNF,NFORI1TONDOREADLNF,POI,1,POI,2CLOSEFENDFUNCTIONLENP1,P2INTEGERREAL求两点之间距离的函数BEGINLENSQRTSQRPOP1,1POP2,1SQRPOP1,2POP2,2ENDPROCEDURESEARCHDEP,FR,LASTBYTEALREAL搜索最短路径VARI,PBYTERSREALPROCEDUREDID将第2条路径的长度加入当前的长度VARKBYTEBEGINKFR1RS0PLASTWHILEKIDOBEGINRSRSLENP,KPKINCKENDRSRSLENFR,IENDBEGINIFALMINTHENEXITIFFRNTHENBEGINIFALLENLAST,NKTHENBEGINFORI1TONDOIFIINSANDKUINUMSIDISWHAT,IWHATTHENDIDDEP1,I,SIENDBEGINFORI1TONDO初始化动态规划记录数组BEGINNEWKUINEWDIRIFILLCHARKUI,SIZEOFKUI,FFENDFORI1TONDOKUI0DISI,0FORK1TON1DO为动态规划数组赋值FORWHAT1TONDODID1,0,S1NK60000FORI1TONDOIFDIS0,IKUINUMSIWUWHAT,1THENWRITEF,WUWHAT,1,WRITEF,WUWHAT,2,EXCLUDES,WHATLASTWHATWHATDIRWHATNUMSENDIFAWULAST,2THENWRITEF,ACLOSEFENDBEGININIT初始化PREPARE准备MAIN计算ENDPROGRAMPRO_4_2例4的搜索算法CONSTMAPARRAYAG,AGOFBYTE每两个农场之间的距离0,56,43,71,35,41,36,56,0,54,58,36,79,31,43,54,0,30,20,31,58,71,58,30,0,38,59,75,35,36,20,38,0,44,67,41,79,31,59,44,0,72,36,31,58,75,67,72,0INPUTFILED1INP输入文件名OUTPUTFILEDATA_4_1TXT输出文件名VARFTEXT文件变量NINTEGER任务的数目MINWORD最短距离WUARRAY012,12OFCHAR记录任务的数组DISARRAY012,012OFINTEGER记录每两个任务的连接权值QIU,PRARRAY014OFBYTE搜索中的记录数组SESETOFBYTE未完成的任务的集合PROCEDUREINIT初始化过程VARIINTEGERCHCHARBEGINASSIGNF,INPUTFILERESETFREADLNF,N读入数据FORI1TONDOREADLNF,WUI,1,CH,WUI,2CLOSEFENDPROCEDUREPREPARE准备过程VARI,JINTEGERBEGINWU0,1AWU0,2A求出每两个任务的连接权值FORI0TONDOFORJ0TONDODISI,JMAPWUI,2,WUJ,1ENDPROCEDURESEARCHDEPBYTEALWORD搜索最优得路径VARIBYTEBEGINIFALMINTHENEXITIFDEPN1THENBEGINIFDISQIUN,0ALWUPRI,1THENWRITEF,WUPRI,1,WRITEF,WUPRI,2,ENDIFAWUPRN,2THENWRITEF,ACLOSEFENDBEGININIT初始化PREPARE准备SE112初始化各项搜索应用值QIU00MIN60000SEARCH1,0搜索PRINT输出ENDPROGRAMPRO_4_3例4改进后的搜索算法CONSTMAPARRAYAG,AGOFBYTE每两个农场的距离0,56,43,71,35,41,36,56,0,54,58,36,79,31,43,54,0,30,20,31,58,71,58,30,0,38,59,75,35,36,20,38,0,44,67,41,79,31,59,44,0,72,36,31,58,75,67,72,0INPUTFILED1INP输入文件名OUTPUTFILEDATA_4_1TXT输出文件名TYPEKUSARRAY04095OFWORD记录数组类型SESSETOF112集合类型VARFTEXT文件变量NINTEGER任务的数目MINWORD最短路径的长度BIG,IWORD应用变量WUARRAY012,12OFCHAR记录任务的数组DISARRAY012,012OFINTEGER记录每两个任务的连接权值KUARRAY112OFKUS记录最优权值的数组QIUARRAY113OFBYTE搜索中记录路径的数组SESESPROCEDUREINIT初始化过程VARIINTEGERCHCHARBEGINASSIGNF,INPUTFILERESETFREADLNF,NFORI1TONDO读入数据READLNF,WUI,1,CH,WUI,2CLOSEFENDPROCEDUREPREPARE准备过程VARI,JINTEGERBEGINWU0,1AWU0,2A求出每两个任务的连接权值FORI0TONDOFORJ0TONDODISI,JMAPWUI,2,WUJ,1FORI1TONDO初始化记录数组BEGINNEWKUIFILLCHARKUI,SIZEOFKUI,FFENDBIGKU11ENDFUNCTIONNUMSSESWORD将集合转化为整数的函数VARXWORDABSOLUTESBEGINNUMXDIV2ENDPROCEDURESEARCHDEPBYTEALWORD搜索过程VARIBYTEDWORDBEGINIFALMINTHENEXITIFKUQIUDEP1NUMSENTHENBEGIN边界时直接计算KUQIUDEP1NUMSEDISQIUDEP1,0IFALKUQIUDEP1NUMSEMINDOINCJDMINFORI1TONDOINCD,MAPWUI,1,WUI,2ASSIGNF,OUTPUTFILEREWRITEFWRITELNF,DWRITEF,ADECMIN,DIS0,JLAST0FORI1TONDOBEGINIFWUJ,1WULAST,2THENWRITEF,WUJ,1,WRITEF,WUJ,2,IFINTHENBEGINLASTJEXCLUDESE,JJ1WHILENOTJINSEORKUJNUMSEJDISLAST,JMINDOINCJDECMIN,DISLAST,JENDENDIFWUJ,2ATHENWRITEF,ACLOSEFENDBEGININIT输入PREPARE准备SE1N初始化搜索中应用的各项值MINBIGFORI1TONDOBEGINSE1NIQIU1ISEARCH2,DIS0,I搜索ENDPRINT输出END例5题目一些生物体的复杂结构可以用其基元的序列表示，而一个基元用一个大写英文字母字符串表示。生物学家的一个问题就是将一个这样的长序列分解为基元（字符串）的序列。对于给定的基元的集合P，如果可以从中选出N个基元P1，P2，P3，PN，将它们各自对应的字符串依次连接后得到一个字符串S，称S可以由基元集合P。在从P中挑选基元时，一个基元可以使用多次，也可以不用。例如，序列ABABACABAAB可以由基元集合A，AB，BA，CA，BBC构成。字符串的前K个字符称为该字符串的前缀，其长度为K。请写一个程序，对于输入的基元集合P和字符串T，求出一个可以由基元集合P构成的字符串T的前缀，要求该前缀的长度尽可能长，输出其长度。输入数据有两个输入文件INPUTTXT和DATATXT。INPUTTXT的第一行是基元集合P中基元的数目N（1N100），随后有2N行，每两行描述第一基元，第一行为该基元的长度L1L20。随后一行是一个长度为L的大写英文字符串，表示该基元。每个基元互不相同。文件DATATXT描述要处理的字符串T，每一行行首有一个大写英文字母，最后一行是一个字符”，表示字符串结束。T的长度最小为1，最大不超过500,000。输出数据文件名为OUTPUTTXT。只有一行，是一个数字，表示可以由P构成的T的最长前缀的长度。说明本问题是第八届国际奥林匹克信息学竞赛试题。程序在下面。样例输入、输出为DATA_5TXT，INPUT_5TXT，SOL_5TXT。在子目录DATA下。程序PROGRAMPRO_5例5的动态规划解法CONSTDATAFILEDATATXT文本输入文件名INPUTFILEINPUTTXT基元输入文件名OUTPUTFILEOUTPUTTXT输出文件名TYPEJISRECORD基元记录类型说明LSTBYTE基元长度STSTRING20基元内容ENDVARFTEXT文件变量JIARRAY1100OFJIS基元记录数组CHARRAY021OFCHAR字符记录数组BOARRAY021OFBOOLEAN记录是否为前缀的数组NINTEGER基元数目TOTLONGINT总的字符数BIGLONGINT最长的前缀长度PROCEDUREINIT初始化过程VARIINTEGERBEGINASSIGNF,INPUTFILERESETFREADLNF,N读入每个基元FORI1TONDOBEGINREADLNF,JIILSTREADLNF,JIISTENDCLOSEFENDPROCEDUREMAIN求最长前缀的过程VARI,JINTEGERPROCEDURESEE查看此位是否为前缀VARIBYTEX,YINTEGERBEGINBOJFALSEFORI1TONDOBEGIN考察每个基元XJYJIILSTWHILEY0ANDJIISTYCHXDOBEGINDECXDECYIFXDO如果超过20位不连续或读完文件,结束BEGININCTOTINCJIFJ21THENJ0READLNF,CHJIFCHJTHENBEGINSEEIFBOJTHENBIGTOTENDENDCLOSEFENDPROCEDUREPRINT输出数据BEGINASSIGNF,OUTPUTFILEREWRITEFWRITELNF,BIGCLOSEFENDBEGININIT输入MAIN动态规划求最长前缀PRINT输出END例6题目某公司运进一批箱子，总数为N（1N1000）由“传送带”依次运入，然后在仓库内至多排成P（1P4）列，此排列过程由一台“调度机器”完成（如图8所示）。现在已知运来的箱子最多为M（1M20）种，老板自然想让这些箱子排列的尽可能“漂亮”，即把同一种类的箱子尽量排在一起，以便美观。根据老板的爱好，他的“美观程度”T定义为T（每列依次看到的不同种类数）；所谓“依次看到的不同种类数”即为若第K个与第K1个不同种类，则单记一类。如1231这一列的“依次看到的不同种类数”为4；1223312这一列的“依次看到的不同种类数”为5；即T越小，就越美观，老板就越满意。现已知对每列箱子的个数不做限制，你可以将运来的箱子排在一列，也可以分P列排列。但由于是传送带运输，所以箱子是有次序的，即若A箱子在B箱子前运来，则若A、B排在一列，A必在B的前边。现在请你为“调度机器”编一段程序，使其根据“传送带”发来的箱子信息进行调度，使其排列为P列后的“美观程度”数最小。输入要求输入文件名为“INPUTTXT”。内容有两行，第一行有三个数，依次为N，M，P。第二行有N个数，为传送带运来的箱子种类。第K个数为第K个箱子的种类。输出要求输出文件名为“OUTPUTTXT”。内容为两行，第一行为“美观程度”数T，第二行有N个数，为一种调度方案，即第K个数表示第K个箱子将去往那一列。说明这个问题是我自己编的。程序在下面，样例输入、输出为DATA_6TXT、SOL_6TXT在DATA子目录中。程序PROGRAMPRO_6例6的动态规划解法CONSTFININPUTTXT输入文件名FOUOUTPUTTXT输出文件名TYPEKUSARRAY01160OFBYTE记录数组的类型说明ZISARRAY01160OFINTEGERVARKUARRAY11000OFKUS记录决策的数组SHU,SHU1ARRAY11000OFBYTEZIARRAY01OFZIS记录状态的数组USE1ARRAY020,020,020OFINTEGER记录三个数的组合的数组USE2ARRAY01160,13OFBYTE将一个数转化为三个数组合的数组TOTAL,I,M,N,P,N1INTEGER总数与各种数据FTEXT文件变量INITPROCEDUREINIT初始化VARI,JINTEGERBEGINASSIGNF,FINRESETFREADLNF,N1,M,PFORI1TON1DOREADF,SHU1ISHU1SHU11N1FORI2TON1DOIFSHU1ISHU1I1THENBEGININCNSHUNSHU1IENDCLOSEFENDDIDUSEPROCEDUREDIDUSE将三个数组合的情况转化为一个序数与其对应VARQSARRAY13OFBYTESTOPBYTEI,J,KBYTESERCHPROCEDURESERCHDEPTH,FROMBYTE搜索所有的组合情况VARIBYTEBEGINIFDEPTHSTOP1THENBEGININCTOTALUSE2TOTAL,1QS1USE2TOTAL,2QS2USE2TOTAL,3QS3USE1QS1,QS2,QS3TOTALUSE1QS1,QS3,QS2TOTALUSE1QS2,QS1,QS3TOTALUSE1QS2,QS3,QS1TOTALUSE1QS3,QS1,QS2TOTALUSE1QS3,QS2,QS1TOTALENDELSEFORIFROMTOM1DOBEGINQSDEPTHISERCHDEPTH1,I1ENDENDBEGINTOTAL0FILLCHARQS,SIZEOFQS,0FORI0TOMDOFORJ0TOMDOFORK0TOMDOUSE1I,J,K1USE20,10USE20,20USE20,30USE10,0,00FORSTOP1TOP1DOSERCH1,1ENDMAIN主过程PROCEDUREMAINVARI,J,K,W1,W2,W3INTEGERQARRAY14OFBYTEBEGINFORI1TONDOBEGINNEWKUIENDFILLCHARZI,SIZEOFZI,0动态规划初始化FILLCHARKU1,SIZEOFKU1,0ZI001FILLCHARQ,SIZEOFQ,0FORI2TONDO动态规划求值BEGINFORJ0TOTOTALDOIFZI0J0THENBEGINW10FORK1TO3DOBEGINQKUSE2J,KIFQKSHUI1THENINCQKIFQKSHUITHENW1K