基于贪心算法的马踏棋盘哈密顿回路问题


问题分析

马踏棋盘其实相当于一个解空间的搜索问题，而遍历到每一个节点并要求最后可以回到起点本质上是一个哈密顿回路问题

目前大部分马踏棋盘的相关问题并不要求回到起点，然后实际上在不重复的走完全盘的可行解中寻找最后可以回到起点的最优解更为困难。

问题在于，这个搜索空间十分的庞大，倘若不考虑棋盘位置约束与遍历次数限制，解空间大小将达到指数级的庞大规模。但是即便在这些解中加上棋盘限制与单次访问等的剪枝条件，为了在可行解（64 个节点仅各访问一次）中搜寻到可以回到起点的最优解仍然是非常困难的。倘若仅仅固定八个可行方向的顺序，使用深度优先的递归来实施搜索，效率将会非常低下。

这是因为对于靠近边界的四个顶点的区域来说，如果不能尽快的遍历完这些区域，而是按照固定的顺序来遍历会十分容易造成“死节点”，将来不可能再次访问。而与此同时，程序还在徒劳的往更深的方向搜索，极大的影响搜索效率。

贪心算法的改进

为了尽量较快的遍历完一个边界区域，我们应当尽量“靠边走”。故而有以下的贪心策略。再对八个方向进行顺序的考虑时，优先选取拥有较少可行孙节点的子节点方向（边界区域）,并给每一个方向一个权值由于方向的排序。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void  sort_direction(int x, int y) {
	int x_new, y_new, xx_new, yy_new;
	int score[Row] = { Row,Row,Row,Row,Row,Row,Row,Row}; // 定义不同方向的得分权值
	for (int i = 0; i < Row; i++) {
		int count = 0;
		x_new = x + deta_x[i];
		y_new = y + deta_y[i];
		if (check(x_new, y_new) == 1) {       // 检查点a[xx][yy]是否满足条件
			for (int j = 0; j < Columns; j++) {
				xx_new = x_new + deta_x[j];
				yy_new = y_new + deta_y[j];
				if (check(xx_new, yy_new) == 1) // 检查点a[xx][yy]是否满足条件
					count++;
			}
		}
		score[i] = count;
	}
	sort_index(score, sorted, Row);              // 快速排序
}

基于此思想再结合深度优先的递归算法基本可以秒出（ 0.02s 以内）绝大多数点（除去四个边界顶点与 (8,7) 这个点）的哈密顿回路。

42 33 26 9 62 13 28 11
25 8 41 58 27 10 63 14
34 43 32 61 40 59 12 29
7 24 57 50 31 64 15 52
44 35 46 39 60 51 30 1
23 6 49 56 47 18 53 16
36 45 4 21 38 55 2 19
5 22 37 48 3 20 17 54

完整代码见文末

边界顶点的优化

即便基于以上贪心算法改进后，边界上的四个顶点仍然较难求出最优解。归其本质为边界顶点有且仅有两个节点联通，故而若唯一的回路在中间递归过程被占用的话便永远也回不到起点。故而优化方式便是强行定义一个规则: 让唯一的回路关键节点最后一次访问

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
if (x_0 == 1 && y_0 == 1) {
		if (deep <= Total_step - 1)
			qipan[2][1] = 1;
		else 		qipan[2][1] = 0;
	}
	if (x_0 == 1 && y_0 == Columns) {
		if (deep <= Total_step - 1)
			qipan[2][Columns-2] = 1;
		else  qipan[2][Columns - 2] = 0;
	}
	if (x_0 == Row && y_0 == Columns) {
		if (deep <= Total_step - 1)
			qipan[Row-3][Columns - 2] = 1;
		else  qipan[Row - 3][Columns - 2] = 0;
	}
	if (x_0 == Row && y_0 == 1) {
		if (deep <= Total_step - 1)
			qipan[Row - 2][2] = 1;
		else  qipan[Row - 2][ 2] = 0;
	}

加上以上改进后四个节点的一条哈密顿解亦可秒出

这里写图片描述

上图便是各个顶点不重复的走完全盘但是没有回到起点的次数、可以看出边界区域上的回溯次数明显大于中心区域的点。特别的，(8,7) 这个点的回溯次数更是高达 5000 多，但是从理论上棋盘应该是对称的。

显然这个回溯次数极高的情况应该是本代码的一个bug, 希望读者可以帮忙指正，未完待续~

完整代码

新手程序写的很冗长，大佬勿喷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<stdio.h>
#include<stdlib.h>

# define Total_step 64  // 马的总步数
# define Row     8      // 棋盘的行数
# define Columns 8      // 棋盘的列数
# define Drections 8    // 每一步的八个方向
# define x_0 2          // 初始位置横坐标
# define y_0 4          // 初始位置纵坐标
# define jilu 1

