0x08算法设计与分析复习（二）：算法设计策略-回溯法2 算法设计策略-回溯法

参考书籍：算法设计与分析——C++语言描述（第二版）

子集和数

问题描述

已知n个不同的正数。

回溯法求解

对于子集和数问题问题，可采用两种不的解结构形式：可变长度元组和固定长度元组。

• 采用可变长度元组表示解

  当采用可变长度元组表示解时，代表一个可行解的元组长度可以不同，成为一个k-元组。

• 采用固定长度元组表示解

  固定长度n-元组。

一般称从n个元素的集合中找出满足某些性质的子集的状态空间树为子集树。子集树有。

最后讨论子集和数的约束函数

• 因为如果上式得不到满足，那么意味着当剩余的正数全部加入子集后，子集中的正数之和仍小于不可能导致一个答案状态。

如果假定n个正数

• 因为如果子集中加入下一个待选的正数。

根据上面两式，可以得到约束函数：

子集和数算法

函数定义：

void SumOfSub(float s, int k, float r, int *x, float m, float *w)

• 前置条件：
• 后置条件：在以为根的子树上搜索答案状态

函数SumOfSub的初始条件是。

//子集和数的回溯算法
void SumOfSub(float s, int k, float r, int *x, float m, float *w)
{
    x[k]=1;
    if(s+w[k]==m){
        for(int j = 0;j<k;j++){
            //得到一个可行解
            cout << x[j]<<" ";
        }
        cout << endl;
    } else if(s+w[k]+w[k+1]<=m){
            //搜索左子树
            SumOfSub(s+w[k],k+1,r-w[k],x,m,w);
    }
    if((s+r-w[k]>=m)&&(s+w[k+1]<=m)){
        x[k]=0;
        //搜索右子树
        SumOfSub(s,k+1,r-w[k],x,m,w);
    }
}

void SumOfSub(int *x,int x, float m,float *w)
{
    float r=0;
    for(int i = 0;i<n;i++){
        r=r+w[i];
        //计算r=sum_{i=k}^{n-1}w[i];
    }
    if(r>=m && w[0]<=m)
        SumOfSub(0,0,r,x,m,w);
}

图的着色

问题描述

已知无向图和m中不同颜色，如果只允许使用这m中颜色对图G的结点着色，每个结点着一种颜色，问是否存在一种着色方案，使得图中任意相邻的两个结点都有不同的颜色。这就是m-着色判定问题（m-colorability decision problem）。对给定的无向图G，求对图G的结点着色所需的最少颜色数m，使得图中任意两个相邻结点有不同的颜色。这被称为m-着色最优化问题（m-colorability optimization problem），整数m称为图G的着色数（chromatic number）。

回溯法求解

设无向图

下面采用n-元组。

约束函数的设计：约束函数从隐式约束产生，对所有i和j。

图着色算法

//图的m-着色算法
template<class T>
void MGraph<T>::NextValue(int k,int m,int *x)
{
    //本函数在[1,m]中为x[k]确定一个值最小，且不与其邻接点冲突的颜色
    //x[k]=0表示没有可用颜色，颜色从1开始编号
    do{
        x[k]=(x[k]+1)%(m+1);//尝试下一种颜色
        if(!x[k])
            return;//没有可用颜色
        for(int j=0;j<k;j++){
            if(a[k][j] && x[k]==x[j]){
                //若(i,j)是图的边，且相邻结点k和j颜色相同
                break;//发生冲突，选择下一种颜色
            }
        }
        if(j==k)
            return;//成功选择一种颜色返回
    }while(1);
}

template<class T>
void MGraph<T>::mColoring(int k,int m,int *x)
{
    do{
        NextValue(k,m,x);//为x[k]分配颜色
        if(!x[k])
            break;//x[k]=0表示没有适当的颜色
        if(k==n-1){
            //得到图G的一种m-着色方案
            for(int i=0;i<n;i++){
                cout << x[i] <<" ";
            }
            cout << endl;
        } else {
            //已经对前k个结点分配了颜色，尝试其余结点
            mColoring(k+1,m,x);
        }
    }while(1);
}

template<class T>
void MGraph<T>::mColoring(int m,int *x)
{
    mColoring(0,m,x);
}

函数mColoring对一个给定的无向图G和m，列出图中结点的所有可能的m-着色方案。算法以深度优先方式生成状态空间树中的结点，寻找所有答案结点，即m-着色方案。搜索中使用约束函数剪去不可能包含答案结点的分枝。

时间分析

算法的计算时间上界可以由状态空间树的结点树

哈密顿环

问题描述

已知图外，路径上其余各点各不相同。并不是每个连通图都存在哈密顿环。

哈密顿环算法

对于n个结点的图。

//哈密顿环算法
//，函数NextValue的功能是约束函数。
template<class T>
void MGraph<T>::NextValue(int k,int *x)
{
    //函数NextValue的功能是约束函数
    do{
        x[k]=(x[k]+1)%n;//下一个结点编号
        if(!x[k])
            return;
        if(a[x[k-1]][x[k]]){
            //检查(x[k-1],x[k])是否是图中一条边
            for(int j=0;j<k;j++){
                //检查与前k个结点是否相同
                if(x[j]==x[k])
                    break;
            }
            if(j==k){
                //x[k]是当前可取的结点编号
                if((k<n-1)||((k==n-1)&&a[x[n-1]][x[0]]))
                    return;
            }
        }
    }while(1);
}

template<class T>
void ExtMGraph<T>::Hamiltonian(int k,int *x)
{
    //递归函数Hamiltonian实际计算哈密顿环
    do{
        NextValue(k,x);//产生x[k]的下一个值
        if(!x[k])
            return;//x[k]=0表示x[k]已经没有可取的值
        if(k==n-1){
            //输出一个哈密顿环
            for(int i=0;i<n;i++){
                cout << x[i]<<" ";
            }
            cout << "0" << endl;
        } else {
            //深度优先进入下一层
            Hamiltonian(k+1,x);
        }
    }while(1);
}

template<class T>
void ExtMGraph<T>::Hamiltonian(int *x)
{
    Hamiltonian(1,x);//x[0]=0为约定的起始结点
}