回溯算法二：算法框架与实现

一、算法框架分析

1、刻画组合各自特性的动态属性统一表示如下：
（1）MAKE-ITEMS:生成当前节点的取值集合；
（2）IS-PARTIAL:判断部分解；
（3）IS-COMPLETE:判断完整解；
（4）PRINT-SOLUTION:打印一个合法解，输出结果；
静态属性：
（5）问题的解向量长度：n
（6）问题的解向量x

2、组合问题抽象描述如下：

输入：解向量的最大长度n，解向量x，产生解向量第k个分量取值集合items={items1,items2,...,itemsm}的过程MAKE-ITEMS，判断部分解规则IS-PARTIAL，判断完整解的规则IS-COMPLETE,打印合法解的方法PRINT-SOLUTION的组合问题P。

输出：如果问题P有合法解，输出所有合法解，否则输出无解信息。

3、算法框架如下：

设解向量的分量取值集合items有m个元素，解向量的维数为n，则解空间可以组织为高度为n的m叉完全树。

回溯算法框架：

BACKTRACK(P)
1 flag = false           // 是否有解标志
2 为解向量x分配存储空间    // malloc
3 EXPLORE(P, 1)          // 探索过程
4 if flag == false       // 判断解标志
5	then print_error "no solution"    // 打印无解信息

探索过程EXPLORE：

EXPLORE(P, K)
1 if IS-COMPLATE(X)                  // 判断解向量是否完全
2    then flag = true                // 若为完全解，则置解标志，输出解信息，并返回
3         PRINT-SOLUTION(X)
4         return		     // 需要分析，是否需要输出所有的完整解
5 if k > n			     // k为当前解向量长度，n为解向量的最大长度
6    then return                     // 若k>n,表示当前分支遍历完全且无解，直接返回
7 items = MAKE-ITEMS(K)              // 生成当前节点的取值集合
8 m = length(items)                  // 集合长度
9 for i=(1,...,m)                    // 对当前第k个分量，逐一检测各种可能的取值
10    do x[k] = items[i]            
11        if IS-PARTIAL(x, k)        // 确定是否为部分解
12            then 	EXPLORE(P, k+1)  // 继续递归下一步探索过程

二、 框架代码实现

结构体及变量定义：

// 单链表定义
struct List {
    void *data;
    struct List *next;
};
typedef struct List List;

// 变量定义
void *x;                                 // 解向量
int n;                                   // 解向量长度
int elesize;                             // 解向量元素存储长度
int flag = 0;                            // 解标志

int (*isComplete)(void *x, int k);       // 判断完整合法解
void (*printSolution)(void *x, int k);   // 打印解向量
List (*makeItems)(int k);                // 生成第k个分量的选项表
int (*isPartial)(void *x, int k);        // 判断部分合法解

算法框架实现：

void backtrack(void(*explore)(int))
{
    explore(0);
    if (!flag) {
        printf("no solution.\n");
    }
}

void generalExplore(int k)
{
    int i;
    if (isComplete(x, k)) {
        flag = 1;
        printSolution(x, k);
        return;
    }

    if (k >= n) {
        return;
    }

    List *iterms = makeIterms(k);
    List *q = iterms;
    while (q != NULL) {
        memcpy(x + k * elesize, q->data, elesize);
        if (isPartial(x, k)) {
            generalExplore(k + 1);
        }
        q = q->next;
    }

    listClear(iterms);
    free(iterms);
    iterms = NULL;
}

三、 m-着色问题：代码实现

待续

回溯算法二：算法框架与实现

原文：https://www.cnblogs.com/HZL2017/p/14635547.html