论文部分内容阅读
有向中国邮递员问题是一个经典优化问题,在现实生活中的各个领域都有广泛应用。本文结合地震后救援救灾的紧迫程度,将有向中国邮递员问题进行衍生,研究点带优先顺序的有向中国邮递员问题。该问题在交通运输、紧急救援、道路清扫等方面既有理论意义,又有广泛的实际应用价值。对于有向中国邮递员问题而言,我们都是在强连通有向图上进行研究与求解。 本文分两种情况建立数学模型:第一种情况为带优先顺序的点不可以重复经过的有向中国邮递员问题,第二种为带优先顺序的点可以重复经过的有向中国邮递员问题。本文将此两类问题分解为有向最短路与有向欧拉迹问题进行求解。对第一种情况,设计了一个多项式时间算法,证明了最优性并给出复杂性分析。对第二种情况,设计出一个2-近似算法找到其有向欧拉回路,并对算法复杂性进行了分析。为了使这一问题更接近现实生活,本文对点带优先顺序的有向中国邮递员问题进行了三类推广,即点带优先顺序弧带次数限制的有向中国邮递员问题,部分弧带优先顺序和所有弧带次数限制的有向中国邮递员问题,及混合图上点带优先顺序的中邮递员问题,并设计出解决它们的近似算法。最后,利用Matlab程序实现求解点带优先顺序的有向中国邮递员问题的算法。