摘要：由于多媒体通信的需要，QoS路由技术已成为通信网络中研究的热点。通常情况下，在网络中寻找同时满足多个独立加性约束条件的路由是一个NP完全问题。本文探讨了多约束条件下的路径选择（McP）问题，通过将MCP问题转化为离散化的动态网络，得到了一个性能更好的启发式QoS路由算法，复杂度从O（Tmn）降低为O（Tm），其中m、n分别是节点数和边数，丁是算法定义的正整数，并在理论上证明了算法的正确性。最后给出实验举例，并通过与现有算法性能比较，表明改进的启发式算法能快速、有效地解决MCP问题，且适用于大规模的网络系统。

关键词：qos路由 路径选择 多约束条件 启发式算法 mcp 

单位：63655部队 新疆乌鲁木齐841700 国防科学技术大学理学院 湖南长沙410073 北京航空航天大学电子信息工程学院 北京100083