代码语言
.
CSharp
.
JS
Java
Asp.Net
C
MSSQL
PHP
Css
PLSQL
Python
Shell
EBS
ASP
Perl
ObjC
VB.Net
VBS
MYSQL
GO
Delphi
AS
DB2
Domino
Rails
ActionScript
Scala
代码分类
文件
系统
字符串
数据库
网络相关
图形/GUI
多媒体
算法
游戏
Jquery
Extjs
Android
HTML5
菜单
网页交互
WinForm
控件
企业应用
安全与加密
脚本/批处理
开放平台
其它
【
C
】
骑士游历问题(回溯法)
作者:
Dezai.CN
/ 发布于
2013/6/20
/
503
// 文件:KNIGHT.CPP // 功能:使用回溯算法求解骑士游历问题 #include <iostream.h> #include <iomanip.h> 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; }
试试其它关键字
骑士游历
同语言下
.
获取手机通讯录 iOS去除数字以外的所有字符
.
异步加载音乐等资源
.
交通罚单管理系统
.
freemark实现,简单的替换
.
计算斐波那契数列
.
base64解码 包括解码长度
.
图像显示
.
冒泡排序
.
输入十进制数,输出指定进制
.
链式栈
可能有用的
.
C#实现的html内容截取
.
List 切割成几份 工具类
.
SQL查询 多列合并成一行用逗号隔开
.
一行一行读取txt的内容
.
C#动态修改文件夹名称(FSO实现,不移动文件)
.
c# 移动文件或文件夹
.
c#图片添加水印
.
Java PDF转换成图片并输出给前台展示
.
网站后台修改图片尺寸代码
.
处理大图片在缩略图时的展示
Dezai.CN
贡献的其它代码
(
4037
)
.
多线程Socket服务器模块
.
生成随机密码
.
清除浮动样式
.
弹出窗口居中
.
抓取url的函数
.
使用base HTTP验证
.
div模拟iframe嵌入效果
.
通过header转向的方法
.
Session操作类
.
执行sqlite输入插入操作后获得自动编号的ID
Copyright © 2004 - 2024 dezai.cn. All Rights Reserved
站长博客
粤ICP备13059550号-3