我正在尝试使用分层搜索(在树中)找到包含点的最小圆。我搜索了很多，我似乎只在网上找到最小的封闭圆(奇异)算法。这是大学类(class)，所以我要求的可能解决方案和想法比实际代码更多。
我的问题是我有一个公式涉及两个常数和一个圆的半径来计算它的成本，我需要最小化总成本。这意味着对于一组点 (x,y)，我可以找到一个包含所有点的圆，或多个圆，每个圆包含一部分点，具体取决于每个圆的成本。
举个例子，如果公式是1+2*半径**2，我的答案肯定会有多个小圆圈。所有点都必须在最后一个圆圈内。
我的目标是使用 a*、分支定界或广度优先等图搜索算法，并使用状态及其可能的操作构建树。
我目前正在尝试将可能的操作写成添加圆、删除圆和更改圆的半径。为了限制计算时间，我决定只在两点之间或两组点之间(圆心可能所在的位置)尝试这些操作。但是这个算法似乎远非最优。如果您有任何想法，那真的对我有帮助。
无论如何感谢您的帮助。
如果问题不清楚，请告诉我。
最佳答案
我将专注于寻找最佳解决方案。如果您对近似解决方案持开放态度，您会有更多选择，而且我相信还会有其他答案。
我会通过将其表述为整数程序来解决这个问题。抽象地说，程序看起来像
variable x_C: 1 if circle C is chosen; 0 if circle C is not chosen
minimize sum_C cost(C) * x_C
subject to
for all points p, sum_{C containing p} x_C >= 1
for all circles C, x_C in {0, 1}.
现在，当然有无限多个圆圈，但假设一个圆圈的面积严格地大于另一个圆圈的成本更高，则可以合理选择 O(n^3) 个圆圈，其中 n 是点数.这些是恰好覆盖一个点的退化圆；两点形成直径的圆；以及通过三点的圆圈。您将编写代码，以整数程序求解器(例如 GLPK)接受的格式将抽象整数程序扩展为具体程序，然后运行求解器。
整数程序的大小为 O(n^4)，这对于较大的实例而言过于昂贵。为了降低成本，您需要生成列。这是您需要弄清楚求解器的编程接口(interface)的地方。您将寻找一个选项，在解决整数程序的线性松弛时，用每个点的当前价格回调您的代码，并期望一个可选的圆，其成本小于点的价格之和它包含。
生成列的原始算法仍然是 O(n^4)，但如果切换到扫描算法，成本将是 O(n^3 log n)。给定一对点，想象所有经过这些点的圆。所有的圆心都位于垂直平分线上。对于每个其他点，都有一个圆心间隔，圆围绕该点。计算所有这些事件点数，对它们进行排序，然后按顺序处理事件，同时更新封闭点数的当前总价。 (由于圆圈是封闭的，所以在出发之前处理到达。)
如果您想进一步插入这一点，请查看分支和价格。高级分支变量将决定是否用相同的圆覆盖两个点。
关于python - 以最小成本包围点的最小圆，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35255345/