N 皇后问题：两种写法的比较

N 皇后问题DFS 搜索空间与剪枝之前写 N 皇后问题我用了两种写法。一种是按行遍历每一层 DFS 处理一行另一种是按点遍历每次从当前位置开始枚举后面的所有格子。两种写法都用数组记录列和对角线check 都是 O(1)但实际运行起来性能差距很大。先看按行遍历的写法voiddfs(intu){if(un){solutions;return;}for(intj0;jn;j){if(check(u,j)){col[j]line[u-jn]unline[uj]1;dfs(u1);col[j]line[u-jn]unline[uj]0;}}}每一层只处理一行所以不需要考虑同一行放置多个皇后的情况。再看按点遍历的写法voiddfs(intpos,intcnt){if(cntn){solutions;return;}if(posn*n)return;for(intkpos;kn*n;k){intxk/n,yk%n;if(check(x,y)){row[x]col[y]line[x-yn]unline[xy]1;dfs(k1,cnt1);row[x]col[y]line[x-yn]unline[xy]0;}}}这里有一个问题。假设第一行还没有放皇后搜索却已经进入了第二行。那么后续就不可能再回到第一行因为pos只会递增。既然每一行必须放置一个皇后这条搜索路径就已经注定失败了。但原来的代码并不知道这一点仍然会继续搜索。我给两种写法增加了节点数和 check 次数的统计运行 n 10。指标按行遍历按点遍历解的数量724724DFS 节点35,5397,535,369check 次数348,15070,450,278耗时3.088 ms535.993 ms按点遍历的 DFS 节点是按行遍历的 212 倍左右。为了验证这个猜想我统计了进入 DFS 时已经越过至少一行空行的节点。结果是 7,499,830 个占全部 DFS 节点的约 99.53%。接下来增加一个剪枝voiddfs(intpos,intcnt){nodes;intnext_rowpos/n;for(intr0;rnext_row;r){if(!row[r]){return;}}if(cntn){solutions;return;}if(posn*n)return;for(intkpos;kn*n;k){intxk/n,yk%n;if(check(x,y)){row[x]col[y]line[x-yn]unline[xy]1;dfs(k1,cnt1);row[x]col[y]line[x-yn]unline[xy]0;}}}重新运行指标剪枝前剪枝后解的数量724724DFS 节点7,535,369185,489check 次数70,450,2781,256,703耗时535.993 ms14.271 msDFS 节点减少了约 97.54%耗时减少了约 97.34%。这就验证了我的猜想大量性能开销来自那些已经不可能得到完整解却仍然继续搜索的分支。不过剪枝后的按点遍历仍然比按行遍历慢约 4.75 倍。原因也很简单。剪枝只是提前终止了不可能成功的分支但按点遍历仍然会枚举其他行的格子再通过row[]判断这些位置是否合法。而按行遍历直接规定每一层处理哪一行从搜索结构上就避免了这些操作。所以对于 N 皇后问题与其在按点遍历的基础上不断增加剪枝不如直接按行建模。有时候优化算法不一定是让每一步执行得更快而是让不必要的步骤根本不发生。补充两种搜索空间的结构差异统一节点和检查次数的统计口径完整代码#includeiostream#includechronousingnamespacestd;namespacev1{constintN20;intn;intcol[N],line[2*N],unline[2*N];longlongnodes0;longlongchecks0;longlongsolutions0;boolcheck(inti,intj){checks;return!col[j]!line[i-jn]!unline[ij];}voiddfs(intu){nodes;if(un){solutions;return;}for(intj0;jn;j){if(check(u,j)){col[j]line[u-jn]unline[uj]1;dfs(u1);col[j]line[u-jn]unline[uj]0;}}}voidrun(intnn){nnn;nodescheckssolutions0;for(inti0;iN;i)col[i]0;for(inti0;i2*N;i)line[i]unline[i]0;autot0chrono::steady_clock::now();dfs(0);autot1chrono::steady_clock::now();doublemschrono::durationdouble,milli(t1-t0).count();cout\n[v1 行建模]\nn n\nsolutions solutions\nnodes nodes\nchecks checks\ntime ms ms\n;}}// namespace v1namespacev3{constintN20;intn;introw[N],col[N],line[2*N],unline[2*N];longlongnodes0;longlongchecks0;longlongsolutions0;// 进入了多少个包含“前面某行仍为空”的 DFS 状态longlongskipped_nodes0;// 其中有多少个状态没有成功放满 n 个皇后longlongdead_nodes0;// 由于越过空行而必然无法得到完整解的状态按深度统计longlongskipped_by_depth[N1]{};boolcheck(intx,inty){checks;return!row[x]!col[y]!line[x-yn]!unline[xy];}voiddfs(intpos,intcnt){nodes;// 检查已经越过的行 [0, pos / n) 是否存在空行intnext_rowpos/n;boolhas_skipped_rowfalse;for(intr0;rnext_rowrn;r){if(!row[r]){has_skipped_rowtrue;break;}}if(has_skipped_row){skipped_nodes;skipped_by_depth[cnt];}if(cntn){solutions;return;}if(posn*n){if(has_skipped_row)dead_nodes;return;}for(intkpos;kn*n;k){intxk/n;intyk%n;if(check(x,y)){row[x]col[y]line[x-yn]unline[xy]1;dfs(k1,cnt1);row[x]col[y]line[x-yn]unline[xy]0;}}}voiddfs2(intpos,intcnt){nodes;// 剪枝已经越过的行必须全部放置过皇后intnext_rowpos/n;for(intr0;rnext_row;r){if(!row[r]){return;}}// 已经放满 n 个皇后找到一个解if(cntn){solutions;return;}// 棋盘已经遍历完仍未放满 n 个皇后if(posn*n){return;}// 从当前位置开始枚举后续所有格子for(intkpos;kn*n;k){intxk/n;intyk%n;if(check(x,y)){// 放置皇后row[x]col[y]line[x-yn]unline[xy]1;dfs2(k1,cnt1);// 回溯撤销皇后row[x]col[y]line[x-yn]unline[xy]0;}}}voidrun(intnn){nnn;nodescheckssolutions0;skipped_nodesdead_nodes0;for(inti0;iN;i)skipped_by_depth[i]0;for(inti0;iN;i)row[i]col[i]0;for(inti0;i2*N;i)line[i]unline[i]0;autot0chrono::steady_clock::now();dfs(0,0);autot1chrono::steady_clock::now();doublemschrono::durationdouble,milli(t1-t0).count();cout\n[v3 点级建模]\nn n\nsolutions solutions\nnodes nodes\nchecks checks\nskipped_nodes skipped_nodes\ndead_nodes dead_nodes\ntime ms ms\n;cout\n按已放置皇后数量统计 skipped_nodes\n;for(inti0;in;i){coutcnt i: skipped_by_depth[i]\n;}}}// namespace v3intmain(){intn10;v1::run(n);v3::run(n);return0;}