迭代劃分和征服算法

我想創建一個算法，使用分而治之的方法但使用迭代算法（即沒有遞歸）。迭代劃分和征服算法

我很困惑如何處理循環。

我需要把我的問題分解成更小的子問題，直到我遇到基本情況。我認爲這仍然是正確的，但是我不確定我怎麼能（沒有遞歸）使用較小的子問題來解決更大的問題。例如，我試圖想出一個算法，它可以找到最接近的一對點（在一維空間中 - 儘管我打算將它自己推廣到更高維度）。如果我有一個函數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

迭代劃分和征服算法

回答

相關問題