问题描述
滑雪赛道由一条带有障碍物和加速带的网格表示。滑雪者从山顶出发，每次可以向左下、正下或右下三个方向滑行一格。每个格子有不同的分值：障碍物为负分、普通雪道为0分、加速带为正分。目标是找到从起点到终点的最大得分路径。
本文将用Java实现滑雪最优路径求解，使用动态规划计算最大得分路径，并结合贪心策略进行实时障碍物规避。
核心算法思路
动态规划模型
设 $dp[i][j]$ 表示到达第 $i$ 行第 $j$ 列时的最大得分。状态转移方程为：
$$dp[i][j] = grid[i][j] + \max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1])$$
边界条件：$dp[0][j] = grid[0][j]$（第一行直接初始化）。
路径重构
通过记录每个状态的前驱方向，从终点回溯即可得到最优路径。
贪心障碍物规避
在动态规划的基础上，若检测到前方存在高密度障碍物区域，贪心策略会优先选择障碍物较少的通道，即使该通道的总得分略低。这种折中策略在真实滑雪场景中更具鲁棒性。
Java实现
import java.util.*;
/**
* 滑雪最优路径求解器
* 使用动态规划计算最大得分路径，支持贪心障碍物规避策略
*/
public class SkiPathPlanner {
// 格子类型
public static final int OBSTACLE = -10; // 障碍物（树木/岩石）
public static final int NORMAL = 0; // 普通雪道
public static final int BOOST = 5; // 加速带
public static final int SUPER_BOOST = 10; // 超级加速带
public static final int CLIFF = -50; // 悬崖（必须规避）
private int[][] grid;
private int rows;
private int cols;
public SkiPathPlanner(int[][] grid) {
this.grid = grid;
this.rows = grid.length;
this.cols = grid[0].length;
}
/**
* 动态规划求解最大得分路径
* @return 包含最大得分和路径的结果对象
*/
public PathResult findOptimalPathDP() {
int[][] dp = new int[rows][cols];
int[][] parent = new int[rows][cols]; // 记录前驱列号
// 初始化第一行
for (int j = 0; j < cols; j++) {
dp[0][j] = grid[0][j];
parent[0][j] = -1;
}
// 动态规划填充
for (int i = 1; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int maxPrev = Integer.MIN_VALUE;
int bestK = j;
// 检查三个可能的前驱方向：左上、正上、右上
for (int delta = -1; delta <= 1; delta++) {
int prevJ = j + delta;
if (prevJ >= 0 && prevJ < cols) {
if (dp[i-1][prevJ] > maxPrev) {
maxPrev = dp[i-1][prevJ];
bestK = prevJ;
}
}
}
dp[i][j] = grid[i][j] + maxPrev;
parent[i][j] = bestK;
}
}
// 寻找终点的最大值
int maxScore = Integer.MIN_VALUE;
int endCol = 0;
for (int j = 0; j < cols; j++) {
if (dp[rows-1][j] > maxScore) {
maxScore = dp[rows-1][j];
endCol = j;
}
}
// 重构路径
List<int[]> path = new ArrayList<>();
int currCol = endCol;
for (int i = rows - 1; i >= 0; i--) {
path.add(new int[]{i, currCol});
currCol = parent[i][currCol];
}
Collections.reverse(path);
return new PathResult(maxScore, path, dp);
}
/**
* 贪心障碍物规避策略
* 在局部范围内选择障碍物密度最低的方向
*/
public PathResult findGreedyPathWithObstacleAvoidance(int lookahead) {
List<int[]> path = new ArrayList<>();
int currRow = 0;
int currCol = cols / 2; // 从中间出发
int totalScore = grid[currRow][currCol];
path.add(new int[]{currRow, currCol});
while (currRow < rows - 1) {
int bestDelta = 0;
double bestScore = Double.NEGATIVE_INFINITY;
for (int delta = -1; delta <= 1; delta++) {
int nextCol = currCol + delta;
if (nextCol < 0 || nextCol >= cols) continue;
// 计算lookahead范围内的综合得分
double score = evaluatePathSegment(currRow + 1, nextCol, lookahead);
// 严重惩罚悬崖
if (grid[currRow + 1][nextCol] == CLIFF) {
score -= 1000;
}
if (score > bestScore) {
bestScore = score;
bestDelta = delta;
}
}
currCol += bestDelta;
currRow++;
totalScore += grid[currRow][currCol];
path.add(new int[]{currRow, currCol});
}
return new PathResult(totalScore, path, null);
}
/**
* 评估从指定位置开始的lookahead段路径质量
*/
private double evaluatePathSegment(int startRow, int startCol, int lookahead) {
double score = 0;
int count = 0;
for (int i = 0; i < lookahead && startRow + i < rows; i++) {
int r = startRow + i;
// 在每一行考虑当前列及左右邻居
for (int delta = -1; delta <= 1; delta++) {
int c = startCol + delta;
if (c >= 0 && c < cols) {
score += grid[r][c];
count++;
}
}
}
return count > 0 ? score / count : 0;
}
/**
* 混合策略：DP全局最优 + 贪心局部调整
*/
public PathResult findHybridPath(double obstacleThreshold) {
// 先计算DP最优路径
PathResult dpResult = findOptimalPathDP();
List<int[]> dpPath = dpResult.path;
// 检查路径上是否有过多障碍物
int obstacleCount = 0;
for (int[] pos : dpPath) {
if (grid[pos[0]][pos[1]] < 0) obstacleCount++;
}
double obstacleRatio = (double) obstacleCount / dpPath.size();
// 如果障碍物比例超过阈值，使用贪心策略
if (obstacleRatio > obstacleThreshold) {
System.out.println("DP路径障碍物过多 (" + String.format("%.1f%%", obstacleRatio * 100)
+ ")，切换至贪心规避策略");
return findGreedyPathWithObstacleAvoidance(3);
}
return dpResult;
}
/**
* 打印赛道和路径
*/
public void printTrack(PathResult result) {
boolean[][] onPath = new boolean[rows][cols];
if (result.path != null) {
for (int[] pos : result.path) {
onPath[pos[0]][pos[1]] = true;
}
}
System.out.println("=== 滑雪赛道 ===");
System.out.println("图例: ★起点/终点 ○普通 ▲加速 ■障碍 ▼悬崖 ☆路径");
System.out.println();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (onPath[i][j]) {
if (i == 0) System.out.print(" S ");
else if (i == rows - 1) System.out.print(" E ");
else System.out.print(" * ");
} else {
switch (grid[i][j]) {
case OBSTACLE: System.out.print(" T "); break;
case NORMAL: System.out.print(" . "); break;
case BOOST: System.out.print(" + "); break;
case SUPER_BOOST: System.out.print(" ++"); break;
case CLIFF: System.out.print(" C "); break;
default: System.out.printf("%2d ", grid[i][j]);
}
}
}
System.out.println();
}
System.out.println("\n总得分: " + result.score);
System.out.println("路径长度: " + result.path.size() + " 步");
}
/**
* 生成随机赛道
*/
public static int[][] generateRandomTrack(int rows, int cols, long seed) {
Random rand = new Random(seed);
int[][] grid = new int[rows][cols];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
double r = rand.nextDouble();
if (r < 0.15) grid[i][j] = OBSTACLE;
else if (r < 0.20) grid[i][j] = CLIFF;
else if (r < 0.35) grid[i][j] = BOOST;
else if (r < 0.40) grid[i][j] = SUPER_BOOST;
else grid[i][j] = NORMAL;
}
}
// 确保起点和终点安全
grid[0][cols/2] = NORMAL;
grid[rows-1][cols/2] = NORMAL;
return grid;
}
// 结果类
public static class PathResult {
public final int score;
public final List<int[]> path;
public final int[][] dpTable;
public PathResult(int score, List<int[]> path, int[][] dpTable) {
this.score = score;
this.path = path;
this.dpTable = dpTable;
}
}
public static void main(String[] args) {
// 生成15x10的随机赛道
int[][] track = generateRandomTrack(15, 10, 12345);
SkiPathPlanner planner = new SkiPathPlanner(track);
System.out.println("=== 动态规划最优路径 ===");
PathResult dpResult = planner.findOptimalPathDP();
planner.printTrack(dpResult);
System.out.println("\n=== 贪心障碍物规避路径 ===");
PathResult greedyResult = planner.findGreedyPathWithObstacleAvoidance(3);
planner.printTrack(greedyResult);
System.out.println("\n=== 混合策略路径 ===");
PathResult hybridResult = planner.findHybridPath(0.3);
planner.printTrack(hybridResult);
}
}
算法复杂度分析
- 动态规划：时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$，其中 $m$ 为行数，$n$ 为列数。每个格子只需计算三个前驱状态的最大值。
- 贪心策略：时间复杂度 $O(m \times n \times k)$，$k$ 为lookahead深度。每步需要评估前方 $k$ 行的局部区域。
- 混合策略：先执行DP（$O(mn)$），若障碍物比例过高再执行贪心（$O(mnk)$），最坏情况下为 $O(mnk)$。
扩展思考
- 多目标优化：除得分外，还可引入路径平滑度指标（减少急转弯）、最短时间指标等，使用加权目标函数或帕累托最优求解。
- 随机赛道生成：可通过柏林噪声（Perlin Noise）生成更自然的山地地形，而非完全随机分布。
- 实时重规划：若滑雪过程中发现前方出现意外障碍（如雪崩），可使用A*算法从当前位置重新规划到终点。
- 概率模型：将障碍物视为概率分布而非确定值，使用期望动态规划（EDP）计算最大期望得分路径。
总结
滑雪路径规划将动态规划与贪心策略有机结合：DP保证全局最优性，贪心策略在障碍物密集区域提供鲁棒的局部规避能力。混合策略通过阈值判断自动切换两种模式，兼顾了最优性与安全性。这种分层决策框架广泛应用于机器人路径规划、游戏AI和导航系统中。
