回溯法简介
回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。
回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：
- 1. 使用约束函数，剪去不满足约束条件的路径；
- 2.使用限界函数，剪去不能得到最优解的路径。
问题的关键在于如何定义问题的解空间，转化成树（即解空间树）。解空间树分为两种：子集树和排列树。两种在算法结构和思路上大体相同。
素数环问题
Problem Description
A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.
Note: the number of first circle should always be 1.
Input
n (0 < n < 20).
Output
The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.
You are to write a program that completes above process.
Print a blank line after each case.
Sample Input
6 8
Sample Output
Case 1:
- 1 4 3 2 5 6
- 1 6 5 2 3 4
Case 2:
- 1 2 3 8 5 6 7 4
- 1 2 5 8 3 4 7 6
- 1 4 7 6 5 8 3 2
- 1 6 7 4 3 8 5 2
C++代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<iostream> #include<vector> using namespace std; //Nmax = 17 //Prime Ring int n; int ans[22]; bool hashx[22]; int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41}; bool isPrime(int x){ for(int i = 0; i < 13; i++){ if(prime[i] == x)return true; } return false; } void checkAndPrint(){ //检查输出由回溯法枚举得到的解 if(! isPrime(ans[n] + ans[1]))return; //判断最后一个数与第一个数是否为素数，若不是则直接返回 for(int i = 1; i <= n; i++){ printf("%d%s", ans[i], i == n ? "\n" : " "); } } void DFS(int num){ //num为环中的个数 if(num > 1){ if(!isPrime(ans[num] + ans[num - 1]))return; //如果不是素数，则返回 } if(num == n){ checkAndPrint(); //输出结果 return; } for(int i = 2; i <= n; i++){ if(!hashx[i]){ //没有被放入 hashx[i] =true; ans[num + 1] = i; DFS(num + 1); //继续尝试放入下一个 hashx[i] = false; //回溯后，重新标记为未使用 } } } int main(){ int casex = 0; while(cin>>n){ casex++; for(int i = 0; i < 22; i++)hashx[i] = false; ans[1] = 1; printf("Case %d:\n", casex); hashx[1] = true; //标记1已经被使用 DFS(1); } return 0; } |
