目标函数为∑和max的双目标最短路问题:算法和复杂性

摘要：

本文研究了一个双目标最短路问题.在该问题中,一个目标函数是∑形式,另一个目标函数是max形式.首先给出了一个时间复杂性为O(m2logn)的算法产生代表有效解集合.然后研究了∑和max的组合目标函数最短路问题,对动态问题和静态问题,分别给出了一个时间复杂性都为O(m2logn)的算法.最后在字典序最优解的意义下,本文给出了两个时间复杂性都为O(mlogn)的算法.

关键词：双目标、最短路、有效解、算法

所属期刊栏目：11

分类号：O1224(初等数学)

资助基金：国家自然科学基金70171028

在线出版日期：2003-12-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：37-41