自1991年由Mitchell和Papadimitriou提出带权区域问题以来，人们开始认识到带权值模型的通用性较强，陆续有很多学者开始研究这个问题。在二维带权区域近似最优路径问题中，一个二维空间被划分成n个三角形区域，每个三角形区域与一个正的权值相关联，不同的三角形区域权值可以不同。之所以说带权值模型的通用性强，是因为带障碍物无权值区域最短路径问题可以看作是特殊的带权值区域问题，即障碍点的权值为+∞，无障碍点的权值为l。由于求带权值区域的精确最优路径算法在时间和空间上代价很高，所以现在趋势是主要集中在研究近似最优路径算法。 带权区域最短路径问题可运用于很多领域，例如机器人、交通控制、搜索和逃生、地理信息系统等，具有较高的实际应用价值。近年来，三维空间中的路径寻找和计算又成为一个亟待解决的问题。鉴于带权区域最优路径问题的实际应用价值，本文将三维空间带权区域最优路径问题作为本文的重要研究内容。 遗传算法、蚂蚁算法都是启发式算法，启发式算法求解速度较快，可有着算法复杂，评估函数不易求得，求得的解是满意解并不一定是最优解等缺点。1996年Zhan和Noon使用实际交通网络测试了17种算法中的15种，测试结果表明：计算一点到所有其它点的最短路径最快的算法是Dijkstra算法。而且遗传算法和蚂蚁算法要想取得较好结果需要一定的专家经验，而Dijkstra算法一定能找到较好的最优路径，所以在本文设计主要基于Dijkstra算法。 经典的Dijkstra算法是用于求解从连通图中的一个顶点出发到图中其它所有顶点的最短路径，这样比较费时，而且也不符合实际需要，并且也只给出了从源点到其它各点的最短路径长度，而没有给出源点到其它各点的最短路径所经过的中间点，这与本文求解的带权区域上最短路径问题的最终要求不符。因此，针对这两点，本文求解带权区域最短路径问题时对经典Dijkstra算法改进了两处。其中第二处改进与前人方法不同，本文方法直接在原Dijkstra算法的原有循环中进行求取最短路径，时间效率更高。 细分法是通过在原有的三角网格模型中按一定规则插人离散点，产生新的离散边，在更细致的网格上求解最短路径，从而使得路径精度提高。我们将细分方法分为两种，一种是全局细分，一种是局部细分。全局细分就是对整个不规则三角网格按一定规则进行细分，并且求取最短路径。局部细分法是在原始三角网格上求出初始最短路径后，对初始最短路径周围的三角形进行细分，在局部网格上调整最短路径。很显然局部细分法的算法效率比全局细分法高，但本文是在带权区域上求解两点间的最短路径，所以极有可能求得的初始路径走向错误，则细分之后求得的最短路径误差较大。而全局细分法能够在最大程度上保证最短路径的走向正确，从而保证路径的精确度。所以文本设计求解初始近似最短路径时采取全局细分法。 本文设计首先采取全局细分法对整个原始不规则三角网格按固定离散点方案进行一次细分，细分程度可以用户决定，然后在细分后新生成细分图上利用改进的Dijkstra算法求取最短路径，并求出最短路径所经过三角形面片的面号。对这些三角形面片进行局部细分，并求取最短路径，再对这些三角形面片进行局部细分以及求解最短路径，如此重复局部细分求解最短路径的过程，以对最短路径进行微调来达到更高的精度，直到前后两次迭代的结果小于用户给定的精度。 本文设计在VC++6.0环境下利用OpenG1实现，通过实验结果表明本文设计方案可以高效、方便地求得带权区域上任意两点间的近似最优路径。