关于前端:回溯算法

45次阅读

共计 441 个字符,预计需要花费 2 分钟才能阅读完成。

回溯算法

原文链接:https://note.noxussj.top/?source=sifo

介绍

回溯算法是算法设计中的一种办法。回溯算法是一种渐进式寻找并构建问题解决形式的策略。回溯算法会先从一个可能的动作开始解决问题,如果不行,就回溯并抉择另一个动作,直到将问题解决。

就像你在一个迷宫外面遇到了以后有三条岔路,你抉择了第一条后发现此路不通,那你是不是要回到原点,进行抉择第二条路线,以此类推,最初抉择一条正确的路线。


什么问题适宜用回溯算法解决?

  • 有很多分岔路
  • 这些路外面有绝路,也有前途
  • 通常须要用递归来模仿所有的路

根底案例

场景一

全排列

    // 输出
    const input = [1, 2, 3]
    
    // 输入
    const output = [[1, 2, 3],
        [1, 3, 2],
        [2, 1, 3],
        [2, 3, 1],
        [3, 1, 2],
        [3, 2, 1]
    ]
步骤:
  1. 用递归模仿所有前途的状况
  2. 遇到蕴含反复元素的状况,就回溯
  3. 收集所有达到递归起点的状况并返回

原文链接:https://note.noxussj.top/?source=sifo

正文完
 0