回溯算法(解决着色问题).docx

实验四 回溯算法
、实验目的
1） 理解回溯算法的基本原理，掌握使用回溯算法求解实际问
题。
二、方法原理
回溯法是一种类似穷举的搜索尝试过程，主要是在搜索尝试
过程中寻找问题的解，当发现已不满足求解条件时，就回退，尝 试别的路实验四 回溯算法
、实验目的
1） 理解回溯算法的基本原理，掌握使用回溯算法求解实际问
题。
二、方法原理
回溯法是一种类似穷举的搜索尝试过程，主要是在搜索尝试
过程中寻找问题的解，当发现已不满足求解条件时，就回退，尝 试别的路径。
三、实验设备
PC机一台，C语言、PASCAL语言、Mat lab任选
四、掌握要点
搜索到解空间树的任一结点时，总是先判断该结点是否肯定
不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子 树的系统搜索，逐层向其祖先结点回溯；否则进入该子树，继续 按深度优先的策略进行搜索。
五、实验内容
实验内容：（二选一）1）编写程序实现4 后问题的求解；2
编写程序实现用3 种颜色为图2着色问题；
图2
六、实验要求
1) 认真分析题目的条件和要求，复习相关的理论知识， 选择适当的解决方案和算法；
编写上机实验程序，作好上机前的准备工作；
上机调试程序，并试算各种方案，记录计算的结果(包 括必要的中间结果)；
分析和解释计算结果；
按照要求书写实验报告； 源代码：着色问题
# i n c l u d e < s t d i o. h >
# i n c l u d e < s t d l i b. h > # d e f i n e T R U E 1
# d e f i n e F A L S E 0 # d e f i n e M A X 5 # d e f i n e C O L O R C O U N T 3 int TF(int color, int index, int m[][MAX], int p[]) {
for (int i = 0; i < MAX; i++) {
// 顶 点 index 没 有 邻 接 顶 点 的 话 就 继 续
if (m[index][i] == 0)
continue;
//颜色是否和要填的颜色重复 if (p[i] == color)
return FALSE;
}
return TRUE;
}
void
show(
int
p
[])
{
int
i;
for
(i =
0;
i
<
MAX; i++)
printf("%d ", p[i]);
printf("\n");
}
void back(int p[], int m[][MAX], int index,
int colorcount) {
for (int i