N皇后问题

2017/9/20镜像同步4 回复

帮同学写个作业，题目是类似N皇后问题，不同的是地图上可能会出现“大树”，使得本来冲突的两个皇后可以不冲突，比如这样 1 0 0 0 2 0 0 0 1 其中1是皇后，2是大树。要求通过DFS、BFS和模拟退火分别实现。目前三种我都写好了，在没树的情况下退火可以跑35*35 DFS我用了回溯，可以跑15*15 BFS由于大量复制状态信息到队列里，只能跑到10*10，跑了一下profile基本都浪费在复制状态上了求解一般这种情况下BFS应该如何优化？使用vector<vector<bool>>代替vector<string>的话，需要每次枚举状态进入队列时，都要判断当前位置是否可以放一个“皇后”，但是复制状态的速度会明显提高（个人认为），而用后者可以在放“皇后”的时候直接将受影响的位置标记，省去判断的时间，目前这么改需要改动的地方比较多，暂时还没做。除了这种办法，还有没有其他常见的优化BFS的办法？

订阅后，新回复会通过你的通知中心匿名送达。

4 条回复

chenxiansf机器人#1 · 2017/9/21

std::move?

caesar11机器人#2 · 2017/9/21

中间状态只需要存N个坐标就可以了，为什么要存个二维数组？

Nroskill机器人#3 · 2017/9/21

不行，queue<T>.push就会拷贝一份，这个操作就很耗时了，不能move 【在 chenxiansf 的大作中提到: 】 : std::move?

Nroskill机器人#4 · 2017/9/21

改了存坐标，跑了profile之后发现时间耗在reallocate和push_back上了，于是预先分配空间，时间上有了小进步，但是还是跑不了11*11，10*10就要20秒左右，除了拷贝坐标集之外，查找有效点的时间也上来了（因为没有存地图）。【在 caesar11 的大作中提到: 】 : 中间状态只需要存N个坐标就可以了，为什么要存个二维数组？