使用回溯算法求解骑士游历问题
求解骑士游历问题
显然求解骑士游历问题的每一步就是马在棋盘上走的一步。在每一步马需要选择一个方向进行游历，这时记住解的每一步需要记住两件事：
1.当前步的行列位置
2.当前步已经试探过哪些方向了，以便回溯回来时能够选择一个新的方向进行试探
所以使用两个数组，数组board记住棋盘的每个位置是在马的第几步到达的，这反映了问题的解，即第几步到哪个位置。数组direction记住在棋盘的某个位置已经试探过的方向，每个位置有八个方向，可按某种顺序对八个方向编号，然后在每个位置按编号顺序试探方向。
在确定数据结构之后，同样需要确定下面几个问题：
1.怎样的状态是初始状态。
2.怎样选择当前步可能的路线
3.怎样表示向前推进一步
4.怎样回溯及清除当前步的痕迹
显然初始状态是棋盘的每个位置都置为第0步到达（即还没有到达），每个位置都还没有选择任何方向（可赋值MAX_DIR(=8)表示没有选择方向）。
选择当前步可能的路线就是在当前位置选择一个方向来游历下一步。在选择的时候同样需要区分是从第0个方向开始考虑还是从上一次的下一个方向开始考虑。为了方便从下一个方向开始考虑，实际上数组direction在某一位置(curr_x, curr_y)的值记住的是从上一位置选择了哪个编号的方向而到达的，这样容易回溯到上一位置，而且容易在回溯到上一位置之后从下个一方向重新试探。
向前推进一步则要根据所选择的方向推进到下一位置，记住到下一位置所选择的方向，下一位置是第几步到达的，然后增加步数。
回溯一步则要标记当前位置没有到达过（将到达的步数置为0），根据上一步到当前位置的所选择的方向（这个方向是记录当前位置所对应的direction数组中）而回溯到上一位置，然后减少步数。
下面程序用类KNIGHT来封装数组board、direction、当前位置(curr_x, curr_y)、当前步数(step)，并且使用last_direction来记住上一位置到当前位置所选择的方向。为了方便计算选择一个方向后从当前推进到下一位置，使用数组var_x和var_y来记住每个方向在x方向和y方向的改变值。这个类中提供的方法的含义与类QUEEN类似。为节省篇幅起见，我们将类的界面、实现及演示放在了同一文件。
// 文件：KNIGHT.CPP
// 功能：使用回溯算法求解骑士游历问题
#include
#include
enum BOOLEAN {
TRUE = 1,
FALSE = 0
};
const int MAX_WIDTH = 30;
const int MAX_DIR = 8;
class KNIGHT {
public:
// FUNCTION: 设置初始状态
KNIGHT(int width);
// FUNCTION: 用比较直观的方式打印问题的解
// REQUIRE: 必须先调用了成员函数tourist()
void print();
// FUCTION: 根据马的起始位置(start_x, start_y)使用回溯算法求骑士游历问题的一个解
// REQUIRE: (start_x, start_y)必需在所设置的棋盘宽度范围内
BOOLEAN tourist(int start_x, int start_y);
protected:
// FUNCTION: 初始化记录所选方向的数组，将每个值置为MAX_DIR
void init_direction();
// FUNCTION: 初始化记录马在第几步到位每个位置的数组，将每个值置为0 void init_chessboard();
// FUNCTION: 设置初始状态，包括初始化方向数组和棋盘数组，并设置马的初始位置
void set_start(int x, int y);
// FUNCTION: 在当前位置选择一个方向以推进到下一位置
// RETURN: 如果可选择一个方向推进则返回TRUE，否则返回FALSE
// NOTE: 将该函数定义为虚函数，以便下面快速游历的类来重定义该函数而产生动态绑定
virtual BOOLEAN select_direction();
// FUNCTION: 从当前位置回溯到上一位置
// NOTE: 将该函数定义为虚函数，以便下面快速游历的类来重定义该函数而产生动态绑定
virtual void backward();
// FUNCTION: 从当前位置推进到下一位置
// NOTE: 将该函数定义为虚函数，以便下面快速游历的类来重定义该函数而产生动态绑定
virtual void forward();
// FUNCTION: 判断马是否能够走向位置(x, y)。
// RETURN: 如果马已经到过该位置，或该位置超出棋盘范围返回FALSE，否则返回TRUE
BOOLEAN is_legal(int x, int y);
// FUNCTION: 判断是否回溯到初始状态
// RETURN: 如果步数回到第1步则表示回到初始状态而返回TRUE，否则返回FALSE
BOOLEAN back_to_start();
// FUNCTION: 判断是否游历完所有位置
// RETURN: 如果步数等于棋盘格子数则表示游历完所有位置而返回TRUE，否则返回FALSE
BOOLEAN is_end();
// 下面两个数组用来记住选择某个方向后，推进到下一位置时x方向和y方向的值的变化
int var_x[MAX_DIR];
int var_y[MAX_DIR];
// 记录马第几步到达某个位置的棋盘数组
int chessboard[MAX_WIDTH][MAX_WIDTH];
// 记录马在某个位置是在上一位置选择第几个方向到达的
int direction[MAX_WIDTH][MAX_WIDTH];
int width; // 棋盘宽度
int curr_x, curr_y; // 马的当前位置
int step; // 已经游历的步数
int last_direct
ion; // 上一位置到当前位置所选的方向
};
KNIGHT::KNIGHT(int width)
{
this->width = width;
init_direction();
total_step = 0;
}
void KNIGHT::print()
{
int x, y;
cout << " +";
for (x = 0; x < width; x = x + 1) cout << "----+";
cout << '\n';
for (x = 0; x < width; x = x + 1) {
cout << " |";
for (y = 0; y < width; y = y + 1) cout << setw(3) << chessboard[x][y] << " |";
cout << '\n';
cout << " +";
for (y = 0; y < width; y = y + 1) cout << "----+";
cout << '\n';
}
}
BOOLEAN KNIGHT::is_legal(int x, int y)
{
if (x < 0 || x >= width) return FALSE;
if (y < 0 || y >= width) return FALSE;
if (chessboard[x][y] > 0) return FALSE;
return TRUE;
}
BOOLEAN KNIGHT::back_to_start()
{
if (step == 1) return TRUE;
else return FALSE;
}
BOOLEAN KNIGHT::is_end()
{
if (step > width * width) return TRUE;
else return FALSE;
}
void KNIGHT::set_start(int x, int y)
{
curr_x = x; curr_y = y; step = 1;
chessboard[x][y] = step; step = step + 1;
direction[x][y] = MAX_DIR;
last_direction = MAX_DIR;
}
BOOLEAN KNIGHT::select_direction()
{
int try_x, try_y;
// last_direction为MAX_DIR表示当前位置是一个新的位置，在新推进到某个位置(curr_x, curr_y)时，
// direction[curr_x][curr_y]会记录上一位置到(curr_x, curr_y)时所选择的方向，这时
// last_direction置为MAX_DIR用来标记该位置是新推进的位置。
if (last_direction == MAX_DIR) last_direction = 0;
else last_direction = last_direction + 1;
while (last_direction < MAX_DIR) {
// 看下一步推进到哪个位置是合法的，如果合法则选择该方向。
try_x = curr_x + var_x[last_direction];
try_y = curr_y + var_y[last_direction];
if (is_legal(try_x, try_y)) break;
last_direction = last_direction + 1;
}
if (last_direction == MAX_DIR) return FALSE;
else return TRUE;
}
void KNIGHT::backward()
{
step = step - 1;
chessboard[curr_x][curr_y] = 0;
// 将last_direction置为上一位置到(curr_x, curr_y)所选择的方向
last_direction = direction[curr_x][curr_y];
// 根据这个方向回溯到上一位置，同时回溯到上一位置之后，在上一位置再试探时应该从
// last_direction+1的方向开始。参看成员函数select_direction()。
curr_x = curr_x - var_x[last_direction];
curr_y = curr_y - var_y[last_direction];
}
void KNIGHT::forward()
{
// 在推进时last_direction是当前位置所选择的方向
curr_x = curr_x + var_x[last_direction];
curr_y = curr_y + var_y[last_direction];
chessboard[curr_x][curr_y] = step;
step = step + 1;
// 这个方向被记录下一位置(这时已经为(curr_x, curr_y))的direction数组中。
direction[curr_x][curr_y] = last_direction;
// last_direction的值已经被记录，这时置为MAX_DIR表示当前位置为新推进的位置
last_direction = MAX_DIR;
}
BOOLEAN KNIGHT::tourist(int start_x, int start_y)
{
init_chessboard();
set_start(start_x, start_y);
do {
if (select_direction()) forward();
else backward();
} while (!back_to_start() && !is_end());
if (back_to_start()) return FALSE;
else return TRUE;
}
void KNIGHT::init_direction()
{
var_x[0] = 2; var_y[0] = 1;
var_x[1] = 1; var_y[1] = 2;
var_x[2] = -1; var_y[2] = 2;
var_x[3] = -2; var_y[3] = 1;
var_x[4] = -2; var_y[4] = -1;
var_x[5] = -1; var_y[5] = -2;
var_x[6] = 1; var_y[6] = -2;
var_x[7] = 2; var_y[7] = -1;
}
void KNIGHT::init_chessboard()
{
int x, y, dir;
for (x = 0; x < width; x = x + 1) {
for (y = 0; y < width; y = y + 1) {
chessboard[x][y] = 0;
}
}
}
int main()
{
int width = 8;
KNIGHT knight(width);
int start_x, start_y;
cout << "\nProgram begin...\n";
start_x = 4; start_y = 4;
if (knight.tourist(start_x, start_y)) {
knight.print();
}else {
cout << "\nHave not found the solution for: ";
cout << "Start: <" << start_x << ", " << start_y << ">, ";
cout << "Width: " << width << "\n";
}
return 1;
}
l 骑士游历问题的快速解
上面求解骑士游历问题的程序效率比较低，对于8×8的棋盘将花费相当长一段时间。为此我们可以在选择当前步的可能路线时增加一些启发式规则，使得这个选择从某种意义下来说是比较好的，从而加速问题的求解过程。
对于骑士游历问题一个启发式规则是，在选择当前步的方向时去选择满足下面条件的方向，当按这个方向推进到下一位置时，这个位置所可以再选择的方向最少。也就是说在当前位置优先选一个走起来比?quot;艰难"的方向来推进。加入这种启发式规则之后，从运行的效果看，在求解的过程中几乎不回溯。
为了使用这个启发式规则，我们首先要修改上面的成员函数
select_direction()。这时在每个位置选择方向时不再是按照一定的顺序来选择，为了避免在回溯时重复选择方向，必需记住在某个位置哪些方向已经选择过了，我们使用三维数组cannot来记住这件事情，当其值为TRUE时表示某个位置的某个方向已经试探过了，为FALSE表示没有试探过。当从当前位置回溯到上一位置是，要先把当前位置所有方向的cannot值置为FALSE，因为下一次再到达这个位置时所有方向需要重新试探。
为了研究加入启发式规则的效果，要求保留上面不使用启发式规则的程序，这样我们从KNIGHT类派生出一个类FAST_KNIGHT来支持快速求解骑士游历问题。在这个类中增加数组cannot，并且只需要重新定义select_direction(), backward()和forward()就可以了。需要重新定义backward()和forward()是因为在这两个成员函数中需要维护数组cannot的值。其它成员函数不用作任何的修改。我们在KNIGHT类中已经将这几个成员函数定义为虚函数，以便在成员函
数tourist()中动态地选择这些函数来调用。读者需要学习完第八章多态性之后才能充分理解动态绑定的含义。
在下面程序中，我们只给出类FAST_KNIGHT的定义，读者很容易修改演示程序以使用类FAST_KNIGHT来求解骑士游历问题。
程序三：快速求解骑士游历问题的程序
// 文件：FASTKNIGHT.CPP
// 功能：使用回溯算法快速求解骑士游历问题
class FAST_KNIGHT: public KNIGHT {
public:
FAST_KNIGHT(int width);
protected:
// FUNCTION: 初始化cannot数组
void init_cannot();
// FUNCTION: 在当前位置根据启发式规则选择一个方向以推进到下一位置
// RETURN: 如果可选择一个方向推进则返回TRUE，否则返回FALSE
// NOTE: 重定义KNIGHT类的select_direction()
virtual BOOLEAN select_direction();
// FUNCTION: 从当前位置回溯到上一位置，注意维持cannot数组
// NOTE: 重定义KNIGHT类的backward()
virtual void backward();
// FUNCTION: 从当前位置根据所选择的方向推进到下一位置
// NOTE: 重定义KNIGHT类的forward()
virtual void forward();
// 用来记住某个位置某个方向是否已经试探过
BOOLEAN cannot[MAX_WIDTH][MAX_WIDTH][MAX_DIR];
};
FAST_KNIGHT::FAST_KNIGHT(int width): KNIGHT(width)
{
init_cannot();
}
void FAST_KNIGHT::init_cannot()
{
int x, y, dir;
for (x = 0; x < width; x = x + 1)
for (y = 0; y < width; y = y + 1)
for (dir = 0; dir < width; dir = dir + 1) cannot[x][y][dir] = FALSE; }
BOOLEAN FAST_KNIGHT::select_direction()
{
int try_x, try_y, next_x, next_y;
int dir_index, next_index;
int min_dir, count;
min_dir = MAX_DIR; last_direction = MAX_DIR;
for (dir_index = 0; dir_index < MAX_DIR; dir_index = dir_index + 1) { // 选择一个方向，使得根据该方向推进到下一位置时，在该位置可选的方向最少
try_x = curr_x + var_x[dir_index];
try_y = curr_y + var_y[dir_index];
if (is_legal(try_x, try_y) && !cannot[curr_x][curr_y][dir_index]) { // 这个位置作为下一位置是合法，那么计算该位置可选的方向
count = 0;
for (next_index = 0; next_index < MAX_DIR; next_index++) {
next_x = try_x + var_x[next_index];
next_y = try_y + var_y[next_index];
if (is_legal(next_x, next_y)) count = count + 1;
}
if (count < min_dir) {
// 记录具有最少可选方向的下一位置
last_direction = dir_index;
min_dir = count;
}
}
}
if (last_direction == MAX_DIR) return FALSE;
else return TRUE;
}
void FAST_KNIGHT::backward()
{
int dir;
step = step - 1;
chessboard[curr_x][curr_y] = 0;
// 从位置(curr_x, curr_y)回溯，那么下一次再到达该位置时所有方向都需要重新试探
for (dir = 0; dir < MAX_DIR; dir = dir + 1) cannot[curr_x][curr_y][dir] = FALSE;
last_direction = direction[curr_x][curr_y];
curr_x = curr_x - var_x[last_direction];
curr_y = curr_y - var_y[last_direction];
}
void FAST_KNIGHT::forward()
{
// 该位置的这个方向已经试探过了
cannot[curr_x][curr_y][last_direction] = TRUE;
curr_x = curr_x + var_x[last_direction];
curr_y = curr_y + var_y[last_direction];
chessboard[curr_x][curr_y] = step;
step = step + 1;
direction[curr_x][curr_y] = last_direction; last_direction = MAX_DIR;
}
【题03】骑士游历问题
【题3】骑士游历问题 设有一个n*m 的棋盘(2≤n ≤50，2≤m ≤50)，如下图。在棋盘上任一点有一个中国象棋马， 马走的规则为： 1.马走日字 2.马只能向右走。即下图所示： 当n ，m 给出之后，同时给出马起始的位置和终点的位置，试找出从起点到终点的所有路径的数目。例如：(n=10，m=10)，(1，5)(起点)，(3，5)(终点)。应输出2(即由(1，5)到(3，5)共有2条路径，如下图)： 输入： n ，m ，x1，y1，x2，y2(分别表示n ，m ，起点坐标，终点坐标) 输出： 路径数目(若不存在从起点到终点的路径，输出0) 分析：使用回溯法是可以计算路径数目，但问题是搜索效率太低，根本不可能在较短的时间内出解。因为题目并不要求每一条路径的具体走法。在这种情况下，是否非得通过枚举所有路径方案后才能得出路径数目，有没有一条简便和快效的“捷径”呢。 从(x 1，y 1)出发，按照由左而右的顺序定义阶段的方向。位于（x ，y ）左方且可达（x ，y ）的跳马位置集合都是（x ，y ）的子问题，起点至（x ，y ）的路径数实际上等于起点至这些位置集的路径数之和（如下图）。 如此一来，状态转移关系便凸显出来。设状态转移方程map ，其中map[i ，j]为起点（x1，y1）至（i ， j ）的路径数目。由于棋盘规模的上限为50*50，可能导致路径数目大得惊人，因此不妨设map 数组的元素类型为extended 。初始时，除map[x1，y1]=1外其余为０。显然 }),(],[],[{],[),),(在界内的坐标集 可达（y x y x map j i map y x map y x j i ∑∈+=。 我们采用动态程序设计的方法计算起点（x1，y1）至终点（x2，y2）的路径数目map[x2，y2]： 阶段j ：中国象棋马当前的列位置(y 1≤j ≤y2)； 状态i ：中国象棋马在j 列的行位置（1≤i ≤n ）；
迷宫求解问题资料
迷宫求解问题 摘要：用矩阵表示迷宫，将矩阵表示的迷宫转换成无向图，用邻接表存储。对无向图从入口结点开始广度优先搜索，用一个一维数组存储各个结点的前驱结点的编号，通过出口结点Vn找到其前驱结点Vn-1,再通过Vn-1找到Vn-2，依次类推直到找到出口结点。 关键字：矩阵迷宫求解 一、需求分析 1.程序题目： 迷宫求解问题。迷宫是一个如下所示的m行n列的0-1矩阵，0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次移动只能从一个无障碍的单元移到周围8个方向的任意一个无障碍的单元，编写程序给出一条通过迷宫的路径或者报告一个“无法通过”的信息。 入口->(0，0，0，1，0，0，0，1，0，0，0，1，0，0，1) (0，1，0，0，0，1，0，1，0，0，0，1，1，1，1) (0，1，1，1，1，1，0，1，0，0，1，1，1，0，1)
(1，1，0，0，0，1，1，0，1，1，0，0，1，0，1) (1，0，0，1，0，1，1，1，1，0，1，0，1，0，1) (1，0，1，0，0，1，0，1，0，1，0，1，0，1，0) (1，0，1，1，1，1，1，0，0，1，1，1，1，0，0) (1，1，1，0，1，1，1，1，0，1，0，1，0，1，0) (1，0，1，0，1，0，1，1，1，0，1，0，0，0，1) (0，1，0，1，0，1，0，0，0，1，1，0，0，1，0)->出口 2．程序说明及任务： 迷宫问题要求寻找一条从入口到出口的路径。路径是由一组位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居，如图C。 计算机走迷宫的方法是，采取一步一步试探的方法。每一步都从东开始，按顺时针对8个方向进行试探，若某方向上maze（x，y）=0，表示可以通行，则走一步；若maze（x，y）=1，表示不可以通行，须换方向再试，直到8个方向都试过；若maze （x，y）均为1，说明此步已无路可走，需退回一步，在上一步的下一个方向重新开始探测。为此，需设置一个栈，用于记录所走过的位置和方向（i,j,dir）。当退回一步时，从栈中退出一个元素，以便在上一个位置的下一个方向上探测，如又找到一个行进方向，则把当前位置和方向重新进栈，并走到新的位置。
算法分析与程序设计动态规划及回溯法解背包问题
动态规划法、回溯法解0-1背包问题 2012级计科庞佳奇 一、问题描述与分析 1.动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会 有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。 不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。 多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。 01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。 2.回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目 标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
动态规划-骑士游历问题
骑士游历问题 设有一个n*m的棋盘(2≤n≤50，2≤m≤50)，如下图。在棋盘上任一点有一个中国象棋马， 马走的规则为： 1.马走日字 2.马只能向右走。 即下图所示： 当n，m 给出之后，同时给出马起始的位置和终点的位置，试找出从起点到终点的所有路径的数目。例如：(n=10，m=10)，(1，5)(起点)，(3，5)(终点)。应输出2(即由(1，5)到(3，5)共有2条路径，如下图)： 输入： n，m，x1，y1，x2，y2(分别表示为：n，m，起点坐标，终点坐标) 输出： 路径数目(若不存在从起点到终点的路径，输出0) 分析： 使用回溯法是可以计算路径数目，但问题是搜索效率太低，根本不可能在较
短的时间内出解。因为题目并不要求每一条路径的具体走法。在这种情况下，是否非得通过枚举所有路径方案后才能得出路径数目，有没有一条简便和快效的“捷径”呢。 从(x 1，y 1)出发，按照由左而右的顺序定义阶段的方向。位于（x ，y ）左方且可达（x ，y ）的跳马位置集合都是（x ，y ）的子问题，起点至（x ，y ）的路径数实际上等于起点至这些位置集的路径数之和（如下图）。 如此一来，状态转移关系便凸显出来。设状态转移方程map ，其中map[i ，j]为起点（x1，y1）至（i ，j ）的路径数目。由于棋盘规模的上限为50*50，可能导致路径数目大得惊人，因此不妨设map 数组的元素类型为extended 。初始时，除map[x1，y1]=1外其余为０。 显然 }),(],[],[{],[),),(在界内的坐标集可达（y x y x map j i map y x map y x j i ∑∈+= 。 采用动态程序设计的方法计算起点（x1，y1）至终点（x2，y2）的路径数目map[x2，y2]： 阶段j ：中国象棋马当前的列位置(y 1≤j ≤y2)； 状态i ：中国象棋马在j 列的行位置（1≤i ≤n ）； 决策k ：中国象棋马在（i ，j ）的起跳方向(1≤k ≤4)； 计算过程如下： fillchar(map ，sizeof(map)，0)； map[x1，y1] ←1； {从（x1，y1）出发} for j ←y1 to y2 do {递推中国象棋马的列位置} for i ←1 to n do {递推中国象棋马在j 列的行位置}
回溯算法的应用(DOC)
回溯算法的应用 课程名称：算法设计与分析 院系：************************ 学生姓名：****** 学号：************ 专业班级：***************************** 指导教师：****** 2013年12月27日
回溯法的应用 摘要：回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 回溯法，其意义是在递归直到可解的最小问题后，逐步返回原问题的过程。而这里所说的回溯算法实际是一个类似枚举的搜索尝试方法，它的主题思想是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。 回溯算法是尝试搜索算法中最为基本的一种算法，其采用了一种“走不通就掉头”的思想，作为其控制结构。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。 全排列和求最优解问题是比较经典的问题，我们可以采用多种算法去求解此问题，比如动态规划法、分支限界法、回溯法。在这里我们采用回溯法来解决这个问题。 关键词：回溯法全排列最优值枚举
算法设计与分析：回溯法-实验报告
应用数学学院信息安全专业班学号姓名 实验题目回溯算法 实验评分表
实验报告 一、实验目的与要求 1、理解回溯算法的基本思想； 2、掌握回溯算法求解问题的基本步骤； 3、了解回溯算法效率的分析方法。 二、实验内容 【实验内容】 最小重量机器设计问题：设某一个机器有n个部件组成，每个部件都可以m个不同供应商处购买，假设已知表示从j个供应商购买第i个部件的重量，表示从j个供应商购买第i个部件的价格，试用回溯法求出一个或多个总价格不超过c且重量最小的机器部件购买方案。 【回溯法解题步骤】 1、确定该问题的解向量及解空间树； 2、对解空间树进行深度优先搜索； 3、再根据约束条件（总价格不能超过c）和目标函数（机器重量最小）在搜索过程中剪去多余的分支。 4、达到叶结点时记录下当前最优解。 5、实验数据n,m, ] ][ [j i w,] ][ [j i c的值由自己假设。 三、算法思想和实现【实现代码】
【实验数据】 假设机器有3个部件，每个部件可由3个供应商提供（n=3，m=3）。总价不超过7（c<=7）。 部件重量表： 部件价格表： 【运行结果】
实验结果：选择供应商1的部件1、供应商1的部件2、供应商3的部件3，有最小重量机器的重量为4，总价钱为6。 四、问题与讨论 影响回溯法效率的因素有哪些？ 答：影响回溯法效率的因素主要有以下这五点： 1、产生x[k]的时间； 2、满足显约束得x[k]值的个数； 3、计算约束函数constraint的时间； 4、计算上界函数bound的时间； 5、满足约束函数和上界函数约束的所有x[k]的个数。 五、总结 这次实验的内容都很有代表性，通过上机操作实践与对问题的思考，让我更深层地领悟到了回溯算法的思想。 回溯算法的基本思路并不难理解，简单来说就是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。回溯法的基本做法是深度优先搜索，是一种组织得井井
算法实验报告：罗密欧与朱丽叶迷宫求解
河南科技大学 课程设计报告 课程名称：算法设计与分析 设计题目：罗密欧与朱丽叶迷宫求解问题 院系：电子信息工程学院 专业：计算机科学与技术 班级：计算机092班 学生姓名: 学号:09************ 起止日期: 2011年5月28日 - 2011年6月3日指导教师:孙士保、张明川、冀治航
课程设计题目罗密欧与朱丽叶的迷宫问题 姓名*** 学号091040602** 班级092班系别电子信息工程学院专业计算机科学与技术 组别1人组长*** 组员*** 指导教师姓名孙士保、张明川、冀治航 课程设计目的 进一步巩固C程序设计和算法设计与分析的基础知识，提升结构化程序、模块化程序设计的方法和能力，深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。 设计环境1. PC兼容机 2．Windows 2000/XP操作系统3．TC集成开发环境或其他C语言开发环境 课程设计要求和任务要求：1．熟练掌握回溯法，能够利用回溯法解决实际问题； 2．使用文件进行存储和管理。程序启动时可从文件中读取信息，或从键盘输入信息；运行过程中也可对文件进行存取；退出前可选择将部分信息保存 到文件中； 3．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 4．对系统进行功能模块分析、画出总流程图和各模块流程图； 5．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单； 6．通过命令行相应选项能直接进入某个相应菜单选项的功能模块； 7．所有程序需调试通过。 任务：完成罗密欧与朱丽叶的迷宫问题.设计内容包括： 1．确定能对给定的任何位置的罗密欧都能够找到一条通向朱丽叶的路线； 2．程序能够演示一条罗密欧找到朱丽叶的路线过程等。 课程设计工作进度计划 序号起止日期工作内容 1 下发任务书，分组，选定课题，查阅相关资料 2 总体设计，划分模块 3 编制源程序 4 上机调试，修改、完善系统 5 程序检查 6 撰写说明书
搜索与回溯算法介绍
搜索与回溯算法介绍 一、概述： 计算机常用算法大致有两大类：一类叫蛮干算法，一类叫贪心算法。前者常使用的手段就是搜索，对全部解空间进行地毯式搜索，直到找到指定解或最优解。后者在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解。 二、搜索与回溯： 这里着重介绍搜索与回溯。当很多问题无法根据某种确定的计算法则来求解时可以利用搜索与回溯的技术求解。回溯是搜索算法中既带有系统性又带有跳跃性的一种控制策略。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索。在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，然后继续向前探索，如此反复进行，直至得到解或证明无解。如迷宫问题：进入迷宫后，先随意选择一个前进方向，一步步向前试探前进。如果碰到死胡同，说明前进方向已无路可走，这时，首先看其它方向是否还有路可走，如果有路可走，则沿该方向再向前试探；如果已无路可走，则返回一步，再看其它方向是否还有路可走；如果有路可走，则沿该方向再向前试探。按此原则不断搜索回溯再搜索，直到找到新的出路或从原路返回入口处无解为止。 【建立解空间】 问题的解应该如何描述，如何建立呢？问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应到少包含问题的一个（最优）解。借助图论的思想，可以用图来描述，图的定义为G，由顶点集和边集构成，顶点即实实在在的数据、对象，而边可以抽象为关系，即顶点间的关系，这种关系不一定非要在数据结构上表现出来，用数据结构的语言来描述，如果关系是一对一，则为线性表，如果关系是一对多，则为树，如果关系是多对多，则为图，如果完全没有关系，则为集合。但在数据结构中这种关系不一定非要在数据的存储性质上一开始就表现出来，譬如，你可以用一个数组表示一个线性表，也可以表示完全二叉树，同样也可以用邻接表表示一个图，对于关系的描述不是数据结构本身的描述，而是算法的描述，正如数据结构是离不开特定的算法一样，不可分开单独而谈。 确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向
【题5】骑士游历问题(1)
【题5】骑士游历问题（1） 设有一个n*m的棋盘(2≤n≤50，2≤m≤50)，如图10.2.1。在棋盘上任一点有一个中国象棋马， 图10.2.1 马走的规则为： 1.马走日字 2.马只能向右走。即如图10.2.2所示： 图10.2.2 问题：当N，M 输入之后，找出一条从左下角到右上角的路径。例如：输入N=4，M=4。对应的路径如图10.2.3所示： 图10.2.3 输出：路径的格式：(1，1)->(2，3)->(4，4) 若不存在路径，则输出"no" 题解 1.计算跳马方向 按题意，中国象棋马共有四个跳动方向 图10.2.4 我们通过子程序move（x，y，x1，y1，i）计算中国象棋马从（x，y）出发，沿i方向跳至（x1，y1）的过程 procedure move(x，y：byte；var x1，y1：byte；i：integer)； begin case i of ｛根据方向计算跳后位置｝ 1：begin x1←x-2；y1←y+1；end； 2：begin x1←x-1；y1←y+2；end； 3：begin x1←x+1；y1←y+2；end； 4：begin x1←x+2；y1←y+1；end； end；{case} end；{move} 2.从起始点出发，沿方向序列输出路径 设
var path：array[1..1000] of integer；{path[i]—第i步的方向。初始时path 清零} 由(1，1)至（n，m）的路径长度为k。我们通过调用print(k)过程输出该条路径。 procedure print(k：integer)； var x，y，x0，y0：byte； i：integer； begin x←1； y←1；｛从（１，１）出发｝ write(’(’，x，’，’，y，’)’)； for i←1 to k do ｛顺序输出长度为k的跳动路线｝ begin move(x，y，x0，y0，path[i])；｛第i步由（x,y）跳至（x0,y0）｝ write(’=>(’，x0，’，’，y0，’)’)； x←x0； y←y0； {从（x0,y0）继续往下跳} end；{for} writeln end；{print} 3.回溯搜索 状态：起跳位置（x，y）和步数k，即准备从（x，y）出发跳第k步； 目标：（x，y）为目的地（n，m）。若满足条件，则输出长度为k-1的路径并成功退出； 搜索范围：四个跳动方向，即1≤i≤4。中国象棋马沿i方向跳至（x1，y1）； 约束条件：（x1，y1）在界内。若满足条件，则记下第k步的方向i，并从（x1，y1）出发递归第k+1步； procedure search(k：integer；x，y：byte)； var i：integer； x1，y1：byte； begin if (x=n) and (y=m) {若（x，y）为目的地，则输出长度为k-1的路径并成功退出} then begin print(k-1)； halt； end； for i←1 to 4 do {搜索4个方向} begin move(x，y，x1，y1，i)； { 中国象棋马从（x，y）出发，沿i方向跳至（x1，y1）} if (x1 in [1..n]) and (y1 in [y+1..m]){若（x1，y1）在右方界内，则记下第k步的方向i，并从（x1，y1）出发递归第k+1步} then begin path[k]←i； search(k+1，x1，y1)；end；{then} end{for} end；{ search } 显然，递归调用search（1，1，1）后可得出由（1，1）至（n，m）的一条路径。
迷宫问题
算法设计与分析课程设计罗密欧与朱丽叶的迷宫问题设计分析测试报告 程序算法设计说明书
一、前言 1、题目：罗密欧与朱丽叶的迷宫问题。 罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计和实现一个算法帮助罗密欧找出这些道路。 2、程序编制环境相关说明 硬件：装有windows操作系统的计算机 软件：Visual C++ 2008
二、程序主要算法设计分析说明 1、算法设计思路 用回溯法解迷宫问题时，用排列树表示其解空间比较合适。可行性约束函数减去不满足约束条件（x,y,z）已越界的子树。在排列树的第i+1层节点z处用board[z][x][y]记载所在的房间。当bool stepok(int x,int y,int z)返回为false时，以z为根的子树中所有子树都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪枝。 算法调用递归方法void backtrack(int dep,int x,int y,int di)实现回溯搜索。void backtrack (int dep,int x,int y,int di)搜索排列树中第dep层子树。数组board[0][x][y]记录排列树中的节点信息。dirs记录当前节点对应的转弯数， best记录最少转弯数。 在算法void backtrack (int dep,int x,int y,int di)中，当i>n时，算法搜索至叶节点，其相应的转弯数dirs。如果dirs>best,则表示当前解优于最优解，此时更新best。当i≤n时，当前扩展节点位于是排列树的第i-1层。此时算法选择下一个要搜索的方向，以深度优先的方式递归地对相应子树进行搜。对于不满足上界约束的节点，则减去相应子树。 算法void backtrack (int dep,int x,int y,int di)动态地生成问题的解空间树。 时间复杂度为整个状态空间，即迷宫大小，O(m*n)
回溯算法实验
中原工学院信息商务学院 实验报告 实验项目名称回溯划算法的应用 课程名称算法设计与分析 学院(系、部)中原工学院信息商务学院学科专业计算机科学与技术系班级学号计科132班17号姓名程一涵 任课教师邬迎 日期2014年12月9日
实验五回溯算法的应用 一、实验目的 1．掌握回溯算法的基本概念 2．熟练掌握回溯算法解决问题的基本步骤。 3．学会利用回溯算法解决实际问题。 二．问题描述 题目一：N皇后问题 要在n*n的国际象棋棋盘中放n个皇后，使任意两个皇后都不能互相吃掉。规则：皇后能吃掉同一行、同一列、同一对角线的任意棋子。求所有的解要求：键盘输入皇后的个数n (n ≤ 13) 输出有多少种放置方法 输入输出实例：
三．算法设计 首先，确定第一行皇后的位置，再确定第二行的位置，并且要注意不能同行同列同对角线，若是发现有错则返回上一层，继续判断。满足约束条件时，则开始搜索下一个皇后的位置，直到找出问题的解。 四.程序调试及运行结果分析 五.实验总结 通过这次试验，使得我们面对问题时的解题思路变得更加灵活和多变，并且使我们的编写能力稍稍的提高一些。初步了解了回溯算法，回溯算法实际是一个类似枚举的搜索尝试方法，他的主题思想是在搜索尝试的过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径。他特别适用于求解那些涉及到寻求一组解的问题或者求满足某些约束条件的最优解的问题。此算法具有结构清晰，容易理解且可读性强等优点，并且通过稍加变通也可以适用于其他类似问题
附录：程序清单（程序过长，可附主要部分） #include 《算法分析与设计》期末复习题 一、选择题 1.算法必须具备输入、输出和（ D ）等4个特性。 A．可行性和安全性 B．确定性和易读性 C．有穷性和安全性 D．有穷性和确定性 2.算法分析中，记号O表示（ B ），记号Ω表示（ A ） A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 3.假设某算法在输入规模为n时的计算时间为T(n)=3*2^n。在某台计算机上实现并 完成概算法的时间为t秒。现有另一台计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？（ B ）解题方法：3*2^n*64=3*2^x A．n+8 B．n+6 C．n+7 D．n+5 4.设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1， T(N)=2T(N/2)+N/2，用O表示的时间复杂度为（ C ）。 A．O(logN) B．O(N) C．O(NlogN) D．O(N2logN) 5.直接或间接调用自身的算法称为（ B ）。 A．贪心算法 B．递归算法 C．迭代算法 D．回溯法 6.Fibonacci数列中，第4个和第11个数分别是（ D ）。 A．5，89 B．3，89 C．5，144 D．3，144 7.在有8个顶点的凸多边形的三角剖分中，恰有（ B ）。 A．6条弦和7个三角形 B．5条弦和6个三角形 C．6条弦和6个三角形 D．5条弦和5个三角形 8.一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A．重叠子问题 B．最优子结构性质 C．贪心选择性质 D．定义最优解 9.下列哪个问题不用贪心法求解（ C ）。 A．哈夫曼编码问题 B．单源最短路径问题 C．最大团问题 D．最小生成树问题 10.下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A．备忘录法 B．动态规划法 C．贪心法 D．回溯法 11.下列算法中不能解决0/1背包问题的是（ A ）。 A．贪心法 B．动态规划 C．回溯法 D．分支限界法 12.下列哪个问题可以用贪心算法求解（ D ）。 需要记忆的算法： -1 pascal 运算优先级 1not 2and * / div mod 3or xor + - 4 in = > < >= <= 0. 文件的输入和输出： begin assign(input,'p1.in'); reset(input); assign(output,'p1.out'); rewrite(output); for i:=1 to 20 do readln(a[i]); sum:=0; for i:=1 to 20 do sum:=sum+a[i]; writeln(sum); close(input); close(output); end. 1. 素数的判断： function ok(x:longint):boolean; var i:longint; begin for i:=2 to trunc(sqrt(x)) do if x mod i=0 then exit(false); exit(true); end; 2.选择排序 For i:=1 to n-1 do For j:=i+1 to n do If a[j]>a[i] then begin t:=a[j];a[j]:=a[i];a[i]:=t;end; 3.二进制枚举法: Fillchar(b,sizeof(b),0); while b[0]=0 do begin j:=m; \\第m位为最低位。 while b[j]=1 do dec(j); \\从最低位开始找非1 的位子； b[j]:=1; \\该位置1； for i:=j+1 to m do b[i]:=0; \\把刚才经过的1全部置0； {已经产生一种2进制数} ｛处理……｝ End; 课程设计说明书 课程名称＿＿软件专题训练＿＿＿＿ 题目罗密欧与朱丽叶迷宫求解问题＿ 院系＿电子信息工程学院计算机系＿ 班级＿计算机科学与技术103班＿＿ 学生姓名＿＿＿＿＿＿＿＿＿＿＿ 指导教师＿孙士保、冀治航＿＿ 日期＿ 2012.5.21—2012.5.27＿＿ 课程设计任务书 课程名称＿＿算法设计与分析＿＿＿ 题目＿罗密欧与朱丽叶的迷宫问题 院系＿电子信息工程学院计算机系＿ 班级＿＿＿计算机103班＿＿＿＿＿ 学生姓名＿＿＿＿魏鹏超＿＿＿＿＿＿ 指导教师＿孙士保、冀治航＿＿ 日期＿ 2012.5.21—2012.5.27＿＿ 河南科技大学 课程设计报告 课程名称＿＿软件专题训练＿＿＿＿ 题目＿罗密欧与朱丽叶的迷宫问题 院系：电子信息工程学院计算机系 专业：计算机科学与技术 班级：计算机10级 学生姓名:学号: 起止日期: 2012年5月21日~ 2012年5月27日指导教师:孙士保、冀治航 目录 第一章需求分析 (4) 1.1课程设计题目 (4) 1.2 课程设计任务及要求 (4) 1.3运行环境及开发工具 (4) 第二章概要设计 (5) 2.1系统流程图 (5) 第三章详细设计 (6) 3.1函数划分 (6) 3.2函数之间的关系 (6) 第四章系统调试与操作说明 (7) 4.1系统调试及操作说明 (7) 第五章课程设计总结体会 (8) 5.1课程设计总结 (8) 5.2致谢 (8) 5.3参考文献 (8) 第一章需求分析 1.1课程设计题目 罗密欧与朱丽叶的迷宫问题 1.2 课程设计任务及要求 1、对于给定的罗密欧与朱丽叶的迷宫，编程计算罗密欧通向朱丽 叶的所有最少转弯道路 2、程序能够演示一条罗密欧找到朱丽叶的路线过程等 罗密欧与朱丽叶的迷宫。罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条路。 1.3运行环境及开发工具 硬件：装有windows操作系统的计算机 软件：Visual C++6.0 NOIP复赛谈 复赛的命题 1．遵循大纲：考察常用的数据结构和基本算法； 2．考察能力：包括阅读理解能力、构建数学模型的能力、程序编码与调试能力、程序的时空性能分析和测试数据的生成能力、各种知识的综合应用能力等； 3．有区分度：一般4题，复赛题目的特点是：1-2题算法和数据结构比较明显、或者和数学关系比较大的题目，得率比较高；1题好上手，但程序量要大一点或数据规 模大的题目，考虑全面、得满分也不容易；还有1题一般是搜索、或者算法不明显、或者用到复杂高深一点的数据结构的题目，难度较大。但顺序不一定！！！ 如何备战复赛 1.做做以往历年的竞赛题和网上的模拟题，熟悉比赛的题型和要求，找出自己的不 足，加强训练； 2.增强自己编写代码和调试的熟练程度，提高做题的时间和节奏感； 3.熟练掌握文件的输入/输出操作，熟悉新大纲中对复赛的要求； 4.提高自己设计测试数据的能力； 5.提高自己做题的正确率（分数/时间）； 6.算法方面：递推、递归、动态规划、贪心、搜索（初中到回溯就差不多了）基本 上是必考！！！对一些经典问题和算法，一定要熟练的不能再熟练； 7.数据结构方面：字符串经常考，树（尤其二叉树）、图的基本算法（最短路径、最 小生成树等）； 复赛注意事项 1.认真审题，尤其要注意问题的规模（数据范围），从某种意义上说，问题规模也 暗示了你可能的算法。数据小，也许是搜索派上用场的时候；数据大了，可能 只能考虑动态规划、数学方法等高算法了。 2.正确的估计题目的难度和自己的水平。拿到试题后先从总体上分析一下题目， 做到心中有数！注意：题目的难易对所有人是公平的，只要最大限度地发挥自 己的水平，不要有包袱，考出自己的最佳成绩。 3.正确地选择题目去做（最擅长、最简单的先完成），合理地安排时间和解题顺序。 4.复赛中：一定提高正确率！！！解题速度是其次。 5.复赛考查的算法并不困难，选手在实现上的问题往往要多一些。建议大家： 1）充分利用草稿纸，不要对自己的“心算能力”太自信！编程熟练的同学喜欢“一气呵成”，拿到题目就开始编码。这样不好，做信息学竞赛题的思维过程是丰 富而曲折多变的，考虑问题必须全面，仅凭一时的“感觉”来编程往往是漏洞 回溯算法实例一 【问题】填字游戏 问题描述：在3×3个方格的方阵中要填入数字1到N（N≥10）内的某9个数字，每个方格填一个整数，使得所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。 可用试探发找到问题的解，即从第一个方格开始，为当前方格寻找一个合理的整数填入，并在当前位置正确填入后，为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填证书，就要回退到前一方格，调整前一方格的填入数。当第九个方格也填入合理的整数后，就找到了一个解，将该解输出，并调整第九个的填入的整数，寻找下一个解。 为找到一个满足要求的9个数的填法，从还未填一个数开始，按某种顺序（如从小到大的顺序）每次在当前位置填入一个整数，然后检查当前填入的整数是否能满足要求。在满足要求的情况下，继续用同样的方法为下一方格填入整数。如果最近填入的整数不能满足要求，就改变填入的整数。如对当前方格试尽所有可能的整数，都不能满足要求，就得回退到前一方格，并调整前一方格填入的整数。如此重复执行扩展、检查或调整、检查，直到找到一个满足问题要求的解，将解输出。 回溯法找一个解的算法： { int m=0,ok=1; int n=8; do{ if (ok) 扩展; else 调整; ok=检查前m个整数填放的合理性; } while ((!ok||m!=n)&&(m!=0)) if (m!=0) 输出解; else 输出无解报告； } 如果程序要找全部解，则在将找到的解输出后，应继续调整最后位置上填放的整数，试图去找下一个解。相应的算法如下： 回溯法找全部解的算法： { int m=0,ok=1; int n=8; do{ if (ok) { if (m==n) { 输出解； 调整； } else 扩展; } else 调整; ok=检查前m个整数填放的合理性; } while (m!=0); 内部资料，转载请注明出处，谢谢合作。 一。选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、在下列算法中有时找不到问题解的是（ B ）。 A、蒙特卡罗算法 B、拉斯维加斯算法 C、舍伍德算法 D、数值概率算法 5. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树6．下列算法中通常以自底向上的方式求解最优解的是（ B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 7、衡量一个算法好坏的标准是（C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 8、以下不可以使用分治法求解的是（D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 9. 实现循环赛日程表利用的算法是（ A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 10、下列随机算法中运行时有时候成功有时候失败的是（C ） A 数值概率算法 B 舍伍德算法 C 拉斯维加斯算法 D 蒙特卡罗算法 11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 例1、骑士游历：（noip1997tg） 设有一个n*m的棋盘(2<=n<=50,2<=m<=50),如下图,在棋盘上任一点有一个中国象棋马,马走的规则为：1.马走日字 2.马只能向右走，即如下图所示： 任务1：当N,M 输入之后,找出一条从左下角到右上角的路径。 例如：输入N=4,M=4 输出：路径的格式：(1,1)->(2,3)->(4,4)；若不存在路径,则输出"no" 任务2：当N,M 给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目。 例如：(N=10,M=10),(1,5)(起点),(3,5)(终点) 输出：2(即由(1,5)到(3,5)共有2条路径) 输入格式：n,m,x1,y1,x2,y2(分别表示n,m,起点坐标,终点坐标) 输出格式：路径数目(若不存在从起点到终点的路径,输出0) 算法分析：为了研究的方便，我们先将棋盘的横坐标规定为i，纵坐标规定为j，对于一个n×m的棋盘，i的值从1到n，j的值从1到m。棋盘上的任意点都可以用坐标(i,j)表示。对于马的移动方法，我们用K来表示四种移动方向(1,2,3,4)；而每种移动方法用偏移值来表示，并将这些偏移值分别保存在数组dx和dy中，如下表 根据马走的规则，马可以由（i-dx[k],j-dy[k]）走到(i,j)。只要马能从（1，1）走到（i-dx[k],j-dy[k]），就一定能走到（i,j）,马走的坐标必须保证在棋盘上。我们以（n,m）为起点向左递推，当递推到（i-dx[k],j-dy[k]）的位置是（1，1）时，就找到了一条从（1，1）到（n,m）的路径。 我们用一个二维数组a表示棋盘，对于任务一，使用倒推法，从终点(n,m)往左递推，设初始值a[n,m]为（-1，-1），如果从(i,j)一步能走到(n,m)，就将(n,m)存放在a[i,j]中。如下表，a[3,2]和a[2,3]的值是（4，4），表示从这两个点都可以到达坐标（4,4）。从（1,1）可到达（2，3）、（3，2）两个点，所以a[1,1]存放两个点中的任意一个即可。递推结束以后，如果a[1,1] 任务一的源程序： const dx：array[1..4]of integer=(2,2,1,1); dy：array[1..4]of integer=(1,-1,2,-2); type map=record x,y：integer; end; 算法分析与设计论文论文题目：回溯法解迷宫问题 作者姓名陈相艺 任课教师王松 学院班级计算机学院计自1101班 学号201126100404 提交日期2013年6月10日 回溯法解迷宫问题 陈相艺 （计算机+自动化1101 201126100404） 摘要：迷宫的存储结构以二维数组来存储，用0，1表示通或不通。表面上似乎迷宫问题是一种特殊问题的解决方法，其实迷宫问题是一种特殊形式图的问题，因此，迷宫总量可转化为图的问题来解决。设计一个计算机程序对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论.本文采用回溯法求解迷宫路径，算法用到数据结构中的栈。 关键词：迷宫；二位数组；回溯法；栈；矩阵。 1.前言 迷宫实验是取自心理学的一个古典实验.在该实验中,把一只老鼠从一个无顶大盒子放入,在盒中设立了许多墙,对行进方向形成了多处阻挡.盒子仅有一个出口处放置一快奶酪,吸引老鼠在迷宫中寻找道路以到达出口.对同一老鼠重复进行上述实验,一直到老鼠从入口到出口,而不走错一步.老鼠经多次试验终于得到它学习走通迷宫的线路.设计一个计算机程序对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论. 回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 2.迷宫问题的算法思想及研究 迷宫问题中，在寻找路径时，采用的方法通常是：从入口出发，沿某一方向向前试探，若能走通，则继续向前进；如果走不通，则要沿原路返回，换一个方向再继续试探，直到所有可能的能跟都试探完成为止。为了保证在任何位置上都能沿原路返回（回溯），要建立一个后进先出的栈来保存从入口到当前位置的路径。而且在求解迷宫路径中，所求得的路径必须是简单路径。即在求得的路径上不能有重复的同一块通道。 为了表示迷宫，设置一个数组，其中每个元素表示一个方块的状态，为0时表示对应方块是通道，为1时表示对应方块为墙，数组如下所示： int mg[10][10] = { {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,1,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}}; （可根据自己喜好，改变迷宫的大小和通道安排。） 对于迷宫中每个方块，都有上下左右四个方块相邻，第i行第j列的当前方块的位置为(i,j)，最新《算法分析与设计》期末考试复习题纲(完整版)
需要记忆的算法(new)
罗密欧与朱丽叶迷宫求解问题
NOIP复赛谈
回溯算法实例一培训讲学
算法分析复习题目及答案
递推例题
回溯法解迷宫问题