PACMAN：吃所有點的短路徑

我想找到一個PACMAN問題的解決方案，找到一個在大型迷宮中吃掉所有點的短路徑（不是最短的，但是很好的）。我見過很多人在談論TSP，Dijsktra，BFS，A *。我不認爲這是一個TSP，因爲我不必回到我開始的地方，如果我願意，我可以重複節點。而且我不認爲Dijsktra，BFS和A *會有幫助，因爲我沒有尋找最短路徑，即使是這樣，它也不會在合理的時間內給出答案。PACMAN：吃所有點的短路徑

任何人都可以給我這個提示嗎？這是什麼問題？這是一種TSP嗎？什麼樣的算法以有效的方式解決這個問題？我會很感激任何有關實施的提示。

來源

2012-10-13 Bruno Calza

在這裏看到：http://stackoverflow.com/questions/7437489。做相同的課程？ – Junuxx

相同的過程，不同的問題 –

我認爲你正在嘗試做比賽，在30秒內在大型迷宮中找到最短路徑？

我實際上是去年爲了好玩而去的（我的大學班級沒有參加比賽）。經過數週的研究，我能夠在30秒內完成對迷宮的精確解決方案。

我使用的啓發式實際上是一種確切的啓發式。我使用基於圖分解和動態規劃的更高效的算法編寫了一堆代碼來查找最小路徑長度，然後將結果作爲「啓發式」值反饋給A *。

要實現的關鍵是，雖然圖形非常大（273個節點），但雕刻寬度較低（5），這意味着它可以使用固定參數易處理算法有效地解決。

希望這足以讓您走上正確的軌道。

更新：I wrote a blog post explaining the solution

來源

2012-10-13 22:29:59 Antimony

PACMAN：吃所有點的短路徑

回答

相關問題