1 
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で実装しました。ただし、1つの問題があります。

割り当てを返さずに結果として保存すると、再帰停止条件が失敗します（つまり、割り当てはもう存在しません）。別の停止条件を実装するにはどうすればよいですか？たぶん私は最終的にtrueを返す必要がありますか？

これが私のコードです：

/**
 * 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);

}
4

1 に答える 1

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ます。これにより、再帰は解決策を見つけたことを認識します。2番目のステップ、おそらく間違いがあります：

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

する必要があります

if(isPossibleToPlaceIt){
    return(true);
}

バックトラックで何かが見つかった場合はtrue、が返されるため、他に何もチェックする必要がなくなります。

編集＃2 ：すべての解決策を見つけるためにバックトラックを続けたい場合は、前のifセクション全体をreturn：で削除してください。

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

ですから、なんらかの形で検索を続けていきます。

于 2013-03-24T19:39:49.513 に答える