Prime Ring Problem HDU - 1016（带回溯的DFS）

回溯法中，首先需要明确下面三个概念：
（一）约束函数：约束函数是根据题意定出的。通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分。因此，约束函数是对于任何状态空间树上的节点都有效、等价的。
（二）状态空间树：刚刚已经提到，状态空间树是一个对所有解的图形描述。树上的每个子节点的解都只有一个部分与父节点不同。
（三）扩展节点、活结点、死结点：所谓扩展节点，就是当前正在求出它的子节点的节点，在DFS中，只允许有一个扩展节点。活结点就是通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义）。
为什么用DFS
深度优先搜索（DFS）和广度优先搜索（BFS）
在分支界限法中，一般用的是BFS或最小耗费搜索；其思想是一次性将一个节点的所有子节点求出并将其放入一个待求子节点的队列。通过遍历这个队列（队列在遍历过程中不断增长）完成搜索。而DFS的作法则是将每一条合法路径求出后再转而向上求第二条合法路径。而在回溯法中，一般都用DFS。为什么呢？这是因为可以通过约束函数杀死一些节点从而节省时间，由于DFS是将路径逐一求出的，通过在求路径的过程中杀死节点即可省去求所有子节点所花费的时间。BFS理论上也是可以做到这样的，但是通过对比不难发现，DFS在以这种方法解决问题时思路要清晰非常多。
原文：https://blog.****.net/onlyou2030/article/details/49045513

#include <stdio.h>
#include <string.h>

bool mark[21];  //mark[i]用于标记i是否被填充 
int list[21];
int n;    //总共的个数 

int prime[] = {3,5,7,11,13,17,19,23,29,31,37};

bool judge(int x)   
{
    for(int i = 0; i < 11; i++)
        if(x == prime[i])
            return true;
    return false;
}

void print()
{
    for(int i = 1; i <= n; i++)
    {
        if(i == 1)
            printf("%d", list[i]);
        else
            printf(" %d", list[i]);
    }
    printf("\n");
}

//x表示下标，当前正在填充list[x] 
void DFS(int x)
{
    //判断第一个和最后一个数是否满足条件 
    if(x == n+1 && judge(list[x-1] + list[1]))
    {
        print();
        return;
    }
        
    //将2和n之间的数填进list[x]中 
    for(int i = 2; i <= n; i++)
    {
        if(mark[i])   //如果i已经被填充 
            continue;
        list[x] = i;    //试探i填进list[x] 
        if(judge(list[x] + list[x-1]))     //判断list[x]和list[x-1]是否满足条件
        {
            mark[i] = true;
            DFS(x+1);
            mark[i] = false;
        } 
    }
}

int main()
{
    int num = 1;
    while(~scanf("%d", &n))
    {
        memset(mark, 0, sizeof(mark));
        list[1] = 1;
        mark[1] = true;
        printf("Case %d:\n", num++); 
        DFS(2);
        printf("\n");
    }    
    return 0;    
}

Prime Ring Problem HDU - 1016（带回溯的DFS）

相关推荐