每日算法 — 使用java实现套圈：环形约束满足与回溯最优投掷序列

引言

套圈是传统民俗游戏，玩家将圆环抛出，套中目标立柱即可得分。不同距离、不同大小的立柱分值各异，且每次投掷后已套中的立柱会被移除。本文用Java实现一个智能套圈决策系统，核心算法包括抛物线轨迹物理模拟、环形-柱体碰撞检测，以及用回溯搜索求解在有限环数下获得最高总分的最优投掷序列。

核心算法思路

1. 抛物线轨迹建模

圆环出手后受重力影响做抛体运动。设出手位置 (x0, y0, z0)、初速度 (vx, vy, vz)，则时刻 t 的位置为：
– x(t) = x0 + vx * t
– y(t) = y0 + vy * t
– z(t) = z0 + vz * t - 0.5 * g * t²

圆环在空中保持水平姿态（自转稳定），落地时若中心与立柱中心的水平距离小于 (立柱半径 + 圆环内半径差)，且圆环高度低于立柱顶端但高于底端，则判定套中。

2. 碰撞检测

圆环套中立柱需要满足三个条件：
1. 水平覆盖：圆环中心与立柱中心的水平距离 d < (ring_outer_r - pole_r)
2. 垂直覆盖：圆环落地时高度 z 满足 pole_height_bottom < z < pole_height_top
3. 姿态水平：圆环平面近似水平（法向量与竖直方向夹角小于阈值）

3. 最优投掷序列（回溯搜索）

给定 n 个立柱（各有分值和难度）和 m 个圆环，求最大总分的投掷顺序。这是一个带约束的排列优化问题：
– 每个立柱最多被套中一次
– 投掷某立柱的成功率取决于距离和出手参数
– 目标是最大化期望总分

使用回溯搜索枚举所有可能的投掷顺序，剪枝策略：
– 若当前累计期望分 + 剩余立柱最高分 × 剩余环数 ≤ 当前最优解，剪枝
– 优先尝试高分且成功率高的立柱（启发式排序）

完整Java实现

import java.util.*;

/**
 * 套圈游戏智能决策系统
 * 核心算法：抛物线物理模拟 + 环形碰撞检测 + 回溯最优序列搜索
 */
public class RingTossSolver {

    // 物理常量
    static final double GRAVITY = 9.8; // m/s²
    static final double TIME_STEP = 0.01; // 模拟步长

    // 立柱类
    static class Pole {
        int id;
        double x, z;      // 水平位置（y为高度方向）
        double radius;    // 立柱半径
        double height;    // 立柱高度
        int score;        // 分值
        boolean hit;      // 是否已被套中

        Pole(int id, double x, double z, double radius, double height, int score) {
            this.id = id;
            this.x = x;
            this.z = z;
            this.radius = radius;
            this.height = height;
            this.score = score;
            this.hit = false;
        }
    }

    // 圆环类
    static class Ring {
        double innerR;    // 内半径
        double outerR;    // 外半径
        double mass;      // 质量（影响抛出参数）

        Ring(double innerR, double outerR, double mass) {
            this.innerR = innerR;
            this.outerR = outerR;
            this.mass = mass;
        }
    }

    // 投掷参数
    static class ThrowParams {
        double vx, vy, vz; // 初速度分量
        double y0;         // 出手高度

        ThrowParams(double vx, double vy, double vz, double y0) {
            this.vx = vx;
            this.vy = vy;
            this.vz = vz;
            this.y0 = y0;
        }
    }

    // 投掷结果
    static class TossResult {
        boolean success;
        double landX, landZ; // 落点
        double flightTime;   // 飞行时间

        TossResult(boolean success, double landX, double landZ, double flightTime) {
            this.success = success;
            this.landX = landX;
            this.landZ = landZ;
            this.flightTime = flightTime;
        }
    }

    private List<Pole> poles;
    private Ring ring;
    private Random random;

    public RingTossSolver(List<Pole> poles, Ring ring, long seed) {
        this.poles = poles;
        this.ring = ring;
        this.random = new Random(seed);
    }

