使用什麼算法來計算構建建築物的最快訂單？

Question

對於我正在玩的遊戲，我想知道建造多個建築物的最快順序。有問題的遊戲是OGame，如果你對它很熟悉，那麼這是一個加分，但很明顯我會解釋遊戲的基本知識：

• 玩家有許多可用的不同資源。
• 玩家可以一次建造最多一棟建築物。
• 建築物具有不同的等級，例如建築物A等級1，建築物A等級2等等。
• 建造建築物的資源成本在每個等級上增加。
• 建築物也需要花費時間來建造，這也會增加每個級別。
• 一些建築物產生不同的資源，這也會增加每個級別。
• 一些建築物改變了計算方式，使得建築物的建造速度更快。

我明確選擇不顯示方程，因爲它們不是直接的，不應該需要建議算法。

我選擇了與以下操作來模擬這種：

• StartUpgradeBuildingAction：此操作將啓動減去可用資源成本的升級過程。
• FinishUpgradeBuildingAction：此操作通過及時完成升級過程。這也產生資源。
• WaitAction：此操作將時間轉換X秒，同時根據資源生產生成資源。

應當注意的是，狀態空間是無限的，並且可以通過這一事實有到最終構型（其中所有請求的建築物已建成）的多條路徑來表徵，每個可能具有不同的時間花費並最終得到不同數量的資源。現在我最感興趣的是最快的路徑（順序），如果有多個相等的路徑，那麼應該優先考慮花費最少的路徑。

我已經嘗試以下方法：

• 廣度優先搜索
• 深度優先搜索
• 迭代深化深度優先搜索
• 迭代深化A *搜索
• 一*搜索

不幸的是，這些算法中的任何一個都會花費太長時間，或者使用太多的內存。

由於谷歌搜索也沒有給我任何進一步導致，我在這裏提出以下問題：

• 是否有符合我的問題已經存在的模式？例如，我認爲Business Information Systems已經遇到了這種類型的問題。
• 是否存在可提供最佳解決方案的算法？如果是這樣，哪一個？
• 有沒有給出一個解決方案，是接近最好的解決方案的算法？如果是這樣，哪一個？

任何幫助表示讚賞。

Answer 1

沒有一個算法，讓你的問題的最佳解決方案。你嘗試的方法都是合理的。然而，嘗試A *搜索並不意味着很多，因爲A *搜索取決於評估某個特定配置的啓發式算法（即，它將值分配給所建立的建築物的可用時間，數量和選擇的組合的可用值資源等）。藉助良好的啓發式方法，A *搜索可能會使您迅速獲得非常好的解決方案。尋找這種啓發式方法需要對參數有很好的瞭解（建築物的成本，升級的好處等）

然而，我的感覺是，你的問題的結構使得一系列的構建決定可以明顯超過另一系列幾個步驟後的決定。假設你按照這個順序建造建築物A，B和C.只要所需資源可用，即可構建每一個。然後你嘗試C，A，B的順序。你可能會發現一個選擇支配另一個選擇，因爲你擁有相同的建築物，但是在另一個選擇中，你擁有比另一個更多的資源。如果你有很多不同的資源，這當然不太可能。你可能擁有更多的資源X但更少的Y，這使得難以比較的情況。如果是可能的，好東西是你不需要啓發，但你清楚地看到你應該遵循的路徑和切斷。

無論如何，我會探索需要多少步驟，直到找到可以根據這樣的考慮排除的路徑。如果您發現它們很快，那麼儘快遵循廣度優先策略和修剪分支是有道理的。深度優先搜索承擔着花費大量時間探索劣質路徑的風險。