着色问题

问题分析

假设地图共有7个区域,分别是A/B/C/D/E/F/G,对上面顺序进行编号,每个区域用一个结点表示,相邻的区域有连线,那么地图就转化成一个无向连接图。

算法设计

  1. 定义问题的解空间。图的m着色问题解空间形式为n元组{x1,x2,…,xi,…,xn},每个分量取值为1,2,3,…,m,即问题的解是一个n元向量。由此可得,问题的解空间为{x1,x2,…,xi,…,xn},其中显约束为xi=1,2,…,m。
  2. 确定解空间的组织结构:一颗满m叉树,树的深度为n。
  3. 搜索解空间
    • 约束条件:假设当前扩展结点位于解空间树的第t层,那么从第1到第t-1层的结点情况都已经确定,接下来是按照扩展结点的第一个分支进行扩展,此时需要判断是否将第t个结点着色情况。第t个结点的色号要与前t-1个结点中与其有边相连的结点颜色不同,如果有颜色相同的,则第t个结点不能用这个色号,换下一个色号尝试。
    • 限界条件:无。
    • 搜索过程:扩展结点沿着第一个分支扩展,判断约束条件,满足则进入深一层继续搜索;如果不满足,则扩展生成的结点被剪掉,换下一个色号尝试。如果所有色号都尝试完毕,该结点变成死结点,向上回溯到距离其最近的活结点,继续搜索。搜索到叶子结点时,找到一种着色方案,搜索过程直到全部活结点变成死结点为止。

解题过程

地图7个区域,3种颜色。
1. 开始搜索第1层(t=1)。扩展A结点第一个分支,首先判断是否满足约束条件,因为之前还未着色任何结点,所以满足约束条件,扩展该分支,令1号结点着1号色,即x[1]=1,生成B。
2. 拓展B结点(t=2)。扩展第一个分支x[2]=1,首先判断2号结点是否和前面已经确定色号的结点(1号)有边相连且色号相同,不满足约束条件,剪掉该分支,然后沿着x[2]=2扩展,2号结点和前面已经确定色号的结点(1号)有边相连,但色号不同,满足约束条件,扩展该分支,令x[2]=2。
3. 扩展C结点(t=3)。扩展第一个分支x[3]=1,首先判断3号结点是否和前面已经确定色号的结点(1、2号)有边相连且色号相同,不满足约束条件,剪掉该分支;同理剪掉x[3]=2分支。然后沿着x[3]=3扩展,3号结点和前面已经确定色号的结点(1、2号)有边相连,但色号不同,满足约束条件,扩展该分支,令x[3]=3。生成D。
4. 扩展D结点(t=4)。扩展第一个分支x[4]=1,首先判断4号结点是否和前面已经确定色号的结点(1、2、3号)有边相连且色号相同,不满足约束条件(4余1相连),剪掉该分支;然后令x[4]=2,符合条件,生成E。
5. 扩展E结点(t=5)。扩展第一个分支x[5]=1,首先判断4号结点是否和前面已经确定色号的结点(1、2、3号)有边相连且色号相同,确定5与2、3、4相连但色号不同,满足约束条件,扩展该分支,生成F。
6. 扩展F结点(t=6)。扩展第一个分支x[6]=1,同理不满足,剪掉分支;然后沿着x[6]=2扩展,6与5号有边相连但色号不同,故满足约束条件,扩展该分支,令x[6]=2,生成G。
7. 扩展G结点(t=7)。扩展第一个分支x[7]=1,剪掉x[7]=1和x[7]=2的分支,然后令x[7]=3,符合要求,生成H。
8. 扩展H结点(t=8)。t>n,找到一个可行解,输出该可行解{1,2,3,2,1,2,3},回溯到最近的活结点G。
9. 重新扩展G结点(t=7)。G已经考察完毕,成为死结点,回溯到最近的活结点F。
10. 继续搜索,又找到第二种着色方案,输出可行解{1,3,2,3,1,3,2}。
11. 继续搜索,又找到4个可行解。

代码实现

//约束条件bool isRight(int t){ for (int j = 1; j < t; j++) { if (map[t][j]) { if (x[j] == x[t]) return false; } } return true;}//回溯方法函数void Backtrack(int t){ if (t > n) { sum++; cout << "第" << sum << "种方案:"; for (int i = 1; i <= n; i++)//输出该着色方案 { cout << x[i] << " "; } cout << endl; } else { for (int i = 1; i <= m; i++) { x[t] = i; if (isRight(t)) Backtrack(t + 1); } }}

算法复杂度分析

  1. 时间复杂度:O(nmn)。
  2. 空间复杂度:O(n)。

n皇后问题

问题介绍

在n×n的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋规则,皇后可以攻击与之在同一行、同一列、同一斜线上的棋子。现在在n*n的棋盘上放置n个皇后,使其不受攻击。

问题分析

求解策略:
以行为主导:
– 在第1行第1列放置第一个皇后。
– 在第2行放置第2个皇后。第2个皇后的位置不能和前面的皇后同列、同斜线,不用再判断同行了,因为每行我们本来就只放一个。
– 在第3行放置第3个皇后。第3个皇后的位置不能和前面的皇后同列、同斜线。
– ……
– 在第t行放置第t个皇后。第t个皇后的位置不能和前面的皇后同列、同斜线。
– ……
– 在第n行放置第n个皇后。第n个皇后的位置不能和前面的皇后同列、同斜线。

算法设计

(1)定义问题的解空间。n皇后问题解的形式为n元组:{x1,x2,…,xi,…,xn},分量xi表示第i个皇后放置在第i行第xi列,xi取值为1,2,3,…,n。显约束为不同行。

(2)解空间的组织结构:一颗m(m=n)叉树,树深度为n。

(3)搜索解空间。
约束条件:在第t行放置第t个皇后时,第t个皇后的位置不能和前t-1个皇后同列、同斜线。第i个皇后和第j个皇后不同列,即xi!=xj

限界条件:不需要设置。

搜索过程:

从根开始,以DFS的方式进行搜索。根节点是活结点,并且是当前的扩展结点。在搜索过程中,当前的扩展结点沿纵深方向移向一个新结点,判断该新结点是否满足隐约束。如果满足,则该新结点成为活结点,并且成为当前的扩展结点,继续深一层的搜索;如果不满足,则换到该新结点的兄弟结点继续搜索;如果新结点没有兄弟结点,或其兄弟结点已全部搜索完毕,则扩展结点成为死结点,搜索回溯到其父结点处继续进行。搜索过程直到找到问题的根结点变成死结点为止。

代码实现

bool isPlace(int t){ bool place = true; for (int j = 1; j < t; j++) { if (x[t] == x[j] || t - j == fabs(x[t] - x[j]))//判断列、对角线是否冲突 { place = false; break; } } return place;}void backtrack(int t){ if (t > n) { countn++; for (int i = 1; i <= n; i++) { cout << x[i] << " "; } cout << endl; cout << "---------" << endl; } else {//分别判断n个分支,特别注意i不要定义为全局变量,否则递归调用有问题 for (int i = 1; i <= n; i++) { x[t] = i; if (isPlace(t)) backtrack(t + 1); //上面说的是不冲突就进行下一行搜索 } }}

算法复杂度分析

  1. 时间复杂度:O(nn+1)。
  2. 空间复杂度:O(n)。