两个组合优化问题的算法设计  

Algoritnm decision for two combinational optimization questions

作　　者：杨宏东[1] 王骁力[1] 

机构地区：[1]南阳师范学院数学与统计学院,河南南阳473061

出　　处：《南阳师范学院学报》2009年第12期17-22,共6页Journal of Nanyang Normal University

基　　金：河南省教育厅自然科学基金资助项目(2009B110017);南阳师范学院高层次人才科研资助项目

摘　　要：以有向赋权图为工具,通过对满足限制条件的最短有向路径问题的讨论,给出了两个组合优化问题——大学教学计划的编排问题和交通网络中路径规划问题的有效算法,并通过实例进行了算法分析.Digraph have an important position in network analysis. Especially we can use weighted digraphs as a tool to solve many practical problems, such as transportation network. Some modification was given for the Dijkstra＇ s algorithm of the shortest path problem in special weighted digraphs. A new polynomial algorithm of the schedule of university teaching program was acquired and a new efficient algorithm of planning of the transportation network was presented in this paper. Furthermore, the algorithms＇ complexity was analyzed and some practical applications were discussed in the paper.

关 键 词：有向图 最短有向路 教学计划编排 交通网络 路径规划 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]