山东省青岛市黄岛区峨眉山路396号27号楼4楼 18835847858 MILE@j9.com

游戏中心

依次筛选摆放点为什么顺序会改变结果:独立演算第06例

2026-11-08

摆放装饰或出生标记时,可以逐个接受与已有点足够远的候选。这个方法很容易保证间距,但早先接受的点也会使后面的点失去机会。

候选点在同一二维平面上,要求所有已接受点之间距离至少为r。按给定顺序扫描,只有与每个已有点的距离平方都不小于r平方才接受;空集合直接接受第一个点。再用完全相反的顺序重复。

这一例的完整输入

候选坐标依次为[(8, 5), (19, 13), (0, 7), (15, 7), (15, 13), (19, 0), (0, 5), (19, 5), (18, 1), (10, 14), (11, 5), (6, 14), (13, 11), (20, 14)],最小间距4,比较阈值平方16。

逐项计算记录

正序:编号 | 当时最近距离平方及对象 | 接受 0 | None | 是 1 | (185, 0) | 是 2 | (68, 0) | 是 3 | (52, 1) | 是 4 | (16, 1) | 是 5 | (65, 3) | 是 6 | (4, 2) | 否 7 | (20, 3) | 是 8 | (2, 5) | 否 9 | (26, 4) | 是 10 | (9, 0) | 否 11 | (16, 9) | 是 12 | (8, 4) | 否 13 | (2, 1) | 否 最终接受编号:[0, 1, 2, 3, 4, 5, 7, 9, 11] 反序:编号 | 当时最近距离平方及对象 | 接受 13 | None | 是 12 | (58, 13) | 是 11 | (58, 12) | 是 10 | (40, 12) | 是 9 | (16, 11) | 是 8 | (65, 10) | 是 7 | (17, 8) | 是 6 | (117, 11) | 是 5 | (2, 8) | 否 4 | (8, 12) | 否 3 | (20, 7) | 是 2 | (4, 6) | 否 1 | (2, 13) | 否 0 | (9, 10) | 否 最终接受编号:[13, 12, 11, 10, 9, 8, 7, 6, 3]

读表时先把输入与计算后的结果分开。空值表示这一步没有适用对象或没有可用结果,不应自动换成零。编号只负责识别本例中的元素,同一个数字出现在不同字段时,要先确认它代表位置、对象还是数值。

怎样复核和使用

使用平方距离可以避免开平方及边界舍入。等于阈值仍允许,两次扫描都要从空集合开始。验证每个被拒点在当时有一个过近的已接受点,不能拿后来才接受的点解释过去的拒绝。

这个贪心筛选保证的是最小间距,不保证接受点最多、覆盖最均匀或接近某种理想随机分布。若场地有障碍和不同尺寸对象,应先加入相应的合法性条件。

可以先遮住记录表,只按上述规则重算前两步,再选择一个边界条件重新试算。若结果不一致,应逐项检查输入顺序、端点是否包含以及状态在哪一步更新;不要只看最终合计相同就认为中间处理也完全正确。