每日算法 — 使用java实现挑棍：稳定结构检测与贪心最优抽取策略

引言

挑棍（Pick-up Sticks）是一款风靡全球的童年益智游戏。玩家将一把彩色细棍随意撒落在桌面上，形成相互交叠的复杂结构，然后轮流抽取一根细棍，每次只能移动目标棍子而不触动其他棍子。一旦移动过程中触碰到其他棍子，回合即告结束。这一看似靠运气的游戏，实际上蕴含着丰富的几何判断与策略选择问题：如何判断一根棍子是否”安全”可抽？在众多可抽取的棍子中，哪一根能让后续局面最有利？本文将用Java实现挑棍游戏的稳定结构检测系统，讲解线段相交判定算法与贪心最优抽取策略。

算法原理

线段相交判定

挑棍的核心问题是线段相交检测：给定两根线段，判断它们是否在平面内相交。常用的方法是跨立实验（Orientation Test），基于向量叉积的符号来判断点的相对位置。

对于三点 $A$, $B$, $C$，定义方向函数：

$$orientation(A, B, C) = (B_x – A_x)(C_y – A_y) – (B_y – A_y)(C_x – A_x)$$

结果为正值：$C$ 在向量 $AB$ 的左侧
结果为负值：$C$ 在向量 $AB$ 的右侧
结果为零：$A$, $B$, $C$ 三点共线

两条线段 $AB$ 和 $CD$ 相交的充要条件是：
– $A$ 和 $B$ 分别位于直线 $CD$ 的两侧（或其中一点在直线上）
– $C$ 和 $D$ 分别位于直线 $AB$ 的两侧（或其中一点在直线上）

贪心抽取策略

判断一根棍子是否可安全抽取，需要检查它是否与任何其他棍子相交。若不相交，则该棍子位于结构的最上层，可直接抽取。

贪心策略：在每一轮中，优先抽取被压棍子数最少的棍子。这种策略的直觉是：被压最少的棍子最容易抽出，且抽出后对整体结构影响最小，为后续操作保留更多选择。

Java实现

1. 几何基础类

/**
 * 二维点：表示细棍的端点坐标
 */
public class Point {
    public final double x;
    public final double y;

    public Point(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return String.format("(%.2f, %.2f)", x, y);
    }
}

/**
 * 线段：表示一根细棍
 */
public class Stick {
    public final Point p1;      // 起点
    public final Point p2;      // 终点
    public final int id;        // 编号
    public final String color;  // 颜色

    public Stick(int id, Point p1, Point p2, String color) {
        this.id = id;
        this.p1 = p1;
        this.p2 = p2;
        this.color = color;
    }

    /** 计算线段中点 */
    public Point getCenter() {
        return new Point((p1.x + p2.x) / 2.0, (p1.y + p2.y) / 2.0);
    }

    /** 计算线段长度 */
    public double getLength() {
        return Math.hypot(p2.x - p1.x, p2.y - p1.y);
    }

    @Override
    public String toString() {
        return String.format("Stick%d[%s] %s-%s", id, color, p1, p2);
    }
}

2. 线段相交检测引擎

/**
 * 几何引擎：提供线段相交检测与方向判断
 */
public class GeometryEngine {

    /**
     * 计算三点的方向（叉积符号）
     * @return >0 左侧, <0 右侧, =0 共线
     */
    public static double orientation(Point a, Point b, Point c) {
        return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    }

    /**
     * 判断点p是否在线段ab上（假设三点共线）
     */
    public static boolean onSegment(Point a, Point b, Point p) {
        return Math.min(a.x, b.x) <= p.x && p.x <= Math.max(a.x, b.x)
            && Math.min(a.y, b.y) <= p.y && p.y <= Math.max(a.y, b.y);
    }

    /**
     * 判断两条线段是否相交（包含端点接触的情况）
     */
    public static boolean segmentsIntersect(Stick s1, Stick s2) {
        Point a = s1.p1, b = s1.p2;
        Point c = s2.p1, d = s2.p2;

        double o1 = orientation(a, b, c);
        double o2 = orientation(a, b, d);
        double o3 = orientation(c, d, a);
        double o4 = orientation(c, d, b);

        // 一般情况：两线段互相跨立
        if (o1 * o2 < 0 && o3 * o4 < 0) {
            return true;
        }

        // 特殊情况：某点恰好在另一条线段上
        if (o1 == 0 && onSegment(a, b, c)) return true;
        if (o2 == 0 && onSegment(a, b, d)) return true;
        if (o3 == 0 && onSegment(c, d, a)) return true;
        if (o4 == 0 && onSegment(c, d, b)) return true;

        return false;
    }

