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

被引：3

作者：

李帮义

盛昭翰

机构：

[1] 南京航空航天大学经济管理学院

[2] 南京大学管理科学与工程研究院南京

[3] 南京

来源：

中国管理科学 | 2003年 / 05期

关键词：

双目标; 最短路; 有效解; 算法;

D O I：

10.16381/j.cnki.issn1003-207x.2003.05.008

中图分类号：

O174 [函数论];

学科分类号：

070104 ;

摘要：

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

引用

页码：38 / 42

页数：5