带均匀分布权值的最短路问题  被引量:1

Shortest Path Problem with Uniform Distribution Weights

在线阅读下载全文

作  者:汪泽焱[1] 刁兴春[2] 汪挺[2] 

机构地区:[1]解放军理工大学理学院,南京210007 [2]总参第六十三研究所,南京210007

出  处:《计算机工程与应用》2005年第17期139-142,共4页Computer Engineering and Applications

基  金:国家部委重点实验室基金

摘  要:最短路问题是网络设计中的一个基本问题,当前研究工作都基于边的权值是确定的这一假设。论文研究边的权值是一区间数时的最短路问题,利用优化理论,建立了目标函数系数在区间上均匀分布的模糊线性整数规划模型。通过引入正、负理想点概念,将模型转化为具有确定系数的单目标优化问题,给出了求解算法,并证明了算法的时间复杂性是多项式时间的。仿真实例说明了模型和算法的有效性。The shortest path problem(SP) is a basic problem in network design,which is NP-complete.Most research works of SP are based on the supposition that the weights on edges are determinate numbers currently.The paper studies the SP with non-determinate weights on edges.A fuzzy linear integer-programming model(FIP) is established,which has a uniform distribution parameter in object function.Applying the positive and negative idea point,FIP can be transformed into a linear integer programming with a single determinate objective function.A new algorithm is presented and is proved to have a polynomial time complexity.The efficiency of the algorithm is demonstrated by simulating example.

关 键 词:最短路 均匀分布 模糊线性整数规划 理想点 复杂性 

分 类 号:TP393.01[自动化与计算机技术—计算机应用技术]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象