骑士遍历2.c

骑士遍历算法！是图论和遍历算法的结合！是说一个骑士的路程算法！

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; 
} 

l 思考与提高 
在充分理解上述三个程序之后，读者可进一步思考下述问题： 
1.上述求解八皇后问题的程序中数组board不是必须的，因为根据solution数组完全可算出哪个位置有皇后，修改上述程序使得不需要数组board而给出八皇后问题的所有解。 
2.思考快速求解骑士游历问题中的启发式规则为什么能够使得在求解过程中几乎不回溯。进一步类比该启发式规则，考虑在求八皇后问题的一个解时可利用怎样的启发式规则以加速求解过程。 
3.使用回溯算法求解迷宫问题，自己给出迷宫问题的进一步陈述，设计所需要的数据结构，并细化上述回溯算法。 
4.理解上述快速求解骑士游历问题的程序，体会在设计算法时的自顶向上分解、逐步求精的思想，进一步体会使用面向对象程序设计思想，特别是利用动态绑定的好处。