📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3539| 回复: 3
跳转到指定楼层
上一主题 下一主题
收起左侧

谁给介绍介绍backtracking?

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
一直对大家说的backtracking没有一个清晰的概念。请问能否推荐篇文章详细说明一下backtracking是怎么个用法?多谢啦

上一篇:LinkedList Dummy Head有什么好处?
下一篇:Dijkstra Good Numerals 求解
🔗
storm_hair 2014-10-23 14:11:09 | 只看该作者
全局:
DFS特殊情况 每次只有一个子状态入栈
回复

使用道具 举报

🔗
mayingjie116 2014-10-28 00:20:40 | 只看该作者
全局:
Backtracking和DFS很像。区别在于Backtracking用在general graph中, DFS只能用在tree里面,所以DFS是Backtracking的特殊情况。
可以参考Artificial Intelligence - A Modern Approach 3rd ed - S. Russell, P. Norvig.
回复

使用道具 举报

🔗
chopinsky 2014-10-28 06:34:19 | 只看该作者
全局:
本帖最后由 chopinsky 于 2014-10-28 06:40 编辑

一个很简单的例子:如何求解sudoku problem,使用recursive call的方法。 步骤就是先在一个空格挨个试探1-9,如果这个数可以放在这一格,则假设目前的表格变成初始状态,进入下一个空格,再挨个填入1-9。最后如果所有空格都填完了,发现都没有问题,那么结束;如果在某个空格发现填上1-9都违反规则,那么说明上面某层的数填的不对,于是回到上一层,从之前的数往后找,看看是不是后面的数还有符合规则的;如果有,拿目前的状态进入下一格,如果还是找到了9还没有符合规则的数,则再返回上一层。
youtube上有一个烙印的视频解决这个问题,用的是backtracking的方法,代码写出来比较简单,也很容易理解。如果不能翻墙就算了。。。。。。

Part 1: algorithm
https://www.youtube.com/watch?v=IX3qHsLGvq8

Part 2: dry code:
https://www.youtube.com/watch?v=P9_F7kuHU90

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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