python - 迭代分而治之算法

Question

我正在尝试使用分而治之的方法创建算法但是使用迭代算法(即没有递归)。

我对如何处理循环感到困惑。

我需要将我的问题分解成更小的子问题，直到找到一个基本案例。我认为这仍然是正确的，但后来我不确定如何(不使用递归)使用较小的子问题来解决更大的问题。

例如，我正在尝试提出一种算法来找到最近的一对点(在一维空间中 - 尽管我打算自己将其推广到更高的维度)。如果我有一个函数 closest_pair(L)，其中 L 是 ℝ 中的整数坐标列表，我怎么能想出一个分而治之的 ITERATIVE 算法来解决这个问题？

(不失一般性，我使用的是 Python)

Answer 1

将任何递归算法转换为迭代算法的廉价方法是采用递归函数，将其放入循环中，并使用您自己的堆栈。这消除了函数调用开销以及在堆栈上保存任何不需要的数据。但是，这通常不是“最佳”方法(“最佳”取决于问题和上下文。)

按照您对问题的表述方式，听起来好像是将列表分成子列表，在每个子列表中找到最接近的对，然后从这两个结果中取出最接近的对。要迭代地执行此操作，我认为比上面提到的通用方法更好的方法是从另一个方向开始:查看大小为 3 的列表(有三对要查看)并从那里开始。请注意，大小为 2 的列表很简单。

最后，如果您的坐标是整数，则它们位于 Z(R 的一个更小的子集)中。