最短连接算法，智力游戏
The shortest connection algorithm, mind game
这是智力游戏书中的一道题。我试过这样解决它 (http://pastebin.com/sdfcuxW1) 但没有运气。它还必须非常优化以在 4 秒内处理 2000 个输入坐标的输出。
任何关于我的代码的建议，或任何新的算法想法都会非常有帮助。
问题：
我们有一个坐标平面，我们只使用第一象限。我们提供了许多坐标，每个坐标都带有 +X 和 +Y 值。例如0,2 - 5,4等。我们需要将这些坐标中的每一个都与矩形连接起来（矩形的一个角接触一个坐标，另一个角接触另一个坐标），以便所有坐标都相互接触（没有遗漏）。我们还必须确保我们用来连接我们的 2 个坐标的矩形不与任何其他坐标重叠（在边缘上很好）。鉴于目标是尽可能使用最小的总矩形面积，什么样的算法可以打印出这个问题的最佳解决方案。
http://cl.ly/image/1P012s3p1E1g
紫色区域是矩形，绿点是坐标。我们可以拥有宽度为 0 的矩形，不占用任何面积。
我想不通的是：找到最接近我们起始坐标的坐标很容易。但很难确保所有坐标都连接在一起。我总是得到漂浮在飞机不同区域的坐标。我的代码也滞后了 >1000 分。
这是一个解决方案：
让我们将此问题建模为图形问题。
顶点是给定的点。
每对顶点之间都有一条边。这条边的权重就是这对点组成的矩形的面积。
答案就是这个图中的最小生成树。我们可以使用Prim的算法来找到它。
这个解的时间复杂度是O(n ^ 2)。
唯一的问题是：为什么这个算法生成的矩形不能包含另一个点？这里我不会post一个正式的证明，但是画一些图可以看出，如果有这样一个矩形，解决方案不是最优的（证明的想法：假设里面有一个点。我们可以拆分这个矩形一分为二，使这个点成为他们的一个角。执行此操作后总面积只能减少）。
这是智力游戏书中的一道题。我试过这样解决它 (http://pastebin.com/sdfcuxW1) 但没有运气。它还必须非常优化以在 4 秒内处理 2000 个输入坐标的输出。
任何关于我的代码的建议，或任何新的算法想法都会非常有帮助。
问题： 我们有一个坐标平面，我们只使用第一象限。我们提供了许多坐标，每个坐标都带有 +X 和 +Y 值。例如0,2 - 5,4等。我们需要将这些坐标中的每一个都与矩形连接起来（矩形的一个角接触一个坐标，另一个角接触另一个坐标），以便所有坐标都相互接触（没有遗漏）。我们还必须确保我们用来连接我们的 2 个坐标的矩形不与任何其他坐标重叠（在边缘上很好）。鉴于目标是尽可能使用最小的总矩形面积，什么样的算法可以打印出这个问题的最佳解决方案。
http://cl.ly/image/1P012s3p1E1g 紫色区域是矩形，绿点是坐标。我们可以拥有宽度为 0 的矩形，不占用任何面积。
我想不通的是：找到最接近我们起始坐标的坐标很容易。但很难确保所有坐标都连接在一起。我总是得到漂浮在飞机不同区域的坐标。我的代码也滞后了 >1000 分。
这是一个解决方案：
让我们将此问题建模为图形问题。
顶点是给定的点。
每对顶点之间都有一条边。这条边的权重就是这对点组成的矩形的面积。
答案就是这个图中的最小生成树。我们可以使用Prim的算法来找到它。
这个解的时间复杂度是O(n ^ 2)。
唯一的问题是：为什么这个算法生成的矩形不能包含另一个点？这里我不会post一个正式的证明，但是画一些图可以看出，如果有这样一个矩形，解决方案不是最优的（证明的想法：假设里面有一个点。我们可以拆分这个矩形一分为二，使这个点成为他们的一个角。执行此操作后总面积只能减少）。