问题描述
攀岩路线由岩壁上的多个支点（手点和脚点）组成，攀岩者需要在这些支点之间移动以到达顶点。每个支点有不同的属性：位置坐标、握持难度、体力消耗值。从当前支点到下一个支点的移动也有对应的体力消耗，取决于距离和角度。
本文将用Java实现攀岩路线的最优能量消耗规划，将岩壁建模为带权有向图，使用Dijkstra算法寻找从起点到终点的最小能量路径，并通过动态规划处理多阶段休息恢复策略。
核心算法思路
图论建模
将每个支点建模为图中的一个节点。若两个支点之间的欧氏距离不超过攀岩者的最大臂展，则在它们之间建立一条有向边，边的权重为从源点到目标点的体力消耗：
$$cost(u, v) = baseCost \times distance(u, v) \times anglePenalty(u, v)$$
其中 $anglePenalty$ 根据移动方向的陡峭程度增加额外消耗（向上攀爬比横向移动更费力）。
Dijkstra最短路径
由于所有边的权重均为正，Dijkstra算法可以在 $O((V+E) \log V)$ 时间内找到从起点到终点的最小能量路径。
动态规划休息策略
攀岩者在途中可以选择在某些支点上休息恢复体力。设 $dp[i][e]$ 表示到达第 $i$ 个支点且剩余体力为 $e$ 时的最大累计恢复值。状态转移考虑两种选择：
– 继续前进：消耗边权重对应的体力
– 休息恢复：在当前支点恢复一定比例的体力（但耗时增加）
Java实现
import java.util.*;
/**
* 攀岩最优能量路径规划器
* 使用图论建模、Dijkstra最短路径与动态规划休息策略
*/
public class ClimbingRoutePlanner {
// 支点类
public static class Hold {
public final int id;
public final double x, y; // 坐标位置 (米)
public final double difficulty; // 握持难度系数 (1.0~3.0)
public final double restValue; // 休息恢复效率 (0~1)
public Hold(int id, double x, double y, double difficulty, double restValue) {
this.id = id;
this.x = x;
this.y = y;
this.difficulty = difficulty;
this.restValue = restValue;
}
public double distanceTo(Hold other) {
double dx = this.x - other.x;
double dy = this.y - other.y;
return Math.sqrt(dx * dx + dy * dy);
}
}
// 边类
public static class Edge {
public final int from, to;
public final double cost;
public Edge(int from, int to, double cost) {
this.from = from;
this.to = to;
this.cost = cost;
}
}
private List<Hold> holds;
private List<List<Edge>> graph;
private double maxReach; // 最大臂展 (米)
private double baseCost; // 基础体力消耗系数
public ClimbingRoutePlanner(double maxReach, double baseCost) {
this.maxReach = maxReach;
this.baseCost = baseCost;
}
/**
* 添加支点列表并构建图
*/
public void setHolds(List<Hold> holds) {
this.holds = holds;
this.graph = new ArrayList<>();
for (int i = 0; i < holds.size(); i++) {
graph.add(new ArrayList<>());
}
buildGraph();
}
/**
* 构建带权有向图
*/
private void buildGraph() {
for (int i = 0; i < holds.size(); i++) {
for (int j = 0; j < holds.size(); j++) {
if (i == j) continue;
double dist = holds.get(i).distanceTo(holds.get(j));
if (dist <= maxReach) {
double cost = computeCost(i, j, dist);
graph.get(i).add(new Edge(i, j, cost));
}
}
}
}
/**
* 计算从支点u到v的体力消耗
*/
private double computeCost(int u, int v, double dist) {
Hold from = holds.get(u);
Hold to = holds.get(v);
// 基础距离消耗
double cost = baseCost * dist;
// 握持难度惩罚
cost *= to.difficulty;
// 角度惩罚：向上攀爬更费力
double dy = to.y - from.y;
double dx = to.x - from.x;
double angle = Math.atan2(dy, dx);
// 向上角度越大，惩罚越高
if (angle > 0) {
cost *= (1 + Math.sin(angle));
}
// 横向移动的微调惩罚
if (Math.abs(angle) < Math.toRadians(15)) {
cost *= 1.2;
}
return cost;
}
/**
* Dijkstra算法寻找最小能量路径
* @param start 起点索引
* @param target 终点索引
* @return 最短路径结果
*/
public ShortestPathResult dijkstra(int start, int target) {
int n = holds.size();
double[] dist = new double[n];
int[] parent = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(dist, Double.MAX_VALUE);
Arrays.fill(parent, -1);
dist[start] = 0;
// 优先队列: (当前距离, 节点)
PriorityQueue<double[]> pq = new PriorityQueue<>(Comparator.comparingDouble(a -> a[0]));
pq.offer(new double[]{0, start});
while (!pq.isEmpty()) {
double[] curr = pq.poll();
double d = curr[0];
int u = (int) curr[1];
if (visited[u]) continue;
visited[u] = true;
if (u == target) break;
for (Edge e : graph.get(u)) {
int v = e.to;
if (visited[v]) continue;
double newDist = dist[u] + e.cost;
if (newDist < dist[v]) {
dist[v] = newDist;
parent[v] = u;
pq.offer(new double[]{newDist, v});
}
}
}
// 重构路径
List<Integer> path = new ArrayList<>();
int curr = target;
while (curr != -1) {
path.add(curr);
curr = parent[curr];
}
Collections.reverse(path);
return new ShortestPathResult(dist[target], path);
}
/**
* 带休息策略的动态规划
* 在体力限制下寻找最优路径
* @param start 起点
* @param target 终点
* @param maxEnergy 最大体力值
* @return 可行路径及剩余体力
*/
public RestStrategyResult findOptimalPathWithRest(int start, int target, double maxEnergy) {
int n = holds.size();
// dp[i] = 到达i时的最小累计消耗
double[] dp = new double[n];
int[] parent = new int[n];
boolean[] canReach = new boolean[n];
Arrays.fill(dp, Double.MAX_VALUE);
Arrays.fill(parent, -1);
dp[start] = 0;
canReach[start] = true;
// 使用类似Dijkstra的扩展，但加入体力约束
PriorityQueue<double[]> pq = new PriorityQueue<>(Comparator.comparingDouble(a -> a[0]));
pq.offer(new double[]{0, start, maxEnergy}); // (累计消耗, 节点, 剩余体力)
while (!pq.isEmpty()) {
double[] curr = pq.poll();
double costSoFar = curr[0];
int u = (int) curr[1];
double energyLeft = curr[2];
for (Edge e : graph.get(u)) {
int v = e.to;
double moveCost = e.cost;
// 检查是否有足够体力
if (energyLeft >= moveCost) {
double newCost = costSoFar + moveCost;
double newEnergy = energyLeft - moveCost;
// 考虑在v休息
Hold holdV = holds.get(v);
if (holdV.restValue > 0) {
double recovered = maxEnergy * holdV.restValue;
newEnergy = Math.min(maxEnergy, newEnergy + recovered);
}
if (newCost < dp[v]) {
dp[v] = newCost;
parent[v] = u;
canReach[v] = true;
pq.offer(new double[]{newCost, v, newEnergy});
}
}
}
}
if (!canReach[target]) {
return new RestStrategyResult(-1, new ArrayList<>(), 0);
}
// 重构路径
List<Integer> path = new ArrayList<>();
int curr = target;
while (curr != -1) {
path.add(curr);
curr = parent[curr];
}
Collections.reverse(path);
return new RestStrategyResult(dp[target], path, maxEnergy - dp[target]);
}
/**
* 打印路线信息
*/
public void printRoute(ShortestPathResult result) {
System.out.println("=== 攀岩路线规划 ===");
System.out.printf("最小能量消耗: %.2f J%n", result.totalCost);
System.out.println("路径支点: ");
for (int i = 0; i < result.path.size(); i++) {
int holdId = result.path.get(i);
Hold h = holds.get(holdId);
System.out.printf(" %d. 支点#%d (%.1f, %.1f) 难度:%.1f 休息效率:%.1f%% %s%n",
i + 1, h.id, h.x, h.y, h.difficulty, h.restValue * 100,
h.restValue > 0.3 ? "[推荐休息]" : "");
}
// 计算路径统计
double totalDist = 0;
double maxStep = 0;
for (int i = 1; i < result.path.size(); i++) {
Hold from = holds.get(result.path.get(i-1));
Hold to = holds.get(result.path.get(i));
double d = from.distanceTo(to);
totalDist += d;
maxStep = Math.max(maxStep, d);
}
System.out.printf("\n总攀爬距离: %.2f m%n", totalDist);
System.out.printf("最大单步距离: %.2f m%n", maxStep);
System.out.printf("平均单步消耗: %.2f J%n",
result.totalCost / (result.path.size() - 1));
}
/**
* 生成随机攀岩路线
*/
public static List<Hold> generateRandomRoute(int numHolds, double wallWidth,
double wallHeight, long seed) {
Random rand = new Random(seed);
List<Hold> holds = new ArrayList<>();
// 起点 (底部中央)
holds.add(new Hold(0, wallWidth / 2, 0, 1.0, 0));
// 中间支点
for (int i = 1; i < numHolds - 1; i++) {
double x = rand.nextDouble() * wallWidth;
double y = (rand.nextDouble() * 0.8 + 0.1) * wallHeight;
double diff = 1.0 + rand.nextDouble() * 2.0;
double rest = rand.nextDouble() > 0.6 ? rand.nextDouble() * 0.5 : 0;
holds.add(new Hold(i, x, y, diff, rest));
}
// 终点 (顶部)
holds.add(new Hold(numHolds - 1, wallWidth / 2, wallHeight, 1.0, 0));
return holds;
}
// 结果类
public static class ShortestPathResult {
public final double totalCost;
public final List<Integer> path;
public ShortestPathResult(double totalCost, List<Integer> path) {
this.totalCost = totalCost;
this.path = path;
}
}
public static class RestStrategyResult {
public final double totalCost;
public final List<Integer> path;
public final double remainingEnergy;
public RestStrategyResult(double totalCost, List<Integer> path, double remainingEnergy) {
this.totalCost = totalCost;
this.path = path;
this.remainingEnergy = remainingEnergy;
}
}
public static void main(String[] args) {
// 创建攀岩规划器：最大臂展1.5米，基础消耗系数10
ClimbingRoutePlanner planner = new ClimbingRoutePlanner(1.5, 10.0);
// 生成20个支点的随机路线，岩壁宽5米高15米
List<Hold> route = generateRandomRoute(20, 5.0, 15.0, 42);
planner.setHolds(route);
// Dijkstra最优路径
System.out.println("=== Dijkstra最小能量路径 ===");
ShortestPathResult sp = planner.dijkstra(0, route.size() - 1);
planner.printRoute(sp);
// 带休息策略的路径
System.out.println("\n=== 带休息策略的路径 (体力限制: 500) ===");
RestStrategyResult restResult = planner.findOptimalPathWithRest(
0, route.size() - 1, 500);
if (restResult.totalCost >= 0) {
System.out.printf("可行路径找到！总消耗: %.2f J, 剩余体力: %.2f%n",
restResult.totalCost, restResult.remainingEnergy);
System.out.println("路径: " + restResult.path);
} else {
System.out.println("在体力限制下无法到达终点，需要增加体力或改进路线！");
}
}
}
算法复杂度分析
- 建图：$O(V^2)$，需要计算所有支点对之间的距离并判断是否在臂展范围内。
- Dijkstra算法：$O((V + E) \log V)$，使用优先队列实现。对于岩壁支点图，$E \leq V^2$。
- 带休息策略的DP：最坏情况下 $O(E \cdot K)$，$K$ 为体力离散化的精度。若使用连续体力值，复杂度退化为与Dijkstra相同的 $O((V+E) \log V)$。
扩展思考
- 三维岩壁：将支点坐标扩展为 $(x, y, z)$ 三维空间，距离计算改为三维欧氏距离，算法框架保持不变。
- 动态支点：若某些支点在受力后会晃动（增加握持难度），可将难度系数建模为随机变量，使用期望最短路径求解。
- 多攀岩者协作：在团队攀岩中，可以使用多智能体路径规划（MAPF）避免绳索缠绕和路线冲突。
- 疲劳累积模型：引入非线性疲劳函数 $f(t) = e^{\lambda t}$，使长时间连续攀爬的边际成本递增，更接近真实生理极限。
总结
攀岩路线规划将图论最短路径与动态规划资源管理巧妙融合。Dijkstra算法在正权图中保证了全局最优性，而休息恢复策略通过状态扩展将体力约束纳入路径评估。这种带资源约束的最短路径框架广泛应用于物流配送（燃油限制）、无人机巡航（电量限制）和角色扮演游戏（魔法值管理）等场景。
