算法分析理论及应用实验7-回溯问题的实践.pdf

《算法分析理论及应用》课程实验报告

一、实验题目

1.图着色问题：给定无向连通图Gm种不司的颜色。用这些颜色为图G的各

顶点着色，每个顶点着一种颜色。如果有一种着色法使G中短条边的两个顶点着不

同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图Gm种颜色，

找出所有不同的着色法。

【输入格式】第1行有3个正整数n、km,表示给定的图G有n个顶点k

条边，m种颜色。顶点编号为1,2,…，n。接下来的k行中，每行有两个正整数u、

v,表示图G的一条边（u,v）o

【输出格式】程序运行结束时，将计算出的不同的着色方案数输出。如果不能着

色，程序输出-1。

【输入样例】

443

12

13

14

24

【输出样例】

12

请写出算法时间复杂度、算法策略基（于回溯法），算法伪代码以及代码实现。

2.0/1背包问题。有n个重量分别为w｛l,w2,…，wn｝的物品，它们的价值分

别为v｛l,v2,…，vn｝,给定一个容量为Q的背包。

设计从这些物品中选取一部分物品放入该背包的方案，每个物品要么选中要么不

选中，要求选中的物品不仅能够放到背包中，而且重量恰好为Q具有最大的价值。

0/1背包问题（Q=6）：

物品编号重量价值

154

234

323

411

请写出算法时间复杂度、算法策略基（于回溯法），算法伪代码以及代码实现。

3.选（做题）八皇后问题：八皇后问题是十九世纪著名的数学家高斯于1850年

提出的。问题是：在8X8的棋盘上摆放八个皇后，使其不能互相攻击，即任意两个

皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题,

即在nXn的棋盘上摆放n个皇后，使任意两个皇后都不能处于同一行、同一列或同

一斜线上。

请写出算法时间复杂度、算法策略(基于回溯法)，算法伪代码以及代码实现。

二、实验内容

1.图着色问题：给定无向连通图Gm种不司的颜色.用这些颜色为图G的各

顶点着色，每个顶点着一种颜色。如果有一种着色法使G中每条边的两个顶点着不

同颜色，则称这个图是m可着色的。图的m着色问题是对于给定图Gm种颜色，

找出所有不同的着色法。

【输入格式】第1行有3个正整数n、km,表示给定的图G有n个顶点k

条边，m种颜色。顶点编号为1,2,…，n。接下来的k行中，每行有两个正整数u、

v