5 月，Stackoverflow 上有一个问题，R 中的 3 维预测限制， “最小封闭矩形”问题的特殊形式。因为这个问题在那里还没有解决，所以我想在这里把它表述为离散优化中的一个问题，并希望有一个有效的算法来准确地解决它。
例如，给定二维中的 N 个点，找到一个
包含至少 95% 点的最小面积的轴平行矩形。
我知道并不总是有解决方案，例如当所有点都位于矩形的边界上时。所以让我们假设这些点在某种程度上处于一般位置，即使没有两个点具有完全相同的 x 或 y 坐标。
我知道可以通过循环遍历所有 x 和 y 坐标来找到解决方案。低于 0.05 或高于 0.95 的分位数。当然，我希望有一种更智能、更高效的算法方法。
你的问题是
例如，给定个点，找到一个包含至少 95% 点的最小面积的轴平行矩形。
这本质上等价于以下问题（最小点封闭矩形），已知有效的确定性算法：
给定二维中的个点的最小面积的平行轴正方形或矩形。
一些参考资料：
在最小轴平行矩形中封闭- Segal 和 Kedem，信息处理快报，1998
用最小的封闭正方形寻找- Smid，1995。
最小的-点包围任意方向的矩形和正方形- Das 等人，信息处理快报，2005
这是一个算法的草图，尽管我没有证据表明它总是产生最小值。
goal = 0.95*points.size()
rect = smallest_rectangle_containing_all(points)
while(rect.number_of_points() > goal):
old_rect = rect
rect.maximally_shrink_by_omitting_at_least_one_point()
if(rect.number_of_points() < goal)
rect = old_rect;
哪里rectangle::maximally_shrink_by_omitting_at_least_one_point()有点棘手，但其他方面很简单（我把它的实现留给你）。
您可以尝试非确定性算法，例如模拟退火。他们不确定得到数学上准确的答案，但他们可以相当快地得到一个很好的近似值。
如果是维度，那么有 2要设置的值（两个对角的位置）。1. 从 2.5% 和 97.5% 的角开始（如果分布表现良好，则为良好的近似值）。这是一维的，否则而不是 2.5%。2.从这两个中选择两个值，增加（分别减少）两者之一并减少（分别增加）另一个以回到 95%。如果面积较小，请保留它。否则，应用您的策略（例如模拟退火：保持它的概率随着时间的推移而下降）。3. 重复。