Sicily1153 解题报告

一.原题中文大意。

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

在这样的8x8的棋盘上任选一个起点,然后模仿象棋里面马的移动规则,只能走“日”字。如果在一个起点开始,走完63步之后能够遍历完,除了起点的其余63个点得话,这次马的周游算成功,然后输出这次周游的路径,就是按马经过的顺序将这64个点输出为一行。

二.算法思想及解题用到的主要数据结构

算法思想与1152另外一道5x5的马的周游问题基本相同,用的是回溯算法的思想,从第一步开始,每次枚举下一步可以移动的位置,然后按一定的顺序选择下一个位置,然后在下一个位置同样递归这个步骤,直到遍历棋盘上的所有的点,该次周游成功,输出路径;或者还没有遍历所有的点就无路可走了,该次周游失敗,不输出任何信息。

其实就是简单的深度优先搜索,尽快找到一条满足条件的路径就算完成任务了。与深度优先搜索匹配的数据结构是栈,根据栈先进后出的特性,可以很好地模拟路径回溯搜索的过程。所以用到了一个有64个元素的一维数组记录路径,再用一个长度为64的一维数组记录每个节点的状态,还有两个长度为8的一位数组用于成对存储一个节点的8个相邻位置。不过由于这道题数据量较大,如果每一次都同等地遍历8个邻接位置会超时,所以要用启发式剪枝,记忆搜索。对每个位置的邻接位置按邻接位的个数进行排序,邻接位的个数越少的位置优先级越高,先走那个最没前途的点,这样会更快,因为它这么没前途,要从其它点到达它就更难了,所以先走。

三.详细解题思路

(1)   输入一个源点,计算出源点的横坐标和纵坐标,然后在一个8x8的棋盘(二维数组)上进行深度优先搜索。

(2)   初始化路径数组和状态数组,首先把源点添加到路径数组(栈)并把源点的状态标识为已经遍历过。

(3)   进入到启发式的深度优先搜索,先把源点当做搜索的起点。计算起点的可走邻接点,然后将这些邻接点进行排序,遍历邻接点数目最少的点。把该点添加到路径数组(栈)并把该点的状态标识为已经遍历过。

(4)   以这个点作为起点重复第(3)步,直到找到一条满足条件的周游路径。

四.逐步求精算法描述

1. 五个个全局变量数组:

int moveX[8] = {1, 2, 2, 1, -1, -2, -2, -1};

int moveY[8] = {2, 1, -1, -2, -2, -1, 1, 2};

//  以逆时针方向记录下一步可能的8各方向

bool isVisited[64];

//  布尔数组记录每个节点的状态,是否已经遍历过了

int path[64];

//记录具体经过节点的路径

point adjacent[8];

//存储每个节点的可走邻接点

  2. 存储节点的数据结构:

//节点有2个属性:节点的横坐标、纵坐标

typedef struct

{

    int x;

    int y;

}point;

3. 计算并存储当前节点可以走到得邻接节点数组还有数目:

      int addNextPosition(point aPoint)

int countNextPosition(point aPoint)

4. 进行启发式搜索时用到的评价函数:

bool compare(point left, point right)

5. 进行启发式深度优先搜索:

void dfs(point startPoint)

五.程序注释清单

 

  1 //
  2 //  main.cpp
  3 //  Sicily-1153 回溯算法 启发式剪枝
  4 //
  5 //  Created by ashley on 14-10-21.
  6 //  Copyright (c) 2014年 ashley. All rights reserved.
  7 //
  8 
  9 #include <iostream>
 10 #include <utility>
 11 #include <algorithm>
 12 using namespace std;
 13 
 14 //用两个长度为8的一维数组来记录当前节点到其8个邻接点的坐标变换
 15 int moveX[8] = {1, 2, 2, 1, -1, -2, -2, -1};
 16 int moveY[8] = {2, 1, -1, -2, -2, -1, 1, 2};
 17 //布尔数组记录每个节点的状态,是否已经遍历过了
 18 bool isVisited[64];
 19 //记录具体路径
 20 int path[64];
 21 int counter;
 22 bool success;
 23 //用来存储每个节点的横坐标和纵坐标
 24 typedef struct
 25 {
 26     int x;
 27     int y;
 28 }point;
 29 //存储每个节点的可走邻接点
 30 point adjacent[8];
 31 
 32 //计算每个节点的可走邻接点
 33 int addNextPosition(point aPoint)
 34 {
 35     int sum = 0;
 36     for (int i = 0; i < 8; i++) {
 37         point newPoint = {aPoint.x + moveX[i], aPoint.y + moveY[i]};
 38         int number = newPoint.y * 8 + newPoint.x + 1;
 39         
 40         if (newPoint.x < 8 && newPoint.x >= 0 && newPoint.y < 8 && newPoint.y >= 0 && isVisited[number - 1] == false) {
 41             adjacent[sum++] = newPoint;
 42         }
 43     }
 44     return sum;
 45 }
 46 
 47 //计算一个节点可走邻接点的数目
 48 int countNextPosition(point aPoint)
 49 {
 50     int sum = 0;
 51     for (int i = 0; i < 8; i++) {
 52         point newPoint = {aPoint.x + moveX[i], aPoint.y + moveY[i]};
 53         int number = newPoint.y * 8 + newPoint.x + 1;
 54         if (newPoint.x < 8 && newPoint.x >= 0 && newPoint.y < 8 && newPoint.y >= 0 && isVisited[number - 1] == false) {
 55             sum++;
 56         }
 57     }
 58     return sum;
 59 }
 60 
 61 //对邻接点节点按优先级排序的时候用到的比较函数,可走邻接点数越少的节点优先级越高
 62 bool compare(point left, point right)
 63 {
 64     return countNextPosition(left) < countNextPosition(right);
 65 }
 66 
 67 //启发式深度优先搜索
 68 void dfs(point startPoint)
 69 {
 70     if (counter == 64) {
 71         success = true;
 72         cout << path[0];
 73         for (int i = 1; i < 64; i++) {
 74             cout << " " << path[i];
 75         }
 76         cout << endl;
 77         return;
 78     }
 79     int key = addNextPosition(startPoint);
 80     //将邻接点排序
 81     sort(adjacent, adjacent + key, compare);
 82     for (int i = 0; i < key; i++) {
 83         point choicePoint = adjacent[i];
 84         int num = choicePoint.y * 8 + choicePoint.x + 1;
 85         isVisited[num - 1] = true;
 86         path[counter] = num;
 87         counter++;
 88         //判断搜索是否成功
 89         if (success) {
 90             return;
 91         }
 92         dfs(choicePoint);
 93         //回溯
 94         isVisited[num - 1] = false;
 95         counter--;
 96     }
 97 }
 98 int main(int argc, const char * argv[])
 99 {
100     int source;
101     while (cin >> source) {
102         if (source == -1) {
103             break;
104         }
105         //计算源点的横坐标和纵坐标
106         point sourcePoint = {(source - 1) % 8, (source - 1) / 8};
107         for (int i = 0; i < 64; i++) {
108             isVisited[i] = false;
109         }
110         success = false;
         counter = 1;
112         //源点只能走一次
113         isVisited[source - 1] = true;
114         path[counter - 1] = source;
115         dfs(sourcePoint);
116     }
117     return 0;
118 }

 