    /**
     * 计算两条线段的交点（若相交）
     * @return 交点坐标，若不相交返回null
     */
    public static Point getIntersection(Stick s1, Stick s2) {
        if (!segmentsIntersect(s1, s2)) return null;

        Point a = s1.p1, b = s1.p2;
        Point c = s2.p1, d = s2.p2;

        double denom = (a.x - b.x) * (c.y - d.y) - (a.y - b.y) * (c.x - d.x);
        if (Math.abs(denom) < 1e-10) return null;  // 平行

        double px = ((a.x * b.y - a.y * b.x) * (c.x - d.x)
                   - (a.x - b.x) * (c.x * d.y - c.y * d.x)) / denom;
        double py = ((a.x * b.y - a.y * b.x) * (c.y - d.y)
                   - (a.y - b.y) * (c.x * d.y - c.y * d.x)) / denom;
        return new Point(px, py);
    }
}

3. 挑棍游戏核心逻辑

import java.util.*;

/**
 * 挑棍游戏引擎：管理棍子状态与抽取策略
 */
public class PickUpSticksGame {
    private final List<Stick> sticks;           // 所有棍子
    private final boolean[] removed;            // 是否已被移除
    private final int[][] intersectionCount;    // 相交计数矩阵

    public PickUpSticksGame(List<Stick> sticks) {
        this.sticks = new ArrayList<>(sticks);
        this.removed = new boolean[sticks.size()];
        this.intersectionCount = new int[sticks.size()][sticks.size()];
        computeIntersections();
    }

