首页/新闻资讯/正文详情

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

发布时间:2026/11/18 9:35:23 来源:云帆数科 栏目:资讯中心
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;}

相关推荐

如何在 Ray 中调用大模型?基于 EMR Serverless Spark 的端到端方案设计
如何在 Ray 中调用大模型?基于 EMR Serverless Spark 的端到端方案设计

当工程师在 Ray 集群中调度大规模语言模型(LLM)推理任务时,常面临资源弹性不足、模型服务与数据处理割裂、多模态输入协同困难三大共性挑战。典型场景包括:用户行为日志需结合截图/录屏等非结构化数据生成意图标签;IoT… · 2026/11/1 22:54:11

WebGIS + OpenLayers + GeoServer + PostGIS #量算 #点聚合
WebGIS + OpenLayers + GeoServer + PostGIS #量算 #点聚合

前言 前两篇我们搞定了地图初始化和基础交互,但真实的业务地图数据都在后端:几千条管线、地块、监测点位存在数据库里,前端怎么高效拿到、怎么渲染、怎么做空间查询? 本篇讲透一套最经典的开源全栈方案: 前端 Vue Ope… · 2026/11/6 17:06:40

AURIX™ TC3xx debug protection (with HSM)调试口保护
AURIX™ TC3xx debug protection (with HSM)调试口保护

AURIX™ TC3xx 设备的调试保护功能是 TriCore™ 和 HSM 核所采用的其中一项安全层级措施,其作用是锁定调试接口,以防止来自外部工具的未经授权的访问。它也防止来自外部调试器的未经授权的闪存读写访问。整个设备的调试访问可以通过 AURIX™ TC3xx 启动模… · 2026/11/6 0:04:58

广西兴安电工证报名官方回应:外省证怎么转?薪资前景你得知道
广西兴安电工证报名官方回应:外省证怎么转?薪资前景你得知道

广西兴安电工证报名官方回应:外省证怎么转?薪资前景你得知道 之前考的证在外省能不能转过来?这是很多特种作业人员在换城市、换工作时最头疼的问题。官方回应是,可以转,但流程和材料不能少,尤其在广西兴安这类基层地区,手续办不全,证书就白考。别以为… · 2026/11/18 9:34:31

山西长治电工证怎么考 实操考试心里没底怕挂科 郑州报考避坑指南
山西长治电工证怎么考 实操考试心里没底怕挂科 郑州报考避坑指南

山西长治电工证怎么考 实操考试心里没底怕挂科 郑州报考避坑指南 实操考试心里没底怕挂科,尤其是像你这样的济源在职建筑工人,电工证不是摆设,是饭碗,是安全的底线。山西长治电工证怎么考?别急,咱们一步步来,别再被那些“包过”“代考”的噱头忽悠了… · 2026/11/18 9:34:31

汉中专业的中级电工证值不值得考?别交了培训费还拿不到证
汉中专业的中级电工证值不值得考?别交了培训费还拿不到证

汉中专业的中级电工证值不值得考?别交了培训费还拿不到证 怕考不过白交培训费?汉中专业的中级电工证确实让人又爱又恨,尤其是对那些在工地摸爬滚打的建筑工人来说,证书成了进阶的关键门槛。但现实中,很多人报了培训班,结果要么考试不过,要么培训内容和… · 2026/11/18 9:34:31

鹤壁电工证跨省转介怎么查?考取电工证怎么查询千万别踩坑
鹤壁电工证跨省转介怎么查?考取电工证怎么查询千万别踩坑

鹤壁电工证跨省转介怎么查?考取电工证怎么查询千万别踩坑 之前考的证在外省能不能转过来?这个问题真的不能马虎。不少在鹤壁从事公路工程的电工,之前在外地考的证,现在回本地用,却发现流程复杂、信息不透明,结果白白耽误了工期,还被甲方扣钱。别急,今… · 2026/11/18 9:34:31

东莞电工证自己报考通过率揭秘,别再交冤枉培训费
东莞电工证自己报考通过率揭秘,别再交冤枉培训费

东莞电工证自己报考通过率揭秘,别再交冤枉培训费 怕考不过白交培训费?东莞电工证自己报考的朋友们,别再被培训机构忽悠了,今天就给你 通过率揭秘 ,从报名、备考到考试流程全拆解,让你少走弯路,一次性拿证! 一、东莞电工证自己报考,真的能行吗?… · 2026/11/18 9:34:31

电工证别人不承认?实操考试心里没底怕挂科,备考攻略+费用全解析
电工证别人不承认?实操考试心里没底怕挂科,备考攻略+费用全解析

电工证别人不承认?实操考试心里没底怕挂科,备考攻略+费用全解析 实操考试心里没底怕挂科,电工证别人不承认?你不是一个人,很多准备考电工证的学员都有这个担心。尤其是在郑州,市政工程行业对电工证的要求越来越严格,但很多人拿到证后发现… · 2026/11/18 9:33:31

长春初级电工证怎么考?通过率揭秘全在这里
长春初级电工证怎么考?通过率揭秘全在这里

长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/18 8:19:55

国内电工证报考条件与考试时间
国内电工证报考条件与考试时间

低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/18 8:19:53

电工作业时如何断电?电子证书到底能不能全国通用?
电工作业时如何断电?电子证书到底能不能全国通用?

电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/17 9:06:35

电工证做题最新内部消息:怕考不过白交培训费?三招教你稳过
电工证做题最新内部消息:怕考不过白交培训费?三招教你稳过

电工证做题最新内部消息:怕考不过白交培训费?三招教你稳过 你是不是也这样?报名了电工证培训,交了钱,结果一到考试就懵, 怕考不过白交培训费 ?别慌,这是很多初次报考人员的真实写照。而最近, 河南省应急管理厅… · 2026/11/18 0:00:37

许昌电工证在哪复审 别踩坑怕考不过白交培训费
许昌电工证在哪复审 别踩坑怕考不过白交培训费

许昌电工证在哪复审 别踩坑怕考不过白交培训费 怕考不过白交培训费,这几乎是每个想考电工证的学员心中的痛。尤其是在许昌,电工证的报考和复审流程复杂,稍有不慎就可能被坑, 千万别踩坑… · 2026/11/18 0:00:37

老式电工证还能用吗?怎么报名别踩坑,河南企业主都在问的实操真相
老式电工证还能用吗?怎么报名别踩坑,河南企业主都在问的实操真相

老式电工证还能用吗?怎么报名别踩坑,河南企业主都在问的实操真相 实操考试心里没底怕挂科?老式电工证还能用吗?怎么报名又怕被坑?这些问题几乎每个准备考电工证的施工企业负责人心里都在打鼓。尤其是河南本地的中小施工企业,很多都在用老式电工证,但随… · 2026/11/18 0:00:37

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/17 21:47:42

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/17 21:47:42

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/17 21:47:42

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码