每日算法 — 使用java实现接力：最优交接棒策略与团队调度动态规划

一、接力赛规则与算法挑战

4×100米接力是田径中最激动人心的项目之一。除个人速度外，交接棒技术直接影响成绩——世界大赛中约30%的 disqualification 源于交接棒失误。

核心算法挑战：
1. 棒次分配：将4位选手分配到4棒，使总时间最小
2. 交接区速度匹配：传棒者与接棒者的速度需匹配，减少动能损失
3. 交接时机：在20米交接区内选择最佳传棒位置
4. 预跑距离：接棒者提前起跑，与传棒者同时到达交接点

二、问题建模

2.1 选手能力模型

每位选手用以下参数描述：
– v_max：最高速度（m/s）
– a：加速度（m/s²）
– endurance：速度保持能力（后程衰减系数）
– handoffSkill：交接技术评分（0-1，影响交接时间损失）

2.2 交接动力学

交接过程可建模为两体速度匹配问题：

传棒者以速度 v1 进入交接区，接棒者从静止开始加速。最优交接发生在两者速度相等时：

v1 = a2 * t
交接距离 = v1 * t_handoff + 0.5 * a2 * t²

其中 t_handoff 为传棒动作时间（约0.3-0.5秒）。

三、核心算法实现

3.1 选手类定义

public class RelayRunner {
    private String name;
    private double maxSpeed;      // 最高速度 (m/s)
    private double acceleration;  // 加速度 (m/s²)
    private double endurance;     // 耐力系数 (0.9-1.0，每100m衰减)
    private double handoffSkill;  // 交接技术 (0-1)
    private double reactionTime;  // 反应时间 (s)

    public RelayRunner(String name, double maxSpeed, double acceleration,
                       double endurance, double handoffSkill, double reactionTime) {
        this.name = name;
        this.maxSpeed = maxSpeed;
        this.acceleration = acceleration;
        this.endurance = endurance;
        this.handoffSkill = handoffSkill;
        this.reactionTime = reactionTime;
    }

    /**
     * 计算跑完距离d所需时间（考虑加速和耐力衰减）
     */
    public double runTime(double distance) {
        // 加速阶段：v = a*t, 达到最高速的时间
        double t_accel = maxSpeed / acceleration;
        double d_accel = 0.5 * acceleration * t_accel * t_accel;

        double totalTime;
        if (distance <= d_accel) {
            // 全程加速：d = 0.5*a*t²
            totalTime = Math.sqrt(2 * distance / acceleration);
        } else {
            // 加速段 + 匀速段
            double d_cruise = distance - d_accel;
            double enduranceFactor = Math.pow(endurance, distance / 100.0);
            double cruiseSpeed = maxSpeed * enduranceFactor;
            totalTime = t_accel + d_cruise / cruiseSpeed;
        }

        return totalTime + reactionTime;
    }

    /**
     * 计算交接过程时间损失
     * 与接棒者的加速能力和传棒者的速度匹配度有关
     */
    public double handoffTimeLoss(RelayRunner receiver, double incomingSpeed) {
        // 接棒者达到匹配速度所需时间
        double matchTime = incomingSpeed / receiver.acceleration;
        // 交接动作时间（受技术影响）
        double actionTime = 0.4 * (1.5 - handoffSkill);
        // 速度不匹配惩罚
        double speedPenalty = Math.abs(incomingSpeed - receiver.getSpeedAt(matchTime)) * 0.1;

        return actionTime + speedPenalty;
    }

    /**
     * 计算t时刻的速度
     */
    public double getSpeedAt(double time) {
        double t_eff = Math.max(0, time - reactionTime);
        double v = acceleration * t_eff;
        return Math.min(v, maxSpeed);
    }

    /**
     * 计算预跑距离：接棒者需要提前跑多远
     */
    public double calculatePreRunDistance(double incomingSpeed) {
        // 接棒者需要在传棒者到达时达到匹配速度
        double matchTime = incomingSpeed / acceleration;
        return 0.5 * acceleration * matchTime * matchTime;
    }

    // Getters
    public String getName() { return name; }
    public double getMaxSpeed() { return maxSpeed; }
    public double getAcceleration() { return acceleration; }
    public double getHandoffSkill() { return handoffSkill; }

    @Override
    public String toString() {
        return String.format("%s[最高速%.1fm/s 加速%.1f 技术%.2f]", 
                            name, maxSpeed, acceleration, handoffSkill);
    }
}

