中国管理科学
中國管理科學
중국관이과학
CHINESE JOURNAL OF MANAGEMENT SCIENCE
2003年
5期
37-41
,共5页
双目标%最短路%有效解%算法
雙目標%最短路%有效解%算法
쌍목표%최단로%유효해%산법
本文研究了一个双目标最短路问题.在该问题中,一个目标函数是∑形式,另一个目标函数是max形式.首先给出了一个时间复杂性为O(m2logn)的算法产生代表有效解集合.然后研究了∑和max的组合目标函数最短路问题,对动态问题和静态问题,分别给出了一个时间复杂性都为O(m2logn)的算法.最后在字典序最优解的意义下,本文给出了两个时间复杂性都为O(mlogn)的算法.
本文研究瞭一箇雙目標最短路問題.在該問題中,一箇目標函數是∑形式,另一箇目標函數是max形式.首先給齣瞭一箇時間複雜性為O(m2logn)的算法產生代錶有效解集閤.然後研究瞭∑和max的組閤目標函數最短路問題,對動態問題和靜態問題,分彆給齣瞭一箇時間複雜性都為O(m2logn)的算法.最後在字典序最優解的意義下,本文給齣瞭兩箇時間複雜性都為O(mlogn)的算法.
본문연구료일개쌍목표최단로문제.재해문제중,일개목표함수시∑형식,령일개목표함수시max형식.수선급출료일개시간복잡성위O(m2logn)적산법산생대표유효해집합.연후연구료∑화max적조합목표함수최단로문제,대동태문제화정태문제,분별급출료일개시간복잡성도위O(m2logn)적산법.최후재자전서최우해적의의하,본문급출료량개시간복잡성도위O(mlogn)적산법.