    /** 预计算所有棍子之间的相交关系 */
    private void computeIntersections() {
        int n = sticks.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (GeometryEngine.segmentsIntersect(sticks.get(i), sticks.get(j))) {
                    intersectionCount[i][j] = 1;
                    intersectionCount[j][i] = 1;
                }
            }
        }
    }

    /**
     * 判断一根棍子是否可以安全抽取
     * 条件：该棍子没有被其他未移除的棍子压住（即不与任何未移除棍子相交）
     */
    public boolean canPick(int stickIndex) {
        if (removed[stickIndex]) return false;
        for (int i = 0; i < sticks.size(); i++) {
            if (i != stickIndex && !removed[i] && intersectionCount[stickIndex][i] > 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 获取所有可安全抽取的棍子索引
     */
    public List<Integer> getPickableSticks() {
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < sticks.size(); i++) {
            if (canPick(i)) {
                result.add(i);
            }
        }
        return result;
    }

    /**
     * 获取指定棍子当前被多少根未移除的棍子压住
     */
    public int getPressureCount(int stickIndex) {
        int count = 0;
        for (int i = 0; i < sticks.size(); i++) {
            if (i != stickIndex && !removed[i] && intersectionCount[stickIndex][i] > 0) {
                count++;
            }
        }
        return count;
    }

    /**
     * 贪心策略：选择被压最少的可抽取棍子
     * @return 最优棍子索引，无可抽取则返回 -1
     */
    public int greedyPick() {
        List<Integer> pickable = getPickableSticks();
        if (pickable.isEmpty()) return -1;

        // 在可抽取的棍子中，选择被压最少的（最安全的）
        int best = pickable.get(0);
        int minPressure = Integer.MAX_VALUE;
        for (int idx : pickable) {
            int pressure = getPressureCount(idx);
            if (pressure < minPressure) {
                minPressure = pressure;
                best = idx;
            }
        }
        return best;
    }

    /**
     * 执行抽取操作
     * @return true 表示抽取成功
     */
    public boolean pick(int stickIndex) {
        if (!canPick(stickIndex)) return false;
        removed[stickIndex] = true;
        return true;
    }

    /**
     * 检查游戏是否结束（所有棍子被移除或无法继续）
     */
    public boolean isGameOver() {
        return getPickableSticks().isEmpty();
    }

    /**
     * 获取剩余棍子数量
     */
    public int getRemainingCount() {
        int count = 0;
        for (boolean r : removed) {
            if (!r) count++;
        }
        return count;
    }

    /**
     * 打印当前游戏状态
     */
    public void printState() {
        System.out.println("=== 当前游戏状态 ===");
        for (int i = 0; i < sticks.size(); i++) {
            if (!removed[i]) {
                int pressure = getPressureCount(i);
                boolean pickable = canPick(i);
                System.out.printf("  %s | 被压: %d | 可抽: %s%n",
                    sticks.get(i), pressure, pickable ? "是" : "否");
            }
        }
        System.out.printf("剩余棍子: %d%n%n", getRemainingCount());
    }
}

4. 主程序演示

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * 挑棍游戏主程序
 */
public class PickUpSticksDemo {

    public static void main(String[] args) {
        Random random = new Random(42);
        int n = 12;  // 12根棍子
        List<Stick> sticks = new ArrayList<>();
        String[] colors = {"红", "蓝", "绿", "黄", "紫", "橙"};

        // 随机生成棍子
        System.out.println("=== 生成随机棍子 ===");
        for (int i = 0; i < n; i++) {
            double x1 = random.nextDouble() * 10;
            double y1 = random.nextDouble() * 10;
            double angle = random.nextDouble() * Math.PI;
            double length = 2.0 + random.nextDouble() * 3.0;
            double x2 = x1 + length * Math.cos(angle);
            double y2 = y1 + length * Math.sin(angle);
            sticks.add(new Stick(i, new Point(x1, y1), new Point(x2, y2), colors[i % colors.length]));
            System.out.println("  " + sticks.get(i));
        }

        PickUpSticksGame game = new PickUpSticksGame(sticks);

        // 预计算相交关系
        System.out.println("\n=== 相交关系矩阵 ===");
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (GeometryEngine.segmentsIntersect(sticks.get(i), sticks.get(j))) {
                    Point inter = GeometryEngine.getIntersection(sticks.get(i), sticks.get(j));
                    System.out.printf("  Stick%d 与 Stick%d 相交于 %s%n", i, j, inter);
                }
            }
        }

        System.out.println("\n=== 开始游戏（贪心策略） ===");
        game.printState();

        int round = 1;
        while (!game.isGameOver()) {
            int pick = game.greedyPick();
            if (pick < 0) break;

            Stick s = sticks.get(pick);
            System.out.printf("第%d轮: 抽取 %s%n", round, s);
            game.pick(pick);
            game.printState();
            round++;
        }

        System.out.println("=== 游戏结束 ===");
        int remaining = game.getRemainingCount();
        System.out.printf("共进行 %d 轮，剩余 %d 根棍子无法抽取%n", round - 1, remaining);
        if (remaining == 0) {
            System.out.println("恭喜！成功移除所有棍子！");
        } else {
            System.out.println("部分棍子被锁住，需要更巧妙的策略。");
        }
    }
}

复杂度分析

操作	时间复杂度	空间复杂度	说明
相交检测（两线段）	$O(1)$	$O(1)$	常数次算术运算
预计算所有相交	$O(n^2)$	$O(n^2)$	$n$ 为棍子数量
判断单根可抽取	$O(n)$	$O(1)$	遍历所有其他棍子
获取所有可抽取	$O(n^2)$	$O(n)$	对每根棍子做判断
贪心选择	$O(n^2)$	$O(n)$	先找可抽取，再算压力

扩展思考

Z-Order排序优化：按棍子的Z坐标（高度）排序后，只需检测相邻层级的相交关系，可将预处理降至 $O(n \log n)$（在均匀分布假设下）。
回溯策略改进：贪心策略在局部最优时可能陷入全局死局。引入回溯搜索，在每一步尝试所有可行选择，通过DFS寻找能清空所有棍子的最优序列。
物理模拟增强：加入弹性形变和摩擦力模拟，使”触碰”判断更贴近真实物理场景。

总结

本文通过Java实现了挑棍游戏的完整模拟系统，核心要点包括：

跨立实验利用向量叉积符号判断线段相交，是计算几何的基础工具
相交矩阵预处理所有棍子间的空间关系，将运行时查询优化至 $O(1)$
贪心抽取策略优先选择被压最少的棍子，在局部最优与操作可行性之间取得平衡

挑棍将几何判断与策略选择融为一体，是理解计算几何和贪心算法的趣味案例。通过扩展回溯搜索，还能进一步探索组合优化的奥秘。

Tagged with: 挑棍线段相交计算几何贪心策略跨立实验