我的应用程序使用 A* 搜索算法查找或构建对于丘陵/山区的徒步旅行者来说最短的路线。输入文件是 .dem（数字高程模型）和包含现有路线的路线图文件。代码使用 Python，使用的库是 pygdal、NumPy 和 PyQGIS。
算法提供的路线非常陡峭。我希望我的路线遵循坡度准则，每 30m 只有 1m 的海拔。 A*找到从峰到谷的直线最短路线，这是不切实际的。输出应以小于 1.91 度的角度从一条轮廓线下降到另一条轮廓线。
“我希望输出应该以小于特定角度的角度从一条轮廓线下降到另一条轮廓线，以便下降不会那么陡。在这种情况下，建议的梯度下降为 1.91 度。”
您的问题细节太少，无法给出详细或完整的答案。
我假设您正在尝试最小化步行距离和“陡度”。
距离很简单。
“陡度”衡量标准需要明确。您想尽量减少步行过程中海拔的总变化吗？最小化最大海拔变化率？最小化平均海拔变化率？或者其他统计数据？
最后，您必须决定步行距离和“陡度”之间的权衡是什么
让：
D be the total distance
S be the "steepness" statistic you have chosen
t be the amount of "steepness" you will accept to reduce D by one unit
那么你想要
minimum C = D + t * S Eq 1
算法如下：
- Construct a graph of the possible routes from the roadmap
- Use standard graph algorithm to find all paths between start and destination
- Apply Eq 1 to paths as they are found.
- Select path with smallest C value so far
仅供参考，您可以在 https://github.com/JamesBremner/LazyHillWalker
查看实现此简单版本的 C++ 代码运行“所有路径”算法的运行时间，以查找从 https://dyngraphlab.github.io/ 下载的大图上两个随机选择的顶点之间的所有路径。使用 graphex 应用程序运行 3 次的最长结果。
| 顶点数 | 边数 | 运行时间（秒） |
|---|---|---|
| 4,700 | 27,000 | 20 |
完整的应用程序详细信息，请访问 https://github.com/JamesBremner/PathFinder/wiki/All-Paths#performance
OP建议使用A*算法。我认为 A* 只适合解决小而简单的问题，原因有两个。
A* 的内存消耗非常大。因此对于大型现实世界问题（> 10,000 个节点）来说不太实用“一个主要的实际缺点是 A* 的 O(b^d) 空间复杂度，因为它将所有生成的节点存储在内存中”https://en .wikipedia.org/wiki/A*_search_algorithm
A* 只关心从起始点到当前节点以及从当前节点到目标点的各个链接。如果选择陡度统计量作为基于整个路径的度量（例如，每单位距离的最大或平均海拔变化），则制定 A* 辅助函数（用于估计从当前顶点开始的剩余路径的成本的启发式方法，以及真实的衡量到达当前顶点的最便宜路径的成本。）将是一个挑战。
您想要选择最佳的可能路径，还是想要获得满足严格限制的所有路径？请回答“是”或“否”
您想要最小化距离和陡度的组合吗？请回答“是”或“否”
请说明如何计算陡度。请给出一个短路径的例子来回答，并说明你如何计算它的距离
您的输入图有多大。请回答顶点数和边数。