一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 851|回复: 13
收起左侧

[算法题] DFS在非图论算法具体是怎么思考的?

[复制链接] |试试Instant~ |关注本帖
baojialiang 发表于 2014-1-3 06:56:30 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
小弟不才 最近刷题的时候 发现很多题目都是属于“dfs”类型的。dfs的概念应该是在图论里吧? 在普通的非图论算法题里面 一般做起题目来是怎么考虑的呢?比如说求一个String的所有permutation,或者八皇后问题。目前理解下来,就是把当前所有可以得到的解 当做图论中得下一个vertex,然后依次去遍历,是吗?我不知道我的理解对不对。或者还有需要补充的地方? 还有一般哪些题型 一般都可以通过dfs来做呢?



1guangnian 发表于 2014-1-3 07:06:27 | 显示全部楼层
个人一点理解:
当前节点(状态)通过某操作转移到下一节点(状态),进入下一层DFS,完了返回到这一状态时要撤销这一步操作
类似于((()))这种括号序列的感觉,左括号看作1(进行某一操作),右括号看作-1(撤销某一操作),他们是一一对应的,栈的顺序
实现时只考虑其中一层(一个状态)
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-1-3 07:08:42 | 显示全部楼层
如果你能把题目抽象成一个图/树,一个节点对应一个状态,状态之间通过某种操作转移,或者需要枚举时,肯定可以用DFS搞定的,具体还是多做题找感觉吧
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-1-3 07:10:51 | 显示全部楼层
感觉还有就是DFS比较好实现recursion
回复 支持 反对

使用道具 举报

constantine124 发表于 2014-1-3 07:17:50 | 显示全部楼层
典型的题目就是 求出所有XXX 所有路径,all possible results 等等
回复 支持 反对

使用道具 举报

readman 发表于 2014-1-3 07:50:22 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| baojialiang 发表于 2014-1-7 10:27:51 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| baojialiang 发表于 2014-1-7 10:28:19 | 显示全部楼层
readman 发表于 2014-1-3 07:50
http://blog.csdn.net/u011095253/article/details/9158387

多谢 哈哈~
回复 支持 反对

使用道具 举报

hetong_007 发表于 2014-1-7 16:45:49 | 显示全部楼层
只要需要求的解可以通过一个序列或者一系列的步骤来表示,就可以用DFS。不过一些情况下DFS需要剪枝,或者是效率太低而使用动态规划等其他方法。
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2014-1-7 17:40:17 | 显示全部楼层
其实我想问问经常会有题目要求给出 all possible result, 那么我用递归, 如果第一步成立,就递归到下一步,知道满足所有条件就是一个possible result, 这种做法是不是DFS?
回复 支持 反对

使用道具 举报

readman 发表于 2014-1-7 19:09:22 | 显示全部楼层
kelvinzhong 发表于 2014-1-7 17:40
其实我想问问经常会有题目要求给出 all possible result, 那么我用递归, 如果第一步成立,就递归到下一步, ...

没看懂你的意思. 给个例子吧
回复 支持 反对

使用道具 举报

lzsilica 发表于 2014-1-15 17:03:51 | 显示全部楼层
hetong_007 发表于 2014-1-7 16:45
只要需要求的解可以通过一个序列或者一系列的步骤来表示,就可以用DFS。不过一些情况下DFS需要剪枝,或者是 ...

“不过一些情况下DFS需要剪枝”, “剪枝”说的好形象,赞一个。
回复 支持 反对

使用道具 举报

hetong_007 发表于 2014-1-15 20:27:15 | 显示全部楼层
lzsilica 发表于 2014-1-15 17:03
“不过一些情况下DFS需要剪枝”, “剪枝”说的好形象,赞一个。

啊,其实这是一个术语
回复 支持 反对

使用道具 举报

discoveryi 发表于 2014-1-15 21:17:34 | 显示全部楼层
请教“剪枝”是什么意思?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 18:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表