<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                [TOC] ## 概述 * 回溯法是一種通過探索所有可能的候選解來找出所有的解的算法。如果候選解被確認不是一個解的話(或者至少不是最后一個解),回溯算法會通過在上一步進行一些變化拋棄該解,即回溯并且再次嘗試。 * 回溯算法就是個多叉樹的遍歷問題 解決一個回溯問題,實際上就是一個決策樹的遍歷過程 1. 路徑:也就是已經做出的選擇。 2. 選擇列表:也就是你當前可以做的選擇。 3. 結束條件:也就是到達決策樹底層,無法再做選擇的條件。 回溯算法框架 ``` result = [] def backtrack(路徑, 選擇列表): if 滿足結束條件: result.add(路徑) return for 選擇 in 選擇列表: 做選擇 backtrack(路徑, 選擇列表) 撤銷選擇 ``` > 其核心就是 for 循環里面的遞歸,在遞歸調用之前「做選擇」,在遞歸調用之后「撤銷選擇」 如枚舉 1,2,3,列出回溯算法的「決策樹」 ![](https://img.kancloud.cn/75/3b/753b5d39590311e4d25d0afd7844ba38_353x186.png) ![](https://img.kancloud.cn/54/6b/546b0da8a7a668c5e5db98d6a9029595_400x224.png) 現在可以解答開頭的幾個名詞:\[2\] 就是**路徑**,記錄你已經做過的選擇;\[1,3\] 就是**選擇列表**,表示你當前可以做出的選擇;**結束條件**就是遍歷到樹的底層,在這里就是選擇列表為空的時候。 **前序和后續后序排列** ![](https://img.kancloud.cn/d4/a7/d4a7981828702cb08d0fefc6a6db57f8_391x208.png) 前序遍歷的代碼在進入某一個節點之前的那個時間點執行,后序遍歷代碼在離開某個節點之后的那個時間點執行。 ![](https://img.kancloud.cn/49/5e/495e2b2c34b2c2caf680028f3f3ffd72_400x225.png) 這樣可以更好的理解回溯算法 ``` for 選擇 in 選擇列表: # 做選擇 將該選擇從選擇列表移除 路徑.add(選擇) backtrack(路徑, 選擇列表) # 撤銷選擇 路徑.remove(選擇) 將該選擇再加入選擇列表 ``` 我們只要在遞歸之前做出選擇,在遞歸之后撤銷剛才的選擇 回溯算法 go 實現 <details> <summary>server.go</summary> ``` import ( "fmt" ) var group [][]int func permute(nums []int) [][]int { group =make([][]int,0) if len(nums) == 0 { return group } // 存儲已經用過的值,遍歷共用一個 狀態 used := make([]bool, len(nums)) track := make([]int, 0,len(nums)) backtrack(nums, track, used) return group } func backtrack(nums []int, track []int, used []bool) { if len(nums) == len(track) { tmp := make([]int, len(track)) // 拷貝切片值 copy(tmp, track) group = append(group, tmp) return } for i := 0; i < len(nums); i++ { if !used[i] { used[i]=true track = append(track, nums[i]) backtrack(nums,track, used) // 撤銷狀態 used[i]=false track=track[:len(track)-1] } } } func main() { fmt.Printf("%+v\n", permute([]int{1,2,3})) //[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]] } ``` </details> <br/> 回溯算法的一個特點,不像動態規劃存在重疊子問題可以優化,回溯算法就是純暴力窮舉,復雜度一般都很高點贊
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看