带权区域上任意两点间的近似最优路径算法调研

Survey of Algorithm of Approximate Optimal Path Between Two Arbitrary Points in Weighted Regions

自1991年由Mitchell和Papadimitriou提出带权值区域问题以来,人们开始认识到带权值模型的通用性较强,陆续有很多学者开始研究这个问题。在二维带权区域近似最优路径问题中,一个二维空间被划分成n个三角形区域,每个三角形区域与一个正的权值相关联,不同的三角形区域权值可以不同。如何快速求解出任意两点间的一条路径并使其代价最少就是文中研究的内容。对此问题的国内外现状进行了详细阐述与比较,并提出一个能获得更为逼近最优路径的结果且牺牲运行时间较少的可行方案,最后指出此问题的发展趋势。

Since Mitchell and Papadimitriou introduced the weighted problerh in 1991 ,people had begun to realize the strong universality of the weighted model, and many scholars had begun to study this problem. In the two dimension weighted region approximate optimal path problem, a two dimension space is divided into n triangular regions, each of which is associated with a distinct positive weight, This paper concentrates on how to solve rapidly a path between two arbitrary points with the least cost. It expatiates internal and external actualities, and has a contrast between them. It presents a feasible scheme from which we can obtain a path with less cost and sacrifice less running time. Finally,it describes the trend of this problem.