遞歸迭代 - 或優化？

我有一個算法，它搜索圖中兩個節點之間的所有可能的路徑，但我選擇的路徑沒有重複節點，並且具有指定的路徑長度。
它是在ActionScript3中，我需要將我的算法更改爲迭代或優化它（如果可能的話）。
我不知道如何做到這一點，我不知道如果改變迭代將帶來一些更好的執行時間的功能。也許它不能被優化。我不確定。遞歸迭代 - 或優化？

這裏是我的功能： http://pastebin.com/nMN2kkpu

如果有人能提供有關如何解決一些小技巧，那將是巨大的。

來源

2012-06-13 Dominik T.

你可以用非常一般的術語解釋你的算法是什麼意思。是否應該找到任何給定節點之間的最短路徑，還是應該找到所有節點之間的所有路徑？如果它是前者，Djisktra的算法會訣竅，如果是後者，我的猜測是不管這是否是一個相當昂貴的CPU操作。我意識到你確實在你的問題中提出了一些解釋，但這並不完全清楚。 – shaunhusain

@shaunhusain算法找出任何給定節點之間的所有路徑，但是我的修改只返回我給定長度的路徑，並且在我的「生成」路徑中每個頂點路徑只能使用一次。 –

首先，您可以通過啓動頂點來對邊進行排序。然後，遍歷一個頂點'鄰居'將與這個頂點的鄰居數量成正比（雖然現在需要O(M)，其中M是整個圖的邊數）。

如果你放鬆不重複頂點的條件，我敢肯定，問題可以在更好的時間解決。

但是，如果您需要這樣做，恐怕沒有簡單的更改可以讓您的代碼更快。不過，我無法保證。

而且，如果我是正確的，如果邊緣已被使用的代碼片段測試，而不是如果頂點使用。我注意到的另一件事是，一旦你找到了這樣的路徑，你就不會停止遞歸。由於在大多數*圖中，這樣的路徑將存在合理的值length，我想說如果你只需要一個這樣的路徑，你可能會在找到一條這樣的路徑後浪費大量的CPU時間。

*大多數 - 被讀取'也許最（IMO）'。

來源

2012-06-13 23:31:53

遞歸迭代 - 或優化？

回答

相關問題