3.2 交接过程物理模拟

public class HandoffSimulator {
    private static final double HANDOFF_ZONE = 20.0; // 交接区长度（米）
    private static final double MIN_HANDOFF_DIST = 5.0; // 最小交接距离（进入交接区后）

    /**
     * 模拟完整交接过程
     * @return 交接过程总时间损失（秒）
     */
    public HandoffResult simulateHandoff(RelayRunner passer, RelayRunner receiver,
                                         double passerEntrySpeed) {
        double dt = 0.01; // 10ms 步长
        double time = 0;

        // 传棒者位置（以交接区起点为0）
        double passerPos = 0;
        double passerSpeed = passerEntrySpeed;

        // 接棒者从预跑位置开始
        double preRunDist = receiver.calculatePreRunDistance(passerEntrySpeed);
        double receiverPos = -preRunDist; // 负值表示在交接区外

        boolean handoffComplete = false;
        double handoffPosition = 0;
        double timeLoss = 0;

        while (passerPos < HANDOFF_ZONE && time < 5.0) {
            // 传棒者以接近最高速匀速跑（已进入后程）
            passerPos += passerSpeed * dt;

            // 接棒者加速
            if (receiverPos < 0) {
                // 还在预跑
                double t_running = time;
                double v = receiver.getSpeedAt(t_running);
                receiverPos += v * dt;
            } else {
                // 进入交接区
                double t_inZone = time - (receiverPos < 0 ? 0 : 
                    Math.sqrt(2 * preRunDist / receiver.getAcceleration()));
                double v = receiver.getSpeedAt(t_inZone);
                receiverPos += v * dt;
            }

            // 检查是否可以交接（距离接近且速度匹配）
            if (!handoffComplete && receiverPos >= MIN_HANDOFF_DIST) {
                double distDiff = Math.abs(passerPos - receiverPos);
                double speedDiff = Math.abs(passerSpeed - 
                    receiver.getSpeedAt(time));

                // 距离差小于0.5米且速度差小于0.5m/s时完成交接
                if (distDiff < 0.5 && speedDiff < 0.5) {
                    handoffComplete = true;
                    handoffPosition = passerPos;
                    // 时间损失 = 理想情况时间 - 实际时间
                    double idealTime = HANDOFF_ZONE / passerEntrySpeed;
                    timeLoss = time - idealTime;
                }
            }

            time += dt;
        }

        if (!handoffComplete) {
            timeLoss = 0.5; // 失误惩罚
        }

        return new HandoffResult(handoffComplete, handoffPosition, timeLoss);
    }

    static class HandoffResult {
        boolean success;
        double position;
        double timeLoss;

        HandoffResult(boolean success, double position, double timeLoss) {
            this.success = success;
            this.position = position;
            this.timeLoss = timeLoss;
        }
    }
}

3.3 棒次分配动态规划

import java.util.*;

public class RelayTeamOptimizer {
    private List<RelayRunner> runners;
    private HandoffSimulator simulator;
    private double[] legDistances = {100.0, 100.0, 100.0, 100.0};

    public RelayTeamOptimizer(List<RelayRunner> runners) {
        this.runners = runners;
        this.simulator = new HandoffSimulator();
    }

    /**
     * 使用全排列枚举+动态规划求解最优棒次
     * 4人4棒 = 4! = 24种排列，可暴力枚举
     * 对于更多选手使用匈牙利算法或动态规划
     */
    public RelayAssignment findOptimalOrder() {
        List<RelayRunner> bestOrder = null;
        double bestTime = Double.MAX_VALUE;

        List<List<RelayRunner>> permutations = generatePermutations(runners);

        for (List<RelayRunner> order : permutations) {
            double time = simulateRelay(order);
            if (time < bestTime) {
                bestTime = time;
                bestOrder = new ArrayList<>(order);
            }
        }

        return new RelayAssignment(bestOrder, bestTime);
    }

