如何在回溯中找到所有可能的解決方案

我試圖實施一種回溯算法（它應該貫穿給定數量的人並檢查所有可能的對，每對都有一定的分數，目標是找到許多次出現「最大」分數;所以我需要檢查所有可能的解決方案）。如何在回溯中找到所有可能的解決方案

問題是我無法理解如何使我的函數實際上'回溯'...當它找到解決方案時，它會一直回到根。我該如何回到一個我可以嘗試不同的道路的地步，並讓它走上這條道路，而不是再做一次呢？

這是我的代碼，但我知道我的想法可能是錯誤的......這只是我試圖用很多方式來思考它，而我完全迷失在這裏。感謝您的幫助！

void allPairs (int x, int pref[], bool teamed[], int* max, int score, int numWorkers) { 
    for (int i=1; i < numWorkers; i++) { 
     int count = 0; 
     pairTwo(x, i, pref, teamed, max, score, numWorkers, &count); 
    } 
} 

int pairTwo (int x, int y, int pref[], bool teamed[], int* max, int score, int numWorkers, int* howMany) { 
     if (x >= numWorkers) { 
      arrToZero(teamed, numWorkers); 
      return score; 
     } 
     else if (x==y) { 
      if(y < numWorkers-1) { 
       y = findUnteamed(teamed, y+1, numWorkers); 
      } 
      else { 
       arrToZero(teamed, numWorkers); 
       return score; 
      } 
     } 

     int pairScore = sumPair(pref, x, y, teamed, numWorkers); 
     x = findUnteamed(teamed, x, numWorkers); 
     y = findUnteamed(teamed, 0, numWorkers); 
     int temp = pairTwo(x, y, pref, teamed, max, score + pairScore, numWorkers, howMany); 
     teamed[x] = 0; // here I tried to "erase" the last move but it's useless 
     teamed[y] = 0; 
     if (temp >= *max) { 
      max = &temp; 
      *howMany++; 
      printf("There are %d optimal pairings:, with a total score of: %d\n", *howMany, *max); 
      return *max; 
     } 
     else { 
     return -1; 
     } 
}

來源

2016-01-21 Anna

您對'pairTwo'的遞歸調用必須在循環中檢查所有可能性，'x'和'y'必須迭代所有* unteamed *，而不僅僅是第一次找到。 –

如果您不遵守它遵循的確切算法，回溯會令人困惑。回溯算法中非官方的方法名稱被廣泛接受，並且幫助調試代碼變得更加容易。標準遞歸回溯算法由solve（），getSuccessors（），isGoal（）和isValid（）組成。使用int數組正在被manuipulated要解決的一個例子，解決（）函數是這樣的：

int[] solve(int[] list) { 
    if (isGoal(list)) { 
     return list; 
    } 
    int[][] successors = getSuccessors(list) 
    for (int[] successor : successors) { 
     if (isValid(successor)) { 
      if (sizeof(solve(successor)) != 0) { 
       return successor; 
      } 
     } 
    } 
    return []; 
}

凡getSuccessors()返回已修改了當前陣列的深層副本列表探索新的解決方案，isGoal()檢查是否已找到解決方案，並且isValid()檢查是否有可能找到沿該當前路徑繼續前進的目標。這三個功能是特定於您正在嘗試解決的問題。

或者，solve（）的迭代版本存在於初始狀態放入空棧的位置，儘管您需要首先構建一個棧。通過迭代回溯來檢查維基百科頁面，瞭解該解決方法的工作原理。

來源

2016-01-21 21:09:22 James

如何在回溯中找到所有可能的解決方案

回答

相關問題