作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2008, Vol. 34 ›› Issue (12): 175-177. doi: 10.3969/j.issn.1000-3428.2008.12.062

• 人工智能及识别技术 • 上一篇    下一篇

带模糊权值的最短路问题及启发式算法

汪泽焱   

  1. (解放军理工大学理学院,南京211101)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-06-20 发布日期:2008-06-20

Shortest Path Problem with Fuzzy Weights and Heuristic Algorithm

WANG Ze-yan

  

  1. (Institute of Sciences, PLA University of Science and Technology, Nanjing 211101)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-06-20 Published:2008-06-20

摘要: 研究网络链路权值是三角型模糊数时的最短路问题,建立模糊线性整数优化模型。通过引入目标函数的正、负理想点和隶属度概念,将模糊优化问题转化为确定系数的单目标优化问题,并给出求解算法。该算法通过调整反映决策者意图的目标函数权系数,得到决策者的满意解。对14个节点的实例网络进行仿真,经过6步就能得到令决策者满意的解,表明了模型和算法的有效性。

关键词: 最短路问题, 模糊权值, 模糊优化, 理想点, 启发式算法

Abstract: This paper studies the Shortest Path(SP) with fuzzy weights on edges. A Fuzzy linear Integer-Programming model (FIP) is established, which has triangular fuzzy numbers in object function. Applying the fuzzy membership functions and positive and negative ideal point of object function FIP can be transformed into a linear integer programming with a single determinate objective functions. A new algorithm is presented. If decision maker is not satisfied with the solution, the weights of objective function in the single objective programming can be modified until the satisfactory solution can be obtained. A satisfactory solution can be obtained after 6 steps by simulating the network with 14 nodes, which demonstrates the efficiency of the model and algorithm.

Key words: shortest path problem, fuzzy weights, fuzzy optimization, ideal point, heuristic algorithm

中图分类号: