有沒有辦法避免不必要的遞歸？

我發佈了這個問題over at CodeReview，但我意識到這不是一個Haskell問題，因爲它是一個算法問題。有沒有辦法避免不必要的遞歸？

Haskell代碼可以找到on my github repo但我認爲代碼並不像一般概念那麼重要。

基本上，該程序計算出Kalaha（瑞典變體）遊戲中最優的第一套動作。只考慮第一個「轉向」，所以我們假設你開始並且沒有計算從對手移動的點開始的任何事情。

Kalaha board http://www.graf-web.at/mwm/kalaha.jpg

板開始與空存儲和在每個盆中彈子的等量。

你開始輪到你，選擇一個非空的鍋在你身邊，從鍋中挑出所有的大理石，然後在盤子上放一塊大理石，在板上移動。如果您的最後一顆大理石在商店中落地，您可以再轉一圈。如果你在一個非空的非專用鍋中着陸，你可以拿起該鍋的所有內容並繼續。最後，如果你落在一個空鍋裏，轉身就傳給對手。

到目前爲止，我已經通過選擇所有可能的路徑，然後根據最終商店中的彈珠數量對它們進行排序來解決此問題。一條道路可能意味着從你的一個鍋子開始，做所有必要的拾取和移動，看看你是在商店還是在空罐子裏。如果你在商店登陸，你會繼續，現在有很多新的分支，因爲你身邊有非空的罐子。

問題在於，如果你從花盆中的五個彈珠開始，它已經有很多路徑。跳到六，ghci用完內存。

我無法弄清楚如何降低成本的原因是因爲我認爲每個路徑在計算過程中都是必需的。儘管我只需要生成數千（或數百萬）中最多三條路徑（最好的路徑），但剩下的路徑需要運行以查看它們是否比以前的路徑更好。
如果一個更長（通常更好），那麼這是好的，但成本高。如果它比任何以前的路徑都短，那麼程序仍然必須計算該路徑才能找到該路徑。

有沒有辦法解決這個問題，還是計算定義所需的所有路徑？

來源

2012-07-12 linduxed

爲了計算最好的單一動作而不嘗試通過對手的動作向前看，可以在這裏採用動態編程：每次計算從特定遊戲狀態的最佳移動時，將移動和結果狀態存儲在一張桌子。可能有許多國家（最多可以將30個分爲6個分箱），但我相信商店裏的彈珠數量可以忽略不計。 – 2012-07-12 15:26:46

我沒有證據，但我認爲應該有可能在一回閤中贏得比賽。文中沒有提到的一個規則是，如果你用完了可彈奏的彈珠，你將所有的彈珠都記錄在對手的坑中，所以目標是一回合用完一個完美的彈珠。如果以空坑結束的移動被忽略，問題將至少減少到指數複雜性而不是NP難度。 – dflemstr 2012-07-12 15:47:28

我會注意到，「計算所有路徑」並不一定意味着「內存不足」，如果你可以垃圾收集你已經考慮過的路徑。 – 2012-07-12 16:25:43

剛剛嘗試他們全力以赴爲了，通過6記錄您的運動序列編號1的序列（表示你選擇從大理石鍋），每次從一開始重放的整個序列。保持並更新三位獲勝者，再加上最後一個動作序列，這樣你就可以知道下一步要做什麼。如果沒有下一個合法的舉動，回去一個缺口。

它可能會過於緩慢，但會使用很少的內存。您不會儲存結果位置，只能從中挑選出的花盆數量，並且每次從起始位置重新播放序列，改變最後一步移動（而不是2，然後嘗試3,4等;如果沒有更多合法移動，回溯一個級別）。或者，也許商店位置只是爲了嘗試最後的一系列動作，以便於回溯。

這是當時速度貿易的典型空間。

來源

2012-07-12 20:15:20

我現在意識到我的問題可能應該分解爲空間效率和計算效率。我想這是空間問題的一個很好的解決方案。 – linduxed 2012-07-13 12:40:35

@linduxed，但也要考慮到這一點：採用這種方法，由於幾乎沒有任何東西，因此它更容易並行化。 – 2012-07-13 12:56:55

可能，但並行化是遠離我的知識水平，所以我不能實現它。 – linduxed 2012-07-13 13:04:35

你可以嘗試使用地圖的這種並行版本parallellizing：

parMap :: (a -> b) -> [a] -> Eval [b] 
parMap f xs = map f xs `using` parList rseq

然後你會引發一場新的線程在您的分支中的每個最佳的選擇。

如果你使用parMap pathFunction kalahaPots作爲你的遞歸，它會引發很多線程，但它可能會更快，你可以將它塊化，但我並不是一個平行的haskeller。

來源

2012-07-13 14:42:48

有沒有辦法避免不必要的遞歸？

回答

相關問題