    /**
     * 模拟完整接力赛
     */
    private double simulateRelay(List<RelayRunner> order) {
        double totalTime = 0;
        double currentSpeed = 0;

        for (int leg = 0; leg < 4; leg++) {
            RelayRunner runner = order.get(leg);
            double distance = legDistances[leg];

            if (leg == 0) {
                // 第一棒：从起跑开始
                totalTime += runner.runTime(distance);
                // 估算出棒速度（简化：假设最后10m速度）
                currentSpeed = runner.getMaxSpeed() * 
                    Math.pow(runner.endurance, 0.9);
            } else {
                // 后续棒：包含交接时间损失
                RelayRunner prevRunner = order.get(leg - 1);

                // 模拟交接
                HandoffSimulator.HandoffResult handoff = 
                    simulator.simulateHandoff(prevRunner, runner, currentSpeed);

                if (!handoff.success) {
                    totalTime += 0.5; // 失误惩罚
                }

                // 跑步时间
                double runTime = runner.runTime(distance);
                totalTime += runTime + handoff.timeLoss;

                // 更新出棒速度
                currentSpeed = runner.getMaxSpeed() * 
                    Math.pow(runner.endurance, 0.9);
            }
        }

        return totalTime;
    }

    /**
     * 生成全排列
     */
    private List<List<RelayRunner>> generatePermutations(List<RelayRunner> list) {
        List<List<RelayRunner>> result = new ArrayList<>();
        permuteHelper(list, 0, result);
        return result;
    }

    private void permuteHelper(List<RelayRunner> list, int start, 
                               List<List<RelayRunner>> result) {
        if (start == list.size()) {
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < list.size(); i++) {
            Collections.swap(list, start, i);
            permuteHelper(list, start + 1, result);
            Collections.swap(list, start, i);
        }
    }

    /**
     * 动态规划版本（适用于更多选手）
     * dp[mask][last] = 已安排mask中选手、last跑最后一棒的最短时间
     */
    public RelayAssignment findOptimalOrderDP() {
        int n = runners.size();
        int fullMask = (1 << n) - 1;

        // dp[mask][last] = minTime
        double[][] dp = new double[1 << n][n];
        int[][] parent = new int[1 << n][n];

        for (int i = 0; i < (1 << n); i++) {
            Arrays.fill(dp[i], Double.MAX_VALUE);
            Arrays.fill(parent[i], -1);
        }

        // 初始化：第一棒
        for (int i = 0; i < n; i++) {
            dp[1 << i][i] = runners.get(i).runTime(legDistances[0]);
        }

        // DP递推
        for (int mask = 1; mask <= fullMask; mask++) {
            int legCount = Integer.bitCount(mask);
            if (legCount >= 4) continue; // 只需4棒

            for (int last = 0; last < n; last++) {
                if ((mask & (1 << last)) == 0) continue;
                if (dp[mask][last] == Double.MAX_VALUE) continue;

                for (int next = 0; next < n; next++) {
                    if ((mask & (1 << next)) != 0) continue;

                    int newMask = mask | (1 << next);
                    double time = dp[mask][last] + 
                        calculateLegTime(last, next, legCount);

                    if (time < dp[newMask][next]) {
                        dp[newMask][next] = time;
                        parent[newMask][next] = last;
                    }
                }
            }
        }

        // 找最优解（4人排列）
        double bestTime = Double.MAX_VALUE;
        int bestLast = -1;
        int targetMask = 0;
        for (int i = 0; i < n && i < 4; i++) targetMask |= (1 << i);

        for (int last = 0; last < n; last++) {
            if (dp[targetMask][last] < bestTime) {
                bestTime = dp[targetMask][last];
                bestLast = last;
            }
        }

        // 回溯
        List<RelayRunner> order = new ArrayList<>();
        int mask = targetMask;
        int last = bestLast;
        while (last != -1) {
            order.add(0, runners.get(last));
            int p = parent[mask][last];
            mask ^= (1 << last);
            last = p;
        }

        return new RelayAssignment(order, bestTime);
    }

    private double calculateLegTime(int prevIdx, int currIdx, int legNum) {
        RelayRunner prev = runners.get(prevIdx);
        RelayRunner curr = runners.get(currIdx);
        double distance = legDistances[legNum];

        // 估算入棒速度
        double entrySpeed = prev.getMaxSpeed() * Math.pow(prev.endurance, 0.9);

        // 交接损失
        HandoffSimulator.HandoffResult handoff = 
            simulator.simulateHandoff(prev, curr, entrySpeed);

        return curr.runTime(distance) + handoff.timeLoss;
    }

    static class RelayAssignment {
        List<RelayRunner> order;
        double totalTime;

        RelayAssignment(List<RelayRunner> order, double totalTime) {
            this.order = order;
            this.totalTime = totalTime;
        }

