迭代分而治之算法
Iterative Divide and Conquer algorithms
我正在尝试使用分而治之的方法创建算法但是使用迭代算法（即无递归）。
我对如何处理循环感到困惑。
我需要将我的问题分解成更小的子问题，直到找到一个基本案例。我认为这仍然是正确的，但我不确定如何（不使用递归）使用较小的子问题来解决更大的问题。
例如，我正在尝试提出一种算法来找到最近的一对点（在一维中 space - 虽然我打算自己将其推广到更高的维度）。如果我有一个函数 closest_pair(L)，其中 L 是 ℝ 中的整数坐标列表，我怎么能想出一个分而治之的迭代算法，它可以解决这个问题？
（不失一般性，我使用 Python）
将任何递归算法转换为迭代算法的廉价方法是采用递归函数，将其放入循环中，并使用您自己的堆栈。这消除了函数调用开销以及在堆栈上保存任何不需要的数据。但是，这通常不是 "best" 方法（"best" 取决于问题和上下文。）
他们用你的方式来描述你的问题，听起来这个想法是将列表分成子列表，在每个子列表中找到最接近的对，然后从这两个结果中取出最接近的对。要迭代地执行此操作，我认为比上面提到的通用方法更好的方法是从另一个方向开始：查看大小为 3 的列表（有三对要查看）并从那里开始。请注意，大小为 2 的列表是微不足道的。
最后，如果您的坐标是整数，则它们位于 Z（R 的一个更小的子集）中。
我正在尝试使用分而治之的方法创建算法但是使用迭代算法（即无递归）。
我对如何处理循环感到困惑。
我需要将我的问题分解成更小的子问题，直到找到一个基本案例。我认为这仍然是正确的，但我不确定如何（不使用递归）使用较小的子问题来解决更大的问题。
例如，我正在尝试提出一种算法来找到最近的一对点（在一维中 space - 虽然我打算自己将其推广到更高的维度）。如果我有一个函数 closest_pair(L)，其中 L 是 ℝ 中的整数坐标列表，我怎么能想出一个分而治之的迭代算法，它可以解决这个问题？
（不失一般性，我使用 Python）
将任何递归算法转换为迭代算法的廉价方法是采用递归函数，将其放入循环中，并使用您自己的堆栈。这消除了函数调用开销以及在堆栈上保存任何不需要的数据。但是，这通常不是 "best" 方法（"best" 取决于问题和上下文。）
他们用你的方式来描述你的问题，听起来这个想法是将列表分成子列表，在每个子列表中找到最接近的对，然后从这两个结果中取出最接近的对。要迭代地执行此操作，我认为比上面提到的通用方法更好的方法是从另一个方向开始：查看大小为 3 的列表（有三对要查看）并从那里开始。请注意，大小为 2 的列表是微不足道的。
最后，如果您的坐标是整数，则它们位于 Z（R 的一个更小的子集）中。