const int* par = 0;     // 用于排序的常量
int times = 0;          // 记录走完全盘的次数
int deta_x[Row] =     { 1,2,2,1,-1,-2,-2,-1 };
int deta_y[Columns] = { 2,1,-1,-2,-2,-1,1,2 };           // 八个方向，优先顺序将极大的影响遍历效果
int sorted[Row] = { 0,1,2,3,4,5,6,7 };                   // 基于贪心算法对上述八个顺序进行动态调整的排序索引
int qipan[Row][Columns];                                 // 二维数组棋盘
void print_result();                                     // 打印棋盘的函数
int  check(int x_new, int y_new);                        // 对马的下一步进行检验，是否在棋盘内并且未被遍历过
int  Find(int x, int y, int deep);                       // 主递归函数
void sort_direction(int x, int y);                       // 对八个方向进行排序的函数
int  compare(const void* p1, const void* p2);            // 快速排序的比较函数
void sort_index(const int ar[], int index[], int num);   // 依据sort_direction 得到的方向权值给索引排序的函数

int main() {
	// 初始化棋盘
	for (int i = 0; i < Row; i++)
		for (int j = 0; j < Columns; j++)
			qipan[i][j] = 0;
	// 输出终端界面
	printf("-----------------------------------------------------\n");
	printf("--------------------马踏棋盘问题---------------------\n");
	printf("----------------------------------------------\n\n");
	// 初始化起点
	qipan[x_0 - 1][y_0 - 1] = 1;
	// 是否找到路径
	if (Find(x_0 - 1, y_0 - 1, 2) == 1)
		printf("\n递归成功!\n");
	else
		printf("\n递归失败!\n");
	getchar();
	return 1;
}
// print()函数进行输出结果
void print_result()
{
	printf("\n");
	int i, j;
	for (i = 0; i < Row; i++) {
		for (j = 0; j < Columns; j++)
			printf("%3d", qipan[i][j]);
		printf("\n");
	}
}
// Check()函数检查新产生的点是否满足条件，满足则返回1.
int check(int x_new, int y_new)
{
	if (x_new >= 0 && x_new < Row && y_new >= 0 && y_new < Columns && qipan[x_new][y_new] == 0)
		return 1;
	return 0;
}
// deep为递归的深度,当深度达到 Total_step=64 时表示遍历结束
int Find(int x, int y, int deep)
{
	if (x_0 == 1 && y_0 == 1) {
		if (deep <= Total_step - 1)
			qipan[2][1] = 1;
		else 		qipan[2][1] = 0;
	}
	if (x_0 == 1 && y_0 == Columns) {
		if (deep <= Total_step - 1)
			qipan[2][Columns-2] = 1;
		else  qipan[2][Columns - 2] = 0;
	}
	if (x_0 == Row && y_0 == Columns) {
		if (deep <= Total_step - 1)
			qipan[Row-3][Columns - 2] = 1;
		else  qipan[Row - 3][Columns - 2] = 0;
	}
	if (x_0 == Row && y_0 == 1) {
		if (deep <= Total_step - 1)
			qipan[Row - 2][2] = 1;
		else  qipan[Row - 2][ 2] = 0;
	}
	int i, x_new, y_new;
	sort_direction(x, y);                   // 对八个方向进行排序
	for (i = 0; i < Drections; i++) {
		x_new = x + deta_x[sorted[i]];      // 按照排序后的方向进行搜索
		y_new = y + deta_y[sorted[i]];
		int detax = abs(x_new - x_0 + 1);
		int detay = abs(y_new - y_0 + 1);
		if (check(x_new, y_new) == 1)       // 检查点a[xx][yy]是否满足条件
		{
			qipan[x_new][y_new] = deep;
			if (jilu == 1) {
			if (deep == Total_step)         // 用于记录找到最优解经历了多少次达到深度最大值的回溯次数
				printf("第%3d 次走完全盘\n", ++times);
			}
			// 最优解终止条件
			if (deep >= Total_step && (detax*detax + detay*detay == 5)) {
				print_result();
				return 1;
			}
			if (Find(x_new, y_new, deep + 1) == 1)  // 如果返回的是1，表示遍历完成。
				return 1;
			else                                    // 如果返回的不是1，表示遍历未完成，继续搜索。
				qipan[x_new][y_new] = 0;            // 一定要通过此步骤将棋盘还原
		}
	}
	return 0;
}
// 对八个方向排序
void  sort_direction(int x, int y) {
	int x_new, y_new, xx_new, yy_new;
	int score[Row] = { Row,Row,Row,Row,Row,Row,Row,Row};           // 定义不同方向的得分权值
	for (int i = 0; i < Row; i++) {
		int count = 0;
		x_new = x + deta_x[i];
		y_new = y + deta_y[i];
		if (check(x_new, y_new) == 1) {           // 检查点a[xx][yy]是否满足条件
			for (int j = 0; j < Columns; j++) {
				xx_new = x_new + deta_x[j];
				yy_new = y_new + deta_y[j];
				if (check(xx_new, yy_new) == 1)   // 检查点a[xx][yy]是否满足条件
					count++;
			}
		}
		score[i] = count;
	}
	sort_index(score, sorted, Row);                 // 快速排序
}
int compare(const void* p1, const void* p2)
{
	int a = *(int*)p1;
	int b = *(int*)p2;
	if (par[a] > par[b])
		return 1;
	else if (par[a] == par[b])
		return 0;
	else
		return -1;
}

void sort_index(const int ar[], int index[], int num)
{
	par = ar;
	qsort(index, num, sizeof(int), &compare);
}

扫一扫，分享到微信

微信分享二维码