时间依赖网络中国邮路问题

中国邮路问题是图论中的经典问题,得到了深入的研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,时间依赖网络问题的研究具有更为重要的现实应用意义。本文首次提出了时间依赖网络中的中国邮路问题,建立了该问题的整数线性规划模型,并对该模型的上界进行了分析,最后给出了网络应用实例。     

一类电路布线问题的分支限界算法

分支限界策略对很多实际问题是重要和有效的。论文首先提出了一类电路布线问题,然后给出了解决该问题的分支限界算法并分析了所给出算法的复杂度。实验结果验证了所提出方法的有效性。     

时间窗-时间依赖中国邮路问题的图转换算法

研究时间依赖网络上带时间窗的中国邮路问题（TDCPPTW）,该问题是对中国邮路问题的扩展,它考虑了时间因素,在实时软件测试等当前许多具有时间依赖性质的热门问题中更具优势。首先提出了一个新的图转换算法;然后,从理论上证明了该转换算法能够在伪多项式时间内将TDCPPTW转换为相应的广义乡村邮路问题（GRPP）;最后,建立了一个0/1线性整数规划模型用于求解转换后的问题,并对随机生成的12个实例进行了求解实验。     

二层SA/GA算法解决时间依赖中国邮路问题

中国邮路问题是图论中的经典问题,得到了深入研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,研究时间依赖网络中的问题具有更为重要的现实应用意义。首先给出了时间依赖中国邮路问题的定义,然后证明了传统中国邮路问题的定理在时间依赖中国邮路问题中不成立,最后设计了二层SA/GA算法(模拟退火/遗传算法)来解决该问题,对随机产生的实例进行了测试,并根据问题下界对算法结果进行了分析。     

基于Visual C++的旅行售货员问题的分支限界算法

旅行售货员问题是经典的NP问题。本文对旅行售货员问题的分支限界算法进行了分析,给出了算法过程,并用Visual C++实现该算法。     

用分支限界法求解旅行商问题

用分支限界法求解旅行商问题,用C 语言编程实现     

用分支限界法求解旅行商问题

用分支限界法求解旅行商问题,用C++语言编程实现     

时变网络中国邮路问题的时间自动机模型

基于时间自动机理论,提出了时间窗、时间依赖服务代价以及时间依赖旅行时间这3类时变网络中国邮路问题的统一建模的语义模型和求解方法.首先,将中国邮路问题可行解条件和时变参数与时间自动机联系起来,建立了3类问题的统一时间自动机系统(timed automata system,简称TAS)模型;然后,将时变网络中国邮路问题归结为TAS模型上的一系列可达性判定问题,并利用形式化验证算法给出了有效的求解方法.由于TAS模型中存在O(|A|+|AR|+1)个时间自动机,限制了问题求解规模.为此,通过扩展时间自动机语义,提出了TAS模型中的时间自动机合并策略,进而将TAS模型转换为一个广义时间自动机(GTA)模型.基于GTA模型,利用UPPAAL工具对9组、共54个随机算例进行实验.实验结果表明,该方法在求解精度上明显优于运筹学领域的方法.     

带有度约束的最小耗费生成树的分支限界算法

最小耗费生成树算法已很成熟,如Dijkstra's 算法,Prim’s 算法等。但在实际应用中我们常会碰到一类问题,对最小耗费生成树中每个结点的度数有所限制。这便是带有度约束bi(i=1,2,…,n)的最小耗费生成树(DCMCST)问题,在管道系统、通信、计算机网络中均会遇到这样的问题。本文提出一种分枝界限算法来产生DCMCST。     

多跳无线网络中基于分支限界法的广播算法

现有的广播算法一般采用分层的方法构建近似的最多叶子最短生成树作为广播树。分析此类算法存在的不足,提出利用分支限界的思想建立最多叶子最短生成树引导广播操作的方法。分析和仿真结果表明,与基于分层的广播算法相比,基于分支限界法的广播算法具有更低的转发比且不增加广播树的深度,能更有效地节省带宽和能量资源。     

基于一种新的边权编码方案的中国邮递员问题的DNA计算模型

权编码方法是DNA计算中一个重要且有挑战性的问题.设计了一种新的用于表示赋权图中边权的DNA编码方案,给出了用该方案求解中国邮递员问题的DNA算法,并利用Markov链分析了DNA算法中生成各种路径的随机过程.对于任一赋权图G=(V,E),首先通过边到点映射把它转换为广义边图G′=(V′,E′).图G的每条边e\\-i被分别映射为图G′的一个顶点v′\\-i. 若G中e\\-i与e\\-j邻接,则连接G′中v′\\-i和v′\\-j. 若G中v\\-i为奇顶点,则在与v\\-i关联的边对应的G′的顶点上添加自环.用于编码顶点v′\\-i的DNA串s\\-i的长度等于边e\\-i的权值.用于编码边v′\\-iv′\\-j的DNA串s\\-\\{ij\\}为s\\-i的后半部分与s\\-j的前半部分并置后的逆补.所提出的DNA编码方案具有易于编码、易于推广且错误率低的特点.该工作可提高DNA计算中表示和处理数值的能力,扩展DNA计算求解最优化问题的范围.     

石油传输网络最少增压器问题的回溯与分支限界解法

回溯法和分支限界法是用于解决诸多问题的重要而有效的方法。本文首先提出石油传输网络中的最少增压器问题,然后介绍了基于回溯法和分支限界法的两种有效算法,最后对这两种算法进行了比较和讨论。实验结果验证了算法的有效性。     

A constructive heuristic for the Undirected Rural Postman Problem

This paper describes a constructive heuristic for the well-known Undirected Rural Postman Problem. At each iteration, the procedure inserts a connected component of the required edges and performs a local postoptimization. Computational results on a set of benchmark instances with up to 350 vertices show that the proposed procedure is competitive with the classical Frederickson procedure. Its use is recommended when a high-quality solution is needed in a short amount of time (e.g., in laser plotter applications).     

The directed Chinese Postman Problem

The Chinese Postman Problem has many applications, including robot exploration, and analysing interactive system and Web site usability. This paper reviews the wide range of applications of the problem and presents complete, executable code to solve it for the case of directed multigraphs. A variation called the ‘open Chinese Postman Problem’ is also introduced and solved. Although optimizations are possible, no substantially better algorithms are likely. Copyright © 2003 John Wiley & Sons, Ltd.     

中国邮递员问题的动态规划算法研究

在动态规划的决策过程思想基础上,针对无向中国邮递员问题,提出了一个新的搜索算法CPDPA(Chinese postman decision process algorithm),首次实现了中国邮递员问题的动态规划求解．针对中国邮递员问题不能直接应用于决策思想,提出了弧点转换算法CEPA(convert edge to Doint algorithm),建立了该问题适用于决策的模型．进而针对这一模型,提出了多阶段决策过程模型转换算法MDPMCA(multistep decision process model convert algorithm),转换所得模型符合多阶段决策过程需求,可用CPDPA算法求解中国邮递员问题．对每一算法都给出了其网络应用实例．对算法的正确性和理论性做出了证明,并对最优性原理在中国邮递员问题上做了一定扩展．     

0/1背包问题

本文对“0／1背包问题”采用贪婪算法、动态规划、回溯法、分枝限界四种不同方法进行求解和算法分析．并通过各种算法的实现．研究了0／1背包问题的实质。