六.测试数据(5-10组有梯度的测试数据,要考虑边界条件)

  A. 一般数据

(1)10

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

(2)26

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

    (3)27

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

    (4)38

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

  边界数据

    (5)25

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

    (6)32

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

    (7)1

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

    (8)8

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

    (9)64

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

 

七.对时间复杂度,空间复杂度方面的分析、估算及程序优化的分析和改进

 一般的深度优先的时间复杂度是O(n2)。如果在进行深度优先搜索的时候,不优先搜索子节点较少的节点,会大大增加时间和空间的复杂度,甚至无法通过sicily的测试。所以,要选择启发式的深度优先算法,并设定评价函数,由于邻接点数目越少的节点可以走到终点的可能性越小,所以搜索路径的时候应该优先考虑邻接点少的节点,所以节点的邻接点数目越少优先级越高。这样会大大减少犯错的机会,也就会减少时间复杂度。深度优先算法和启发式深度优先算法的空间复杂度都是O(n),还是可以接受的。 

更多相关文章
  • 题意和解决回路匹配的思路如同hdu3488 (这里我第一次想到最短路,但是对于有回路这个不知道怎么处理,后来看了别人的解题报告才知道KM匹配,但是看到KM之后就自己想...想了很久....还是不知道回路这个地方怎么匹配......其实应该这样来想....总共有N个城市....如果是要形成回路..那么 ...
  • http://poj.org/problem?id=1173 发现此题资料甚少,斗胆第一次写一份解题报告[题意]     输入 n(代表二进制位数) k(代表黑条白条总共有几条,条形码是以黑条开始的,再白黑交替出现) m(代表每条最多占多少个二进制位)     输出这种模式的条形码的有多少个?    ...
  • 题目大意:使用两个哈希表来解决哈希冲突的问题.假如现在有两个哈希表分别为:H1,H2 ,大小分别为:n1,n2:现有一数据X需要插入,其插入方法为: 1.计算index1 = X MOD N1,  若哈希表H1的index1位置没有保存数据,则直接将X保存到H1得index1:否则,若哈希表H1的i ...
  • 题目大意:输入一个偶数(x<32),输出这个偶数是由哪两个素数相加所得. 比如:一个偶数26,它可以是3+23,7+19,13+13,这些素数相加所得. 输入输出样例: Sample Input 3 4 26 100 Sample Output 4 has 1 representation(s ...
  • 本题大意: 用天平对一物品进行称重,现有重量不同的砝码,砝码的重量分别为:1,3,9,27,..,3^n.(n<20) 天平的右侧放砝码,左侧放物品或物品和砝码,使得左右两边的重量相等. 现有一个物品,计算左右两边应当分别放多少个多大的砝码才能使得天平平衡. 例如:现在有一个重量为21的物品, ...
  • 好几年没有做ACM了,感觉忘得差不多了,这个做着做着就打瞌睡了!言归正传,下面是我的解题思路: 首先的话,我们可以画一个函数图,以输入数组的下标为X轴,以数组的和为Y轴,当数组和小于零时,我们使用备用的数组和sum2和备用的最小下标min2,并用flag进行标记.具体实现可以参考代码. 需要注意的地 ...
  • //我是莱鸟,多多交流 //380k //94ms 题目的意思是:每种装备可由多个生产商提供,从每一种装备中选择一个厂家的设备,使得所选的总的各种装备中的最小带宽B与他们的价格之和P的比值B/P达到最大. 解题思路: 准备工作:在输入时,统计所有装备中的最小值min,和每种装备中的最大值max,然后 ...
  • Spring1F Dice(HDU 5012)解题报告及测试数据
    Dice Time Limit:1MS     Memory Limit:65536KB Description There are 2 special dices on the table. On each face of the dice, a distinct number was writt ...
一周排行