一、優先隊列式分支限界法的通俗的解釋

分支界限法，就是用了某種方法來選擇較好的情況，略過不必要的情況，達到降低復雜度的目的。其實就是優化（也稱剪枝）。用優先隊列實現dijkstra就是問題中的例子。建議上oj手寫一下，動手做過更能理解。

所謂“分支”就是采用廣度優先(BFS)的策略，依次搜索E-結點的所有分支，也就是所有相鄰的結點，拋棄不滿足約束的結點，其余節點加入活結點表。然后從表中選擇一個結點作為下一個E-結點，繼續搜索。

選擇下一個E-結點的方式不同，則會有幾種不同的分支搜索方式：1.FIFO搜索；2.LIFO搜索；優先隊列式搜索。

分支界限法的一般過程

由于求解目標不同，導致分支界限法與回溯法在解空間樹T上的搜索方式也不相同。回溯法以深度優先的方式搜索解空間樹T，而分支界限法則以廣度優先或以最小耗費優先的方式搜索解空間樹T：

搜索策略

在擴展結點處，先生成所有的子結點(分支)，然后從當前的活結點表中選擇下一個擴展結點。為了有效的選擇下一個擴展結點，以加速搜索的進程，在每一活結點處，計算一個函數值(限界)，并根據這些已經計算出的函數值，從當前活結點表中選擇一個最有利的結點作為擴展結點，使搜索朝著解空間樹上有優異解的分支推進，以便盡快找出一個優異解。

分支界限法以廣度優先或以最小耗費(最大效益)優先的方式搜索問題的解空間樹。問題的解空間樹是表示問題解空間的一棵有序樹，常見的有子集樹和排列樹。在搜索問題的解空間樹時，分支限界法與回溯法對當前擴展結點所使用的擴展方式不同。在分支限界法中，每一個活結點只有一次機會稱為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有子結點。在這些子結點中，那些導致不可行解或導致非優異解的子結點被舍棄，其余子結點被加入活結點中。此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續到找到所求的解或活結點表為空時為止。

對某個節點進行搜索時，先估算出目標的解，再確定是否向下搜索（選擇最小損耗的結點進行搜索）在分支結點上，預先分別估算沿著它的各個兒子結點向下搜索的路徑中，目標函數可能取得的界，然后把它的這些兒子結點和它們可能取得的界保存在一張結點表中，再從表中選擇界最小或最大的結點向下搜索。一般采用優先隊列維護這張表。

延伸閱讀：

二、回溯法和分支界限法的區別

回溯法
1）（求解目標）回溯法的求解目標是找出解空間中滿足約束條件的一個解或所有解。
2）（搜索方式深度優先）回溯法會搜索整個解空間，當不滿條件時，丟棄，繼續搜索下一個兒子結點，如果所有兒子結點都不滿足，向上回溯到它的父節點。
分支限界法
1）（求解目標）分支限界法的目標一般是在滿足約束條件的解中找出在某種意義下的優異解，也有找出滿足約束條件的一個解。
2）（搜索方式）分支限界法以廣度優先或以最小損耗優先的方式搜索解空間。
3）常見的兩種分支界限法
a.隊列式（FIFO）分支界限法（廣度優先）：按照隊列先進先出原則選取下一個結點為擴展結點。
b.優先隊列式分支限界法（最小損耗優先）：按照優先隊列規定的優先級選取優先級較高的結點成為當前擴展結點。