        public void print() {
            System.out.println("=== 最优棒次安排 ===");
            System.out.printf("预计总时间: %.2f秒\n", totalTime);
            for (int i = 0; i < order.size(); i++) {
                System.out.printf("第%d棒: %s\n", i + 1, order.get(i));
            }
        }
    }
}

3.4 可视化与主程序

public class RelayRaceSimulator {
    public static void main(String[] args) {
        // 创建4位选手（模拟真实运动员数据）
        List<RelayRunner> team = Arrays.asList(
            new RelayRunner("闪电", 11.5, 8.5, 0.95, 0.85, 0.15), // 起跑快
            new RelayRunner("疾风", 11.8, 7.8, 0.92, 0.90, 0.18), // 交接好
            new RelayRunner("奔雷", 11.6, 8.0, 0.93, 0.88, 0.16), // 均衡
            new RelayRunner("追影", 12.0, 7.5, 0.90, 0.92, 0.20)  // 冲刺强
        );

        System.out.println("=== 4×100米接力赛最优策略求解器 ===\n");
        System.out.println("选手信息:");
        for (RelayRunner r : team) {
            System.out.println("  " + r);
        }
        System.out.println();

        RelayTeamOptimizer optimizer = new RelayTeamOptimizer(team);

        // 方法1：全排列枚举
        System.out.println("--- 全排列枚举 ---");
        RelayTeamOptimizer.RelayAssignment assignment1 = optimizer.findOptimalOrder();
        assignment1.print();

        System.out.println();

        // 方法2：动态规划
        System.out.println("--- 动态规划 ---");
        RelayTeamOptimizer.RelayAssignment assignment2 = optimizer.findOptimalOrderDP();
        assignment2.print();

        // 对比所有排列
        System.out.println("\n=== 所有棒次方案对比 ===");
        List<List<RelayRunner>> allPerm = generateAllPermutations(team);
        int idx = 1;
        for (List<RelayRunner> order : allPerm) {
            double time = simulateSimple(order);
            StringBuilder sb = new StringBuilder();
            for (RelayRunner r : order) sb.append(r.getName()).append(" ");
            System.out.printf("方案%2d: %s -> %.2f秒\n", idx++, sb.toString().trim(), time);
        }
    }

    private static double simulateSimple(List<RelayRunner> order) {
        double total = 0;
        for (int i = 0; i < 4; i++) {
            total += order.get(i).runTime(100);
            if (i > 0) total += 0.2 * (1.1 - order.get(i).getHandoffSkill());
        }
        return total;
    }

    private static List<List<RelayRunner>> generateAllPermutations(List<RelayRunner> list) {
        List<List<RelayRunner>> result = new ArrayList<>();
        permute(list, 0, result);
        return result;
    }

    private static void permute(List<RelayRunner> list, int start, 
                                List<List<RelayRunner>> result) {
        if (start == list.size()) {
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = start; i < list.size(); i++) {
            RelayRunner tmp = list.get(start);
            list.set(start, list.get(i));
            list.set(i, tmp);
            permute(list, start + 1, result);
            list.set(i, list.get(start));
            list.set(start, tmp);
        }
    }
}

四、复杂度分析

其中 N 为选手数，L 为棒数（通常4）。

五、实际策略建议

5.1 经典棒次安排原则

1. 第一棒：起跑反应快、弯道技术好（100m含弯道）
2. 第二棒：速度稳定、交接技术好
3. 第三棒：弯道能力强
4. 第四棒：冲刺能力最强、心理素质好

5.2 交接技术要点

• 上挑式：传棒者掌心向上，接棒者掌心向下——适合高速交接
• 下压式：传棒者掌心向下，接棒者掌心向上——稳定性高
• 预跑时机：接棒者在传棒者进入交接区时启动，20米区内完成交接

六、扩展方向

1. 4×400米接力：加入疲劳累积和配速策略
2. 混合接力：男女选手不同能力组合优化
3. 实时数据：基于训练数据动态调整棒次
4. 风阻模拟：顺风/逆风对交接的影响

七、总结

接力赛优化的核心是组合优化与物理模拟的结合。通过动态规划求解最优棒次分配、通过运动学模拟精确计算交接时间损失，我们可以为教练团队提供数据驱动的决策支持。虽然4人4棒的规模不大，但其中蕴含的资源分配与时序协调思想，在物流调度、生产排程等领域有广泛应用。