比賽計劃算法

我相信這是不可惜的，你不明白的「解決方案」，因爲它沒有提供的基本細節解釋，並且......它也是不正確的。

首先，從開始和結束時開始搜索最佳解決方案，還是從結尾開始搜索並向後開始搜索，應該沒有實際意義。當然，有一點點不同，因爲如果約翰能夠在比賽結束時間之前完成比賽任務，那麼他可能仍然會抓住下一場比賽。因此，如果方向至關重要，那麼他應該從開始時間開始計劃，並且應該繼續前進，如同結束時他可能有機會參加其他比賽一樣。讓我們不要過分深入細節，因爲這個小小的差異對於這個小任務並不重要，它只對一個嚴肅的項目很重要。

我一直對解決方案非常苛刻，因爲我稱之爲不正確。我會重複一遍：這是不正確的。如果你再看一下僞代碼，忘記了向後的方向（這可能對其他問題有用，但不在這裏），你會注意到當你迭代一次時，選擇或不選擇比賽。想象一下，在一天中有一場比賽發生的情況下，約翰可以在此期間參加其他四場比賽，所以他應該選擇參加長時間比賽還是參加其他四場比賽。我們假設約翰很有可能贏得長時間的比賽，並且以較低的概率贏得其他四場比賽。在所給出的迭代中，我們只能看到長期比賽還是其他四場比賽在爭奪一兩個較短的比賽後是否是更好的選擇。

回溯解決方案，通過生成所有可能的場景並找到最佳選擇將肯定能解決問題，但它將具有指數級的複雜性。

「然後可以向後計算A [s]的值。」是的，它可以反向計算。但是，作者是否給出了爲什麼應該倒退計算的原因，爲什麼倒計算這是更好的選擇？是的，在動態規劃中，這是一種常見的方法來反向解決問題，並且在很多情況下是有原因的，但是在這裏我並沒有看到爲什麼我們應該向後計算它的有效理由，因爲問題幾乎是對稱的時間，「前進」和「後退」之間的唯一區別就是時間的開始和時間的結束，這只是兩個常數。

讓我們來詳細說明前面給出的例子。讓我們假設有五個競賽：

S = 1，T = 24，P = 0.99
S = 2，T = 3，P = 0.66
S = 4，T = 5， p值= 0.66
S = 6，T = 7，p = 0.66
S = 8，T = 9，p = 0.66

正如所看到的，每次在，競賽1是更比比賽2,3,4和5中的每一場都有吸引力。但他們在一起比競爭更具吸引力st 1.

所以，具有指數複雜度的算法要好得多。它的速度很慢，但嘿，與給出的「解決方案」相反，這是正確的。如果你想要一個解決方案，那麼你可以停止閱讀這裏。如果您想聽到更好的解決方案，請繼續閱讀。

假設我們定義了「排除」的邏輯運算符，它是對稱的。如果比賽C1不包括比賽C2，則C2也不包括C1。

讓我們進一步假設，當您閱讀輸入時，您還構建了一個包含排除集羣的數據結構：每個集羣都是最大的一組比賽，其中每個C1和C2直接或間接地排除彼此。您可以通過劃分等級找到每個羣集的最佳解決方案，並且當您知道所有羣集的解決方案時，完成該任務所需的唯一任務就是合併子結果以獲得全部結果。

來源

2014-09-21 00:09:36

「這是不正確的」對我來說，看起來很好，因爲fencepost錯誤。「你會注意到，當你迭代到某個時間時，選擇或不選擇比賽」不，完全沒有。不過，你說得對，方向並不重要。 – 2014-09-21 00:42:15

你用我的測試用例試過了嗎？ – 2014-09-21 02:07:15

是的，它工作正常，因爲它不會做你說的那樣。 – 2014-09-21 03:07:41

比賽計劃算法

回答

相關問題