第38卷第4期
2006年12月郑州大学学报(理学版)J.ofZhengzhouUniv.(Nat.Sci.Ed.)Vol138No14Dec12006
一类多投递员中国邮路问题动态规划模型研究
费 蓉, 崔杜武, 王战敏, 梁 琨
(西安理工大学计算机科学与工程学院 西安710048)
摘要:采用动态规划决策思想,针对KPCPP问题,建立了一套算法体系.,通过弧点转换算法,构建了该问题适用于决策的模型.在此模型基础上,,得到的模型符合多阶段决策过程需求;在动态规划的基础上,动态规划模型求解,.
关键词:动态规划;KPCPP;KMDPA算法
中图分类号:O412:1671-6841(2006)04-0102-05
0 引言
当邮递员数目k≥2时,同时投递邮件,全程街道均投递,任务完成后返回邮局,如何分配使完成任务时间最短?该问题是在中国邮递员问题[1-2]的基础上发展起来的,此处记为KPCPP(kpostmenChinesepostmanproblem)[3].
动态规划实质是分治思想和解决冗余[4-5].文献[4]已证明一般情形KPCPP问题是NPC[6]的.本文针对KPCPP问题,结合动态规划的决策过程思想,提出了一个新的搜索算法KMDPA(kpostmendecisionprocessalgorithm),实现了该类问题的动态规划思想求解.针对决策思想不能直接求解该问题,提出了弧点转换算法CEPA(convertedgetopointalgorithm),使其模型能够转换为适用于决策的模型.对于求解可应用于决策的模型,提出了多阶段决策过程模型转换算法MDPMCA(multistepdecisionprocessmodelconvertalgorithm)[7],使该模型符合多阶段决策过程需求,可用KMDPA算法求解此类KPCPP问题.1 邮递员数目k与v0相关的KPCPP问题
1.1 基本定义
定义1 设vi为节点,1≤i≤n,设节点集V={v1,v2,…,vn};若vi、vj之间有弧连接,定义该弧为aij,设弧集A={aij|1≤i≤n,1≤j≤n,i≠j};定义弧aij长为wij,设权值集合W={wij|1≤i
i≠j n
定义2 设xkm为第k阶段的状态变量,设Xk为第k阶段的允许状态集合,即Xk={xkm|1≤m≤n}.定义3 设xn+1为终端变量,Xn+1为终端集合.
定义4 定义一个动态规划函数模型(k,xk,uk(xk),dk,fk(xk)),其中,k为阶段数,按过程的演化划分;xk为状态数,由各段的位置确定;uk(xk)表示为从各个状态出发的走向;指标函数dk(xk,uk(xk))为相邻两状态间的距离;最优值函数fk(xk)是由xk出发到终点的最短距离;基本方程如下:
xk+1=uk(xk);dkn=(xk,uk,xk+1,…,xn+1)=∑dj(xj,uj);j=kn
收稿日期:20060501
作者简介:费蓉(1980-),女,博士研究生,主要从事决策分析与支持、最优化理论及虚拟现实研究;E2mail:annyfei@hotmail.com.
第4期费蓉等:一类多投递员中国邮路问题动态规划模型研究
fk(xk)=min[dk(xk,uk(xk))+fk+1(xk+1)],k=n,…,1;fn+1(xn+1)=0.103
3已知使指标函数dkn达到最优值的策略是从k开始的后步子过程的最优策略,记作pkn={uk3,…,un3},
3333p1n是全过程的最优策略.从初始状态x1(=x1)出发,过程按照最优策略p1n和状态转移方程演变经历所得的状态序列{x13,x23,…,xn3}称最优轨线.综上,对该问题作相关定义:
定义5 对于邮递员数目k与v0相关的KPCPP问题,使指标函数dkn达到相对最优值的策略是全过程
3的相对最优策略,过程按照最优策略pkn和状态转移方程演变经历所得的状态序列称为相对最优轨线.
定义6 对于邮递员数目k与v0相关的KPCPP问题,定义M为其dkn阈值,规定对任何W(G),总有W(G)≥kM,使最大指标函数dkn对应的|dkn-M|达到最小的轨线组,.1.2 问题描述
根据上述定义,对邮递员数目k与v0相关的KPCPP连通无向网络G=〈V,A;W〉,对每一弧aij,有一权wij.从v0K数数目相一致,同时沿网络中的弧行走k条路线,,,这样k条路线称为投递路线,耗时最少的投递路线,2 ,适用于理论上的分析.在实际应用中,许多问题的阶段划分并不明显.对于KPCPP问题,可采用如下算法,进行标准动态规划模型的近似转换.
2.1 算法1(CEPA算法)
Step0 定义弧aij为函数ak(vi,vj)=wij,1≤k≤m,m为G中弧数目;
Step1 从k=1开始,逐一搜索弧函数,直到所有具有公共端点的弧函数均被连接,G→G′转换完毕,否则,执行Step2;
Step2 取ak作为G′的一个顶点;找与其有公共端点的弧函数as(vi,vl)=wil,连接两点,记作弧vks,权值eks=0.
重新定义网络G′=〈A,V;E〉,其中,顶点集A={ak(vi,vj)|1≤i≤n,1≤j≤n,i≠j,1≤k≤m},弧集V={vij|1≤i≤m,1≤j≤m,i≠j},权值集E={els|1≤l≤m,1≤s≤m,l≠s}.
下面给出一个经过算法1处理的实例,见图1.图1经过算法1转化为图2
.
性质1 算法执行完毕后,必不存在弧vij,满足G′中的弧函数ai、aj对应在网络G中的两弧不相连,1≤i
证明 已知图G中两弧ai与aj不相连,设存在弧vij,1≤i
104郑州大学学报(理学版)第38卷ai,1≤i
2.2 算法2(MDPMCA算法)
算法1完成了G中弧和点的转化,把对弧的遍历问题,转换为对点的搜索,对网络G′,这一算法具有普遍意义.但在求解KPCPP问题上,网络G′不适于动态规划分段决策思想.我们提出多阶段决策过程模型转换算法MDPMCA,使该模型符合多阶段决策过程需求,能够进行动态求解.其中涉及到的附属状态变量,是指与原状态变量属性保持一致,因此,遍历附属状态与遍历原状态具有一致性.
MDPMCA算法描述如下:
Step0 设定终端集合Xn+1初始为空;
Step1 在网络G′中,找以出发点v0为端点的弧函数,n;
Step2 执行第1步,直到A中无以v0Step3 取Xn+1中一个状态变量ak,Xn+1中其余任意状态变量aj,作为终结状态;若Xn+1,k;
Step4 对状态ak,,加入第2阶段的允许状态集,同时,搜索在G′,;
Step5 ,模型Nk中其余每一阶段的允许状态集合,均为网络G′所有节点集合,N中为属性不一致的所有状态集合;此种允许状态集合共分为2(m-2)个;
Step6 依照网络G′连接路径分阶段连接模型中所有路径,对于附属状态,属性一致的状态变量之间加弧连接;多阶段决策过程模型Nk建立完毕;
Step7 重复执行3～6步,直到终端集合Xn+1内所有状态变量均已做过第一阶段初始状态,所有模型建立完毕,该算法终止.
至此,我们建立起所有用于MDPMCA算法求解该问题的多阶段决策过程模型Nk.针对多阶段决策过程模型Nk,我们对邮递员数目k与v0相关的KPCPP问题描述如下:
多阶段决策过程模型Nk=〈A,V;E〉,令z=2m(m-1)+2(m对应为网络G′中节点数),其中,A={ap(vi,vj)|1≤i≤n,1≤j≤n,i≠j,1≤p≤z},V={vij|1≤i≤z,1≤j≤z,i≠j},E={els|1≤l≤z,1≤s≤z,l≠s};求解一组包含k条轨线的相对最优轨线组,其中,k值与以v0为顶点的状态变量数目具有一致性,使从终端集合Xn+1中的状态变量出发遍历所有状态变量再回终端集合Xn+1,总耗时最少.
算法2执行结束后,对于任意多阶段决策过程模型Xk,根据算法第2步,存在4个独立的允许状态集,根据算法第4步,允许状态集合共分为2(m-2)个,满足每个允许状态集合内部不存在通路,共有2m个独立允许状态集.因此,根据多段决策分段原则,一定可以分成阶段数k=2m-1的多阶段决策过程模型.
性质2 对建好的ΠNk,总可分为2m-1个阶段.
2.3 算法3(KMDPA算法)
引理1 任何W(G),总有sw/k为其最高阈值.
证明 反证法.设存在一数m>sw/k,满足最高限定测试条件,根据定义6,总有W(G)≥km.存在一种情况,当W(G)=sw时,即所有弧无重复,K条路径平均分配,此时,存在正数L=sw/k使得W(G)=kL,满足定义6,即L亦可做阈值,已知L>m,故假设不成立,证毕.
此处,取M=sw/k.
定理1 对图G,其相对最优轨线组的充分必要条件是,该轨线组对应的最大指标函数dkn无限趋近于sw/k,即|max(dkn)-sw/k∣最小.
证明 必要性.对于原图G,如果一组轨线为该图对应的相对最优轨线组,则有|max(dkn)-sw/k|最小.否则,可以找到其他轨线组对应的最大dk′n无限趋近于sw/k,这与定义6相矛盾.
充分性.如果有|max(dkn)-sw/k|最小,即该组轨线对应的最大dkn无限趋近于sw/k,据此,我们得出,该
(d)-sw/k|并非最轨线的W(G)≤kdkn,即该W(G)无限趋近于sw.假设该图存在另一相对最优轨线组,其|maxkn
第4期费蓉等:一类多投递员中国邮路问题动态规划模型研究105小,则该轨线的W(G)′较之W(G),存在两种情况:
1)当d′′kn>dkn时,对dkn而言,存在耗时更少的dkn,该d′kn对应的轨线组并非耗时最少,矛盾.
2)当d′′knsw/k时,因d′kn
综上,可知充分性得证.证毕.
推论(k值与以v0为顶点的弧数目保持一致的KPCPP问题优化条件) 对于Nk组中的每个节点
),…,(ak,…))为从原图G中的v0出发回到v0的轨线组,某一轨线组时间消耗ap(vi,vj),设Groopk((a1,…
最少的充要条件是对所有包含轨线,其|max(dkn)-sw/k∣相对其他轨线组最小.
根据定理1及其推论,结合动态规划中的决策思想,以下提出一个搜索算法求解邮递员数目k与v0相关的KPCPP问题,提出该算法所具备的一些性质,KMDPA算法描述如下:
Step0 定义集合Xl为空,取Xn+1中非ak,放入Xl;
Step1 取以akNk,i=1;
Step2 从第i阶段始端ak,
1)若第i+12且非ak附属状态变量,满足fk(xk)=min[dk(xk,uk(xk))+fk+)],;
2)2,选取ak附属状态变量的状态为下一策略走向;
Step3 若该状态变量与前一状态变量al公共端点为ak的终止端点,则ekl=ak,记录ak、al各遍历1次,否则,ekl=0,记录al遍历1次,di=ekl+ak;
Step4 i++;当i≤2(m+1)时,执行2、3步,否则,转入5步;
Step5 取dkn最小值的决策,找出该轨线;
Step6 比较dkn与sw/k,dkn=sw/k时,停止,否则,若前一循环过程的dkn=0,转6步,否则,比较该dkn与前一循环过程的dkn:
1)两值均>sw/k或两值均
2)一值sw>/k同时另一值
Step7 对Nk,拆去Xl中一个未标记的状态变量及其连接通路,标记该状态变量已拆过,重组Nk′,对其执行1～6步;
Step8 判断本组模型是否搜索完毕,若未结束,搜索保留dkn的对应轨线,对其未包含的状态变量,标记为已拆过,其余状态变量还原为未标记,遍历次数清零,执行1～7步;否则,转9步;
Step9 判断所有组序是否搜索完毕,若未结束,对Nk调换顺序,重复执行1～8步,否则,转10步;Step10 比较各组结果,每组结果中的最长dkn进行比较,取其min,选定该组策略对应轨线为相对最优轨线.
至此,我们最终记录的dkn组及其对应轨线即为所求,算法完备.
定理2 算法结束后,对于最优轨线组,保证其节点完备性,同时满足k值与以v0为顶点的弧数目保持一致的KPCPP问题优化条件.
证明 算法结束后,如果存在节点未被访问,则其一定在某模型重组过程中被拆除,未经遍历.根据算法Step8,搜索保留dkn的对应轨线,对其未包含的状态变量,标记为已拆过,其余状态变量还原为未标记,可知每个状态变量,若未遍历,在以下模型重建过程中,必不能拆除,根据算法2、3步,在其后的遍历过程必被遍历到,故当算法结束,必不存在节点未被访问.
106郑州大学学报(理学版)第38卷算法结束后,对求得的相对最优轨线组,若存在|max(dkn)-sw/k|并非相对最小,根据算法6步可知,因还存在判断条件为真,算法不能结束,这与算法矛盾.故算法结束后,满足k值与以v0为顶点的弧数目保持一致的KPCPP问题优化条件.证毕.
214 算法的有效性验证
应用上述算法体系,得到了图1的相对最优路径组:k=2,v0-v1-v2-v3-v0,v0-v1-v3-v0.
3 结束语
本文通过算法体系,建立起邮递员数目k与v0相关的KPCPPNk,首次在动态规划基础上提出了KMDPA算法,、交通运输等众多领域.度的问题[8],在以后的研究中,.
参考文献:
[1] RICHARDJ.Med.Beijing:PublishingHouseofElectronicsIndustry,2005.
):14225.[2] KOHKM,TOnpostmanproblem[J].NanyangUniversityJournal,1974/1975,(Ⅷ/Ⅸ
[3] 王权禾.[J].中国科技大学学报,1995,4:4542460.
[4] BONDYJA,MURTYUSR.Graphtheorywithapplications[M].TheMacmillanPressLtd,1976.
[5] BELLMANRE,DREYFUSSE.Applieddynamicprogramming[M].PrincetonUniversityPress,Princeton,New
Jersey,1962.
[6] BOR2RENL,YUNG2CHUANL,TSUNGY.Implementationofathree2phasehigh2power2factorrectifierwithNPCto2
pology[J].TransactionsonAerospaceandElectronicSystems,2004,40(1):1802189.
[7] 王士同.多阶段模糊决策问题的模糊启发式搜索算法FDA[J].计算机研究与发展,1998,35(7):6522656.
[8] SARTAJS.Datastructures,algorithms,andapplicationsinC++[M].Beijing:ChinaMachinePress,1999.
MotionPlanningAlgorithmsforCertainManyPostmen
ChinesePostmenProblems
FEIRong, CUIDu2wu, WANGZhan2min, LIANGKun
(SchoolofComputerScienceandEngineering,Xi’anUniversityofTechnology,
Xi’an710048,China)
Abstract:AmotionplanningalgorithmKMDPA(kpostmendecisionprocessalgorithm)ispresen2tedinordertosolveakindofmanypostmenChineseproblemsinwhichkisequaltothenumberoftheedgesofstartvertex.TheCEPA(convertedgetopointalgorithm)thatmakesthemodelofthismanypostmenChinesepostmenproblemapplytodecision2makingisgiven,andthen,MD2PMCA(multistepdecisionprocessmodelconvertalgorithm)isgiventomakethismodelmeetthedemandofthemultistepdecisionprocess.KMDPAcanbeusedtosolvetheproblem.Intheend,thevalidityandtheoryofthisalgorithmareproved.
Keywords:motionplan;KPCPP;KMDPA