如何實現種族模擬問題的解決方案

Question

有在接受採訪時提出了一個問題：

在公式-1的挑戰，有n個團隊編號爲1到n。每個隊都有一輛車和一名司機。汽車的規格如下：

• 最高時速：（150 + 10 * I）公里每小時
• 加速：（2 * I）每秒平方米。
• 處理因子（hf）= 0.8
• Nitro：將速度提高到雙倍或最高速度，以較小者爲準。只能使用一次。

這裏是我的團隊編號。 賽車參加比賽。第（i + 1）輛汽車的起點在第i輛汽車後面200 * i米。

所有這些都開始在同一時間，並試圖達到其最高速度。每2秒進行一次位置重新評估（所以即使車輛已經越過終點線，2秒鐘後你就會知道了）。在評估過程中，每位駕駛員檢查他的汽車10米內是否有汽車，他的速度降低到：hf *（當時的速度）。另外，如果司機注意到他是比賽中的最後一名，他使用「硝基」。

以團隊數量和軌道長度作爲輸入，計算最終速度和相應的完成時間。

我不明白如何解決這類問題。對於每個實例，我應該檢查每對驅動程序的所有C(n,2)組合並計算結果？但是我怎樣才能弄清楚我應該在什麼情況下進行計算？

Answer 1

如果您檢查Conway's Game of Life，您會發現與種族問題有許多共同之處。

這裏是類比：

• 的初始狀態（該系統的種子）：
  • 生命遊戲：網格上的初始圖案。具有以下參數的每一個細胞：
    • x和y座標
    • 該小區是否是活的或死的
  • 種族問題：N汽車每一個具有預定的參數和軌道L的長度。每輛汽車有以下參數：
    • 最高速度
    • 加速
    • 處理因素正軌
    • 位置
    • 當前速度
• 的規則是在離散時刻施加被稱爲蜱。
  • 生命之遊：規則同時應用於上一代產生下一代的每個細胞。每一代都是前一代的純粹功能。
  • 種族問題：規則同時應用於前一個狀態的每輛車，產生下一個狀態。這每2秒發生一次。與「生命遊戲」中的每一步都是前一個遊戲的純函數，這意味着它僅取決於來自之前狀態的汽車參數。

以往不同的是，生活的遊戲永遠不會結束，而種族問題時，每一輛汽車的當前位置是大於或等於軌道長度l應終止（雖然最後一條語句是值得商榷的：由於對於處理因素來說，在某些情況下，有些車輛可能永遠無法到達終點線）。

關鍵的一點是，計算在離散時刻這回答你的問題做：

但我怎麼能在什麼情況下找出我應該做的計算？

您可以參考Algorithms部分的想法來解決此問題。你需要有2個汽車陣列：一個代表當前狀態，另一個代表下一個步驟。在每一次迭代中，您都要根據賦值規則重新計算每輛車的當前位置和速度，並檢查循環是否應終止。在下一次迭代之前，交換數組角色，以便在最後一次迭代中的後繼數組成爲下一次迭代中的當前數組。

高電平僞代碼可能看起來像這樣：

n = ..; // initial number of cars 
l = ..; // track length 
Car[] currentState = initializeState(n, l); 
Car[] nextState = clone(currentState); 
for (int iteration = 0; iteration < MAX_ITERATIONS; iteration++) { 
    calculateNextState(currentState, nextState, iteration); 
    swap(currentState, nextState); 
    if (shouldTerminate(currentState, l) { 
     break; 
    } 
} 

printResultOrClaimNotTerminated(currentState); 

的規則在calculateNextState（..）函數施加。在最幼稚的做法，你檢查每對汽車的，讓你

O (C(n, 2)) = O (n * (n - 1)/2) = O (n^2)

複雜每次迭代。但是，您可以在這裏考慮可能的優化。例如，您可以首先按當前位置（O (n * log(n))）對汽車進行排序，然後遍歷排序的陣列，僅檢查相鄰的汽車（O (2 * n)）。你可以這樣做，因爲如果10米的條件不滿足相鄰車輛，它不會滿足非相鄰車輛。這會給你由此產生的複雜性：

O (n * log(n)) 

哪個更好。排序好的汽車陣列自然會爲您提供最後一個位置的汽車，您需要應用硝基增壓規則。可能還有其他優化。這回答你的問題：

對於每個實例我應該檢查每對驅動程序的所有C（n，2）組合，並計算結果？

Answer 2

租車對象和遊戲對象

我假設你已經創建了汽車必需的對象，一個遊戲對象中封裝。

思路，加快每個更新步驟不做所有C（N，2）檢查

可以加快更新位置和參數的步驟，通過不必檢查所有在C（n，2）的組合。您可以使用一種簡單的啓發式方法，即我們不需要檢查距離較遠的汽車之間的交互。例如，賽道第一季度的一輛汽車不會與賽道第三季度的汽車相互作用。我想根據你的問題的參數，你想把賽道分成10米長的部分。維護每個部分的列表並跟蹤每個部分中的所有汽車。更新位置後，僅檢查連續車輛之間的交通情況。

同樣，記錄每個更新步驟中哪輛汽車處於最後位置，並相應地切換硝基加速器。時間步長

的

選擇在你的問題的時間步長似乎被固定爲2秒。然而，在您編寫遊戲時的一般設置中，此選項至關重要。你可以玩幾個不同的數字（例如10,50,100,500毫秒）。

如果您選擇timeStep爲較高數字，（例如）汽車可能會通過另一輛汽車並避免檢測到碰撞。 另一方面，如果您選擇timeStep太小，並且如果操作的時間大於timeStep，則遊戲運行速度會比實時慢。