V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
xhf1024
V2EX  ›  Java

v 友们!有没有简单易懂的回溯算法例子,让小弟学习一下。

  •  
  •   xhf1024 · 2020-09-18 10:51:13 +08:00 · 2221 次点击
    这是一个创建于 1287 天前的主题,其中的信息可能已经有所发展或是发生改变。
    9 条回复    2020-09-18 13:13:05 +08:00
    Helix225
        2
    Helix225  
       2020-09-18 11:27:15 +08:00
    探迷宫,数独生成
    twllz
        3
    twllz  
       2020-09-18 11:37:24 +08:00
    LeetCode 《 77.组合》,链接: https://leetcode-cn.com/problems/combinations/
    推荐这一个题解,链接: https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/

    总之就是这样一种模式:
    ```
    1. 执行某种操作;
    2. 在这种操作的基础上继续操作;
    3. 撤回 "1" 中的操作。
    ```
    kanglo
        4
    kanglo  
       2020-09-18 11:43:52 +08:00
    @ChenFanlin 这个 repo 真是太好了,我学算法刷题全靠这个
    asanelder
        5
    asanelder  
       2020-09-18 12:50:43 +08:00
    回溯就是 DFS 吧,可以看看俺写的文章
    https://segmentfault.com/a/1190000024456834

    由一个很简单的直观的例子讲 DFS
    然后从 DFS 的角度来看待树的三种遍历
    还举了一个使用 DFS 轻松解决 leetcode 题的问题
    最后引申到访问者模式,你会发现两者的相似处

    以上由浅入深,举例易懂,配以图片。

    请慢慢细品
    asanelder
        6
    asanelder  
       2020-09-18 12:52:10 +08:00
    @ChenFanlin #1 啊看到这个博主关于树的三种遍历其本质是时间点的看法,这和俺的看法一样啊!

    果然天才所见略同
    CodeJr
        7
    CodeJr  
       2020-09-18 12:53:41 +08:00 via Android
    全排列,八皇后 老经典了
    asanelder
        8
    asanelder  
       2020-09-18 12:56:49 +08:00
    俺的是用 java 举的例子
    一楼那个是 python

    再给楼主提个醒,回溯解题的过程就是一个树的 DFS 过程,所以,首先你要能把一个题的解想像成一颗树(几叉无所谓)
    araaaa
        9
    araaaa  
       2020-09-18 13:13:05 +08:00 via iPhone
    8 皇后
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3257 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 13:52 · PVG 21:52 · LAX 06:52 · JFK 09:52
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.