论文部分内容阅读
在许多服务性行业中，如物流配送等，我们经常会按照事情的轻重缓急来决定优先服务的对象，这样不仅保证了企业的效益，更提升了企业的品质;同样在一些救援问题中，我们也需要根据受灾情况的程度来采取优先救援策略，对于受灾情况越严重的地方就越应该先进行救援。本论文针对以上这些问题，给需要服务或救援的对象设立不同的优先级，提出了中国邮递员问题的一种新的推广形式，即无向图中带优先级点限制的中国邮递员问题，证明了该问题是NP-完备的。针对该问题，本文建立了两个数学模型，并对这两个数学模型分别设计了两个2-近似算法，并给出了相应的程序设计。