用多種解決方案遞歸回溯

Question

function BACKTRACKING-SEARCH(csp) returns a solution, or failure 
     return RECURSIVE- BACKTRACKING({ }, csp) 
function RECURSIVE-BACKTRACKING(assignment,csp) returns a solution, or failure 
     if assignment is complete then 
       return assignment 
     var ←SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp) 
     for each value in ORDER-DOMAIN-VALUES(var,assignment,csp) do 
       if value is consistent with assignment according to CONSTRAINTS[csp] then 
          add {var = value} to assignment 
          result ← RECURSIVE-BACKTRACKING(assignment, csp) 
          if result ̸= failure then 
              return result 
          remove {var = value} from assignment 
     return failure 

這是來自AIMA的回溯遞歸算法僞代碼。但是，我不明白它是否會返回所有可能的解決方案或只是找到第一個解決方案。如果是最後一個選項，請幫我修改它以返回可能的解決方案列表（或者至少更新一些全局列表）。

編輯：我用Java實現了這個算法。但是，有一個問題：

如果我沒有返回賦值，但將其保存在結果而不是遞歸停止條件失敗（即它不再存在）。我怎樣才能實現另一種停止條件？也許我應該回到真的到底？

這裏是我的代碼：

/** 
* The actual backtracking. Unfortunately, I don't have time to implement LCV or MCV, 
* therefore it will be just ordinary variable-by-variable search. 
* @param line 
* @param onePossibleSituation 
* @param result 
*/ 
public static boolean recursiveBacktrack(Line line, ArrayList<Integer> onePossibleSituation, ArrayList<ArrayList<Integer>> result){ 


if (onePossibleSituation.size() == line.getNumOfVars()){ 
    // instead of return(assignment) 
    ArrayList<Integer> situationCopy = new ArrayList<Integer>(); 
    situationCopy.addAll(onePossibleSituation); 
    result.add(situationCopy); 
    onePossibleSituation.clear(); 
} 

Block variableToAssign = null; 
// iterate through all variables and choose one unassigned 
for(int i = 0; i < line.getNumOfVars(); i++){ 
    if(!line.getCspMiniTaskVariables().get(i).isAssigned()){ 
     variableToAssign = line.getCspMiniTaskVariables().get(i); 
     break; 
    } 
} 

// for each domain value for given block 
for (int i = line.getCspMiniTaskDomains().get(variableToAssign.getID())[0]; 
     i <= line.getCspMiniTaskDomains().get(variableToAssign.getID())[0]; i++){ 

    if(!areThereConflicts(line, onePossibleSituation)){ 
     //complete the assignment 
     variableToAssign.setStartPositionTemporary(i); 
     variableToAssign.setAssigned(true); 
     onePossibleSituation.add(i); 
     //do backtracking 
     boolean isPossibleToPlaceIt = recursiveBacktrack(line,onePossibleSituation,result); 
     if(!isPossibleToPlaceIt){ 
      return(false); 
     } 
    } 

    // unassign 
    variableToAssign.setStartPositionTemporary(-1); 
    variableToAssign.setAssigned(false); 
    onePossibleSituation.remove(i); 

} 

// end of backtracking 
return(false); 

} 

Answer 1

此代碼檢查，如果溶液中發現的，如果是，返回的解決方案。否則，繼續回溯。這意味着，它返回找到的第一個解決方案。

if result ̸= failure then 
    return result 
remove {var = value} from assignment 

您可以修改它這樣：

if result ̸= failure then 
    PRINT result // do not return, just save the result 
remove {var = value} from assignment 

或者，更好，修改此部分：

if assignment is complete then 
    print assignment 
    return assignment // print it and return 

關於編輯的問題：

首先，在返回true第一個if，所以遞歸會知道它找到了一個解決方案。第二步，是有錯誤的，大概是：

if(!isPossibleToPlaceIt){ 
    return(false); 
} 

應該

if(isPossibleToPlaceIt){ 
    return(true); 
} 

因爲如果你回溯找到的東西，它會返回true，這意味着你不必檢查別的不再。

編輯＃2：如果您想繼續回溯找到ALL的解決方案，只是刪除了整個先前if節與return：

//if(isPossibleToPlaceIt){ 
// return(true); 
//} 

因此，我們將繼續以任何方式進行搜索。