迭代划分和征服算法

我想创建一个算法，使用分而治之的方法但使用迭代算法（即没有递归）。迭代划分和征服算法

我很困惑如何处理循环。

我需要把我的问题分解成更小的子问题，直到我遇到基本情况。我认为这仍然是正确的，但是我不确定我怎么能（没有递归）使用较小的子问题来解决更大的问题。例如，我试图想出一个算法，它可以找到最接近的一对点（在一维空间中 - 尽管我打算将它自己推广到更高维度）。如果我有一个函数nearest_pair（L），其中L是整数坐标列表,，我怎么能想出一个可以解决这个问题的分而治之的ITERATIVE算法？

（不失一般性，我使用Python的损失）

来源

2016-11-23 TimelordViktorious

是否有一个特定的原因，你为什么不会（不能？）使用递归？ – Gormador

我不得不为类中给定的赋值设计一个迭代算法。我确实知道递归解决方案（使用D＆C），我相信我可以将它翻译为迭代代码，并利用D＆C方法处于O（nlogn）时间而不是O（n^2）的事实。 – TimelordViktorious

这就是我所害怕的。特别是在班级任务的情况下，即使我明白你的问题，但在显示你已经尝试过的代码之前，你也不会得到帮助。问题更多的是关于一般编程而不是语言。唉，你将不得不在一些代码，这将影响具体的答案... 虽然它似乎有人回复！你似乎很幸运！ – Gormador

便宜的方式将任何递归算法为迭代算法是采取递归函数，把它放在一个循环，并使用自己的堆栈。这消除了函数调用的开销，并保存了堆栈上不需要的数据。然而，这通常不是“最好”的方法（“最好”取决于问题和背景。）

他们用这种方式表达了你的问题，这听起来像是想把这个列表分解成子列表，找到每个中最接近的一对，然后从这两个结果中选出最接近的一对。为了迭代地做到这一点，我认为比上面提到的通用方式更好的方法是反过来开始：查看大小为3的列表（有三对要查看）并从那里开始工作。请注意，大小为2的列表是微不足道的。最后，如果你的坐标是整数，它们是Z（R的一个小得多的子集）。

来源

2016-11-23 17:32:07 Andrew

是的，你是对的。我的意思是Z. :-)。我曾经想过Stack的想法，但是因为我试图分析这个算法并证明它是正确的，所以我想避免这个想法。如果我明白你的意思，你是建议采用自下而上的方法吗？ – TimelordViktorious

@TimelordViktorious是;从算法的角度来看，你也可以进行不同的排序，但是我发现迭代版本更有意义，自下而上（并且由于你花更多时间在内存中彼此靠近的元素上工作，因此会有更好的缓存性能） – Andrew

要做到这一点，我应该通过列表L进行线性扫描，并一次查看3个元素的分区（或2个），直到我到达列表的末尾。这是否正确，我正在采取这种做法？ – TimelordViktorious

迭代划分和征服算法

回答

相关问题