Jas*_*son 3 c# algorithm brute-force divide-and-conquer
我有一个分配比较2个不同算法的问题.这是问题所在:
假设我有一系列像这样的xy坐标:
A(2,3),B(5,6),C(7,8),D(6,2),E(5,5)等.
我想找到两条距离最短的坐标.其中一个解决方案是使用蛮力(逐个匹配),但还有另一种使用"分而治之"方法的解决方案.
你能用"分而治之"的方法帮助我吗？
dre*_*ash 5
递归分而治之的方法如下:
1)根据x坐标对点进行排序. 2)通过垂直线x = xmid将点集分成两个相等大小的子集. 3)在左右子集中递归地解决问题.这分别 产生左侧和右侧最小距离dLmin和dRmin. 4)找到一对点中的最小距离dLRmin,其中一个点位于分割垂直的左侧,第二个点位于右侧. 5)最终答案是dLmin,dRmin和dLRmin中的最小值.(来源)
1)根据x坐标对点进行排序. 2)通过垂直线x = xmid将点集分成两个相等大小的子集.
3)在左右子集中递归地解决问题.这分别 产生左侧和右侧最小距离dLmin和dRmin.
4)找到一对点中的最小距离dLRmin,其中一个点位于分割垂直的左侧,第二个点位于右侧.
5)最终答案是dLmin,dRmin和dLRmin中的最小值.(来源)
它有一个复杂的O(n log n).还有一个伪代码实现这里和方法的直观描述这里.
O(n log n)
归档时间：
13 年，1 月 前
查看次数：
1032 次
最近记录：
6 年，11 月 前