Other application examples of backtracking method

In the previous section, we focused on the problem of backtracking prime rings . This section will briefly introduce several other application examples of backtracking .

Catalog

bandwidth Bandwidth, Uva 140

Difficult string Krypton Factor, Uva 129

bandwidth Bandwidth, Uva 140

This topic is about giving a n A graph of nodes G And an arrangement of nodes , node i The bandwidth of the b(i) by i And the farthest distance in the arrangement of adjacent nodes in the original figure , And all nodes b(i) The maximum value of is the bandwidth of the whole graph . The node arrangement that requires a given graph to minimize its bandwidth .

The simplest idea is to recursively enumerate all permutations , But obviously, the amount of calculation is too large , Moreover, there are no obvious constraints like the eight queens problem that can make some nodes interrupt and extend in advance .

In fact, optimization methods can still be found —— Record the minimum bandwidth currently found k, If it is found that the distance between two nodes is greater than or equal to k, Then the arrangement cannot be better than the solution of the current record , So it can be terminated decisively . In the solution tree, it is called “ prune ”(prune).

besides , According to the mathematical relationship of nodes , There is m Nodes of adjacent nodes u, Ideally, these adjacent nodes are u Back , Make the bandwidth m. So if m≥ At present k, Then the permutation can't get a better solution anyway .

Difficult string Krypton Factor, Uva 129

The difficult string refers to “ A string that does not contain two adjacent repeated substrings ”, such as D,DC,ABDAB etc. .... The title requires a positive integer n and L, The output is preceded by the alphabet L Letter composition 、 Dictionary preface No n Small “ Difficult string ”.

Because only “ adjacent ” The substring of is counted into , So you only need to judge the suffix of the current string, not the whole string ：

int dfs(int cur){
    if(cnt++ ==n){
        for(int i=0;i<cur;i++)
            printf("%c",'A'+S[i]);  // Output 
        printf("\n");
        return 0;
    }
    for(int i=0;i<L;i++){
        S[cur]=i;
        int ok=1;
        for(int j=1;j*2<=cur+1;j++){
            int equal=1;
            for(int k=0;k<j;k++)
                if(S[cur-k]!=S[cur-k-j]){ equal=0;break; }
            if(equal){ ok=0;break; }  // The first half is equal to the second half , illegal 
        }        
        if(ok) if(!dfs(cur+1)) return 0;
    }
    return 1;
}

End of today , Clear the learning path to find problems