| Blog信息 |
|
blog名称:
日志总数:1304
评论数量:2242
留言数量:5
访问次数:7588693
建立时间:2006年5月29日 |
| |
|
 [算法]用STL实现先深搜索及先宽搜索——数独(sudoku)例子(2)
软件技术, 电脑与网络
lhwork 发表于 2006/5/31 15:38:29 |
| 用STL实现先深搜索及先宽搜索
——数独(sudoku)例子(2)
前面我们用一个游戏——数独sudoku，实作出了一个简单（但效率较差）的解法，验证了我们的DFS和BFS算法。为简单起见，我们采用了最简单的解法而暂不考虑效率。这里，我们尝试改进一下数独问题解法的效率，并将新的解法与原来的解法进行一个效率的对比。
从DFS/BFS算法中可以看出，搜索算法的执行效率主要取决于问题状态空间树的大小，如果状态空间树每层的分支较少，则树的结点也会较少，这样搜索就可以更快结束。所以，我的基本想法就是，尽量减少状态空间树中每层的分支数目。
具体到数独游戏，我们原来的解法是：在二维数组中扫描到第一个未填数字的空格，就以这个空格为基础来生成下一层状态结点分支，而根本没有考虑过这个空格是否最佳的生成点。这样自然会导致状态空间树的最高几层分支过多，结点数有可能急速增加，从而增长了搜索时间。
我的想法是，不要找到一个空格就立即用于生成下一层状态结点，而是对目前状态中的所有空格都计算出其可能的分支数目，然后以分支数目最少的一个空格为生成点来生成下一层状态结点。这样，状态空间树的最高几层的分支就会相对较少，从而降低搜索的时间。
显然，这只需要对原来的SudokuState::nextStep()成员函数进行改写即可，如下：
void SudokuState::nextStep(vector<SudokuState>& vs) const
{
SudokuState newState;
bool pos[SUDOKU_DIMS], bestPos[SUDOKU_DIMS];
int best = SUDOKU_DIMS+1, bestRow, bestCol;
for (int row = 0; row < SUDOKU_DIMS; ++row)
{
for (int col = 0; col < SUDOKU_DIMS; ++col)
{
if (data_[row][col] == 0) // Space
{
fill_n(pos, SUDOKU_DIMS, true);
for (int k = 0; k < SUDOKU_DIMS; ++k)
{
checkValue(pos, data_[k][col]);
checkValue(pos, data_[row][k]);
}
int rs = row - (row % SUDOKU_ROWS);
int cs = col - (col % SUDOKU_COLS);
for (int i = 0; i < SUDOKU_ROWS; ++i)
{
for (int j = 0; j < SUDOKU_COLS; ++j)
{
checkValue(pos, data_[rs+i][cs+j]);
}
}
int s = count(pos, pos+SUDOKU_DIMS, true);
if (s == 0) // 如果有一个空格没有可以填的值
{
return;
}
if (best > s)
{
best = s;
copy(pos, pos+SUDOKU_DIMS, bestPos);
bestRow = row;
bestCol = col;
}
}
}
}
for (int k = 1; k <= SUDOKU_DIMS; ++k)
{
if (bestPos[k-1]) // a possible value
{
newState = *this;
newState.data_[bestRow][bestCol] = k;
vs.push_back(newState);
}
}
}
与原来的函数相比，多了十几行，增加了几个局部变量，包括三个int和一个bool数组。这些新增的变量用于保存找到的分支最少的空格的一些相关数据，分别是空格所在行、列，分支数量以及可选的数字。其中有一点要注意的是，在循环中如果发现有一个空格没有可填入的数字，则说明当前状态是一个无解的分支状态，可以立即返回。
经测试，新的解法可以正确地用于DFS和BFS算法，并找到了正确答案，速度也有了大幅提高。在我的机器上进行测试结果（剔除I/O时间）如下：
DFS (one answer)
BFS (one answer)
DFS (all answers)
BFS (all answers)
原来的解法
3.5ms
5.8ms
8.3ms
8.3ms
优化的解法
1.6ms
2.3ms
2.2ms
2.3ms
由于我只使用了一个数独题目进行测试，所以结果并不具有广泛代表性，但也可以在一定程度上说明新的解法已经有了明显的速度提高。
当然，这个解法还可以进一步优化，你如果有兴趣，可以自己试着写一下，也欢迎你把结果反馈给我。
关于数独问题的讨论我想就到此为止了，我们回过头来看看我们的DFS/BFS算法，其实它还有很多局限。你可能已经注意到了，它只适用于一些特殊的问题，即这些问题的状态空间树中的结点不能有重复。我们还是以原来的图来说明一下：
500)this.width=500'>
我们想象一下，如果状态空间树中的结点E与结点A是相同的状态，那么会有什么结果？我们的DFS/BFS算法将会陷入一个无限循环！幸好，数独问题恰好不会出现这样的状况，但是象下象棋、推箱子等问题，都会存在这个问题，一个问题状态在几步之后可能会回到以前出现过的状态。如何解决这个问题？我们将在以后继续讨论。
|
|
|