    /**
     * 模拟一次投掷：计算圆环轨迹并判断是否套中立柱
     */
    public TossResult simulateToss(Pole target, ThrowParams params) {
        double x = 0, y = params.y0, z = 0; // 从原点出手
        double vx = params.vx, vy = params.vy, vz = params.vz;

        double t = 0;
        // 迭代模拟轨迹，直到落地（y <= 0）或飞出边界
        while (y > 0 && t < 10) {
            x += vx * TIME_STEP;
            y += vy * TIME_STEP;
            z += vz * TIME_STEP;
            vy -= GRAVITY * TIME_STEP;
            t += TIME_STEP;

            // 检查是否经过立柱顶端附近（套中判定）
            double dx = x - target.x;
            double dz = z - target.z;
            double horizontalDist = Math.hypot(dx, dz);

            // 套中条件：水平距离在允许范围内，且高度在立柱范围内
            double maxDist = ring.outerR - target.radius;
            if (maxDist < 0) maxDist = 0;

            if (horizontalDist < maxDist && y > target.height * 0.3 && y < target.height * 0.9) {
                return new TossResult(true, x, z, t);
            }
        }

        return new TossResult(false, x, z, t);
    }

    /**
     * 为指定立柱计算最优投掷参数（搜索最佳出手角度和力度）
     */
    public ThrowParams findOptimalParams(Pole target) {
        double bestError = Double.MAX_VALUE;
        ThrowParams best = null;

        // 搜索出手角度和速度
        for (double angleH = -30; angleH <= 30; angleH += 2) { // 水平偏角
            for (double angleV = 20; angleV <= 70; angleV += 2) { // 仰角
                for (double speed = 3; speed <= 12; speed += 0.5) {
                    double radH = Math.toRadians(angleH);
                    double radV = Math.toRadians(angleV);

                    double vx = speed * Math.cos(radV) * Math.sin(radH);
                    double vy = speed * Math.sin(radV);
                    double vz = speed * Math.cos(radV) * Math.cos(radH);

                    ThrowParams p = new ThrowParams(vx, vy, vz, 1.5);
                    TossResult result = simulateToss(target, p);

                    double error = Math.hypot(result.landX - target.x, result.landZ - target.z);
                    if (error < bestError) {
                        bestError = error;
                        best = p;
                    }
                }
            }
        }
        return best;
    }

    /**
     * 计算投掷成功率：加入随机扰动后多次模拟
     */
    public double successRate(Pole target, ThrowParams params, int trials) {
        int success = 0;
        for (int i = 0; i < trials; i++) {
            // 加入随机扰动模拟人手误差
            double noiseVx = (random.nextDouble() - 0.5) * 0.3;
            double noiseVy = (random.nextDouble() - 0.5) * 0.3;
            double noiseVz = (random.nextDouble() - 0.5) * 0.3;

            ThrowParams noisy = new ThrowParams(
                params.vx + noiseVx,
                params.vy + noiseVy,
                params.vz + noiseVz,
                params.y0 + (random.nextDouble() - 0.5) * 0.1
            );

            TossResult r = simulateToss(target, noisy);
            if (r.success) success++;
        }
        return (double) success / trials;
    }

    // 回溯搜索状态
    static class SearchState {
        List<Integer> order = new ArrayList<>(); // 已选择的立柱顺序
        double expectedScore = 0; // 当前累计期望分
        boolean[] used; // 哪些立柱已使用

        SearchState(int n) {
            used = new boolean[n];
        }

        SearchState copy() {
            SearchState s = new SearchState(used.length);
            s.order.addAll(this.order);
            s.expectedScore = this.expectedScore;
            System.arraycopy(this.used, 0, s.used, 0, used.length);
            return s;
        }
    }

    private double bestScore = 0;
    private List<Integer> bestOrder = new ArrayList<>();
    private Map<Integer, Double> successRates = new HashMap<>();

