算法概率遊戲的問題

Question

我開始開發爲契機遊戲的問題如下規則的算法：

• 在遊戲開始時，玩家起始如果s開始（開始）。

• 他從擲骰子開始並提前指定空格數。

• 骰子的可能值從1到6

• 然後玩家執行於當前的情況下（事先指定的動作，回去，relance骰子（如果當前的情況是R：Relance ））。

• 每個動作花費1回合。

• 當玩家達到完成情況E時結束遊戲（結束）。玩家必須完全落在終點線上，並且不能超過終點線。

• 開始和結束情況S和E不一定在托盤的開始和結束處。

• 輪到董事會失敗了。

下面是一個例子：

| 4 | S | -2 | 1 | R | 4 | 3 | 4 | 3 | -5 | 2 | -4 | E |

玩家在S的情況下啓動。贏得最快的方法是：

• 滾動骰子，並使3，去R廣場（轉1）。

• 重新擲骰子，並使6，到達方2（轉2）。

• 玩家有義務前進2例並抵達情況E（轉3）。

預期結果是3，因爲它至少需要3次發射完成遊戲。

我的解決方案是基於一個算法，從最終案例開始，並檢查什麼情況下驅動到最後一個。然後，我會檢查哪些病例可以達到我已經找到的病例。這樣，我就不必檢查那些不會導致最終情況的案例。

事情是，我更願意更重視代碼的質量和效率，因爲我認爲我發現的算法是不夠的。

有什麼建議嗎？

Answer 1

你可以看到你的董事會是一個有向圖。每個案例都是一個節點，編號案例的邊緣將它們連接到它們指向的案例，而S和R案例有六條邊將它們連接到接下來的六個案例。邊緣具有相同的重量。

在這種情況下，您的問題變成沿着最短路徑找到起點和終點之間的距離，這是一個問題，其中has been widely studied in many different variants。

作爲參考，你可以看看一個標準的breadth-first search，你的算法應該與這個相當（你可以儘快找到你的目的地然後返回，完整的算法計算從一個節點到所有其他節點的距離） 。

我不認爲決定是否從最終案件或從開始案件出來是很重要的，在這兩種情況下，您都會有一些董事會結構會更慢或更快分析，但平均複雜度應該是一樣的。 （正如你所說，從頭開始你避免檢查不會導致它的情況，但是從Start開始，你將避免檢查無法從它到達的情況）