錯誤在我回溯代碼 - 過橋

我努力學習回溯，併爲此我挑的TopCoder的問題之一 - 其所謂BridgeCrossing。晚上我們有1-6個人試圖過橋，他們之間有一個手電筒。最多2人可以過橋一次，當他們正在做的是，其中至少有一個必須有一個手電筒，否則就什麼也看不見......錯誤在我回溯代碼 - 過橋

答案是給定函數vector <int> times其中times[i-1]表示需要第i人過橋（當2人過橋他們的時間是一個來自較慢人未來）的時間。另外，當我們在橋的另一側有手電筒時，還有一些人需要穿過橋 - 一個人必須帶着手電筒返回，以便引導他們通過。

這裏是我的溶液（vector <int>所有出現被做成VI）：

int backtrack(VI times){ 
     if (times.empty()) return 0; 
     if (times.size() == 1) return times[0]; 
     if (times.size() == 2) return max(times[0], times[1]); 
     VI results; 
     for (int i = 0; i < times.size(); i++){ 
      for (int j = 0; j < i; j++){ 
       VI people_left1; 
       for (int k = 0; k < times.size(); k++){ 
        if (k != i && k != j){ 
         people_left1.push_back(times[k]); 
        } 
       } 
       people_left1.push_back(min(times[i], times[j])); 
       results.push_back(backtrack(people_left1)+ 
       max(times[i], times[j]) + min(times[i], times[j])); 
      } 
      for (int j= i + 1; j < times.size(); j++){ 
       VI people_left; 
       for (int k = 0; k < times.size(); k++){ 
        if (k != i && k != j){ 
         people_left.push_back(times[k]); 
        } 
       } 
       people_left.push_back(min(times[i], times[j])); 
       results.push_back(backtrack(people_left)+ 
       max(times[i], times[j]) + min(times[i], times[j])); 
      } 
     } 
     int res = INT_MAX; 
     for (int i = 0; i < results.size(); i++){ 
      if (results[i] < res){ 
       res = results[i]; 
      } 
     } 
     return res; 
    }

理論上它應該很好地工作 - 我撿所有可能對指數I，J，引導一個人（具有較大時間），通過一個人返回，並緩解留下的人。不幸的是它不起作用 - 對於輸入{1,2,5,10}它應該返回17，但我的功能輸出19.

我一直在盯着這段代碼很長一段時間了，我仍然看不到任何錯誤。哪裏可以隱藏？此外，什麼是調試這種遞歸函數的技術，因爲我現在一直有這樣的問題。

來源

2015-01-16 qiubit

步驟通過在調試器的代碼，一邊看所涉及的變量的值。當某些東西看起來不合適時，它可能是。 –

與調試器調試回溯代碼的問題是遞歸的深度是非常深的，通常我無法「想象」現在是怎麼回事，應該怎麼現在要去... – qiubit

您可以通過添加一些垂直線進行可視化作爲穿過橋樑的人的「深度」和水平箭頭圖。 –

問題是，你不認爲一個已經留在另一邊的人可以在未來回到手電筒。在這個例子中，人員2在一段時間後返回。基本上並不總是一個來自i，j的人會用手電筒回來。

來源

2015-01-16 19:29:08

究竟是什麼導致我的代碼出現問題。謝謝。 – qiubit

歡迎您:) –

不是一個真正的答案，但你的代碼可能是由這樣更具可讀性：

for (int j = 0; j < times.size(); j++){ 
    if (j != i) { 
    .. all that code inside both loops    
    } 
}

也許這將使它更容易找到您的問題。

可以調試遞歸代碼，有時，通過打印按遞歸的水平縮進信息。要做到這一點，你必須添加一個傳遞到每個級別的變量。當你調出一個關卡時增加它。

method(int level, ...) { 
    if (recursing needed) { 
     print(spaces(level * 3) + "recursing"); 
     method(level + 1); 
    } 
}

來源

2015-01-16 19:27:06

錯誤在我回溯代碼 - 過橋

回答

相關問題