試圖找出使用什麼算法

你有一個輸入n場比賽。每個遊戲都有一個聲望（可以是負面的）和必備遊戲（這些遊戲必須在玩遊戲之前播放）。試圖找出使用什麼算法

你想通過玩一套有效的遊戲來找到你可以獲得的最大聲望。

我的一個想法是使用加權有向圖，但是您仍然需要嘗試圖中每對節點來找到最佳解決方案。

任何想法？

來源

2011-05-01 Reflux

隨着所給問題的描述，聽起來好像玩所有遊戲始終是最佳解決方案。 – blubb 2011-05-01 21:45:48

@Simon：不，一些遊戲可能會產生負面的fames（即：費用）。 – hugomg 2011-05-01 22:13:28

你有沒有關於'n'有多大的信息？ – hugomg 2011-05-01 22:33:50

你有最大數量的遊戲可以玩嗎？然後，這聽起來像揹包問題的一個變種http://en.wikipedia.org/wiki/Knapsack_problem（找到問題的一些方法，即使問題是NP完全的，因此原則上不能有效解決）。

如果您可以隨心所欲地玩很多遊戲，那麼從計算的角度來看它仍然很難。對於每個必備遊戲，您可以通過添加遊戲的聲望來計算獲得的點數。當然，這些會隨着你玩的每個先決條件而改變，因爲後來的先決條件可能會使先前的先決條件已啓用的遊戲，從而減少它們提供的名望上的增益。我想你仍然堅持嘗試所有2^p組合對於p前提遊戲。

來源

2011-05-01 21:38:48 Nicolas78

也許A* algorithm會幫助你，也就是說，你會爲圖表中的每條路線做一個有根據的猜測（對於這條路線的最小名氣），請遵循最有前途的猜測，如果你看到它低於猜測還沒有采取的路線，按照新的路線，並停在這裏。

來源

2011-05-01 21:40:49 Thomas

A *不支持負邊權重。 – shams 2011-05-01 23:13:59

下面的方法適用於具有非負邊的圖：由於遊戲之間存在依賴關係，因此該圖是非循環的。您可以否定圖中的所有邊並在P時間中找到最短路徑。這然後給出了原始圖中最長的路徑。

編輯：

因爲，圖表是非循環的最短路徑，將負邊緣也行。請參閱DAG中的最短/最長路徑http://algs4.cs.princeton.edu/44sp/

來源

2011-05-01 21:40:49 shams

我正在考慮使用貝爾曼福特，它與消極的邊緣。 – Reflux 2011-05-01 21:48:53

@Reflux，是的，這將工作。你需要重複每場比賽作爲一個來源找到最長的路徑。 – shams 2011-05-01 21:51:14

查找路徑不能解決問題。考慮4場比賽，A，B，C，D，B，C和D依賴A. A有-2個名望，而B，C，D有名望+1。要找到的最大路徑總有名望-1（所以不太好），但最佳解決方案是每場比賽。 – hugomg 2011-05-01 22:43:37

試圖找出使用什麼算法

回答

相關問題