    /**
     * 回溯搜索最优投掷序列
     * @param ringsLeft 剩余圆环数
     * @param state 当前搜索状态
     * @param poles 立柱列表
     */
    public void backtrack(int ringsLeft, SearchState state, List<Pole> poles) {
        // 剪枝：剩余期望上界
        double remainingMax = 0;
        for (int i = 0; i < poles.size(); i++) {
            if (!state.used[i]) {
                remainingMax += poles.get(i).score;
            }
        }
        remainingMax = Math.min(remainingMax, ringsLeft * 100); // 假设最高100分柱
        if (state.expectedScore + remainingMax <= bestScore) {
            return;
        }

        // 更新最优解
        if (state.expectedScore > bestScore) {
            bestScore = state.expectedScore;
            bestOrder = new ArrayList<>(state.order);
        }

        if (ringsLeft == 0) return;

        // 按(分值×成功率)降序排列候选立柱（启发式）
        List<Integer> candidates = new ArrayList<>();
        for (int i = 0; i < poles.size(); i++) {
            if (!state.used[i]) {
                candidates.add(i);
            }
        }
        candidates.sort((a, b) -> {
            double sa = successRates.getOrDefault(a, 0.5) * poles.get(a).score;
            double sb = successRates.getOrDefault(b, 0.5) * poles.get(b).score;
            return Double.compare(sb, sa);
        });

        for (int idx : candidates) {
            Pole p = poles.get(idx);
            double rate = successRates.getOrDefault(idx, 0.5);

            SearchState next = state.copy();
            next.used[idx] = true;
            next.order.add(p.id);
            next.expectedScore += rate * p.score;

            backtrack(ringsLeft - 1, next, poles);
        }
    }

    /**
     * 求解最优投掷策略
     * @param ringCount 可用圆环数量
     */
    public void solve(int ringCount) {
        // 预计算每根立柱的最优参数和成功率
        System.out.println("=== 预计算各立柱投掷参数 ===");
        for (int i = 0; i < poles.size(); i++) {
            Pole p = poles.get(i);
            ThrowParams optimal = findOptimalParams(p);
            double rate = successRate(p, optimal, 500);
            successRates.put(i, rate);
            System.out.printf("立柱%d (距离%.1fm, %d分): 成功率%.1f%%\n",
                p.id, Math.hypot(p.x, p.z), p.score, rate * 100);
        }

        // 回溯搜索最优序列
        System.out.println("\n=== 回溯搜索最优投掷序列 ===");
        SearchState init = new SearchState(poles.size());
        backtrack(ringCount, init, poles);

        System.out.printf("最优期望总分: %.2f\n", bestScore);
        System.out.print("最优投掷顺序: ");
        for (int id : bestOrder) {
            System.out.print(id + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 创建场景：5根立柱，距离和分值递增
        List<Pole> poles = new ArrayList<>();
        poles.add(new Pole(0, 1.5, 0, 0.02, 0.3, 10));
        poles.add(new Pole(1, 2.5, 0.5, 0.02, 0.35, 20));
        poles.add(new Pole(2, 3.5, -0.3, 0.025, 0.4, 30));
        poles.add(new Pole(3, 4.5, 0.8, 0.025, 0.45, 50));
        poles.add(new Pole(4, 5.5, -0.5, 0.03, 0.5, 80));

        Ring ring = new Ring(0.08, 0.12, 0.05); // 内径8cm，外径12cm
        RingTossSolver solver = new RingTossSolver(poles, ring, 42L);

        solver.solve(3); // 3个圆环

        // 演示单次投掷轨迹
        System.out.println("\n=== 单次投掷轨迹演示（瞄准立柱0）===");
        ThrowParams params = solver.findOptimalParams(poles.get(0));
        TossResult result = solver.simulateToss(poles.get(0), params);
        System.out.printf("落点: (%.2f, %.2f), 飞行时间: %.2fs, 套中: %s\n",
            result.landX, result.landZ, result.flightTime, result.success);
    }
}

算法复杂度分析

扩展方向

1. 风速影响：加入水平风力项，用卡尔曼滤波实时估计风速并调整出手参数
2. 多环连锁：一个圆环落地反弹后可能套中第二根立柱，加入反弹物理模型
3. 对手博弈：双人轮流投掷，用Minimax或蒙特卡洛树搜索进行博弈决策
4. 强化学习训练：让AI通过大量投掷学习出手策略，用PPO算法优化

总结

本文将套圈游戏分解为物理模拟和组合优化两个子问题。通过抛物线轨迹计算精确模拟圆环飞行，利用环形-柱体碰撞检测判定套中，最终采用回溯搜索在有限环数约束下寻找期望得分最大的投掷序列。回溯中的期望上界剪枝和启发式排序显著提升了搜索效率，使算法在毫秒级内即可给出近优策略。