船上運動的優化

假設你有一個n×n的遊戲板，並且你有一個角色可以像國際象棋棋盤上的騎士一樣移動，除非他不能向上或向左移動。而他所移動的每個街區都有一個可以積累到他的點的價值。玩家正在嘗試最大化點並達到T船上運動的優化

我想出了一個解決方案，但我想知道它會在哪裏失敗和運行時間。

我的想法是爲每個可能的目的地創建一個有向加權圖（點爲權重），然後在圖上運行Dijkstra算法，但我們不是最短路徑，而是嘗試尋找最長的路徑。

我猜運行時會O（有些事+ | E | + | V |登錄|| V |）

林不知道是什麼東西。

2014-02-16 RandomGuy

在我看來，圖是非循環的，在這種情況下，有快速算法：[ref1]（http://cs.stackexchange.com/questions/11295/finding-shortest-and-longest-paths-between -two-vertices-in-a-dag）[ref2]（http://stackoverflow.com/questions/2525316/longest-acyclic-path-in-a-directed-unweightedgraph），[ref3]（https： //en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths） – Nabla

該算法不起作用可以有循環的情況下 – RandomGuy

嗯，我認爲你的限制向下和正確的運動會使這個非循環。 – Nabla

Dijkstra不適合尋找最大路徑。爲了找到最大路徑，您應該將每個邊權重乘以-1，衆所周知，dijkstra在負權重邊的圖上無法正確運行。相反，您將需要使用Bellman-Ford algorithm。正如維基百科文章所述，複雜性將會是O(| V | · | E |)。

來源

2014-02-18 09:09:50

您的答案有效，但我認爲Dijkstra也會工作，因爲永遠不會有負面的邊緣。我從來沒有想過乘以-1並找到最短的路徑，它的聰明。 – RandomGuy

@RandomGuy如果您將所有邊緣乘以'-1'**所有**邊緣將爲負 –

船上運動的優化

回答

相關問題