论文部分内容阅读
<正>设图G=(V,E)是一个带权有向连通图,如果把顶点集合V划分成k个互不相交的子集Vi(2≤k≤n,1≤i≤k),使得E中的任何一条边(u,v),必有u∈Vi,v∈Vi+m(1≤i<k,1<i+m≤k),则称图G为多段图,称s∈V1为源点,t∈Vk为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。分支限界法常是用最小耗费(最大效益)或以广度优先的方法搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树,常见的有子集树和排列树。在分支限界法中的分支结