優(yōu)先隊(duì)列式分支限界法的通俗的解釋是什么?

一、優(yōu)先隊(duì)列式分支限界法的通俗的解釋

分支界限法，就是用了某種方法來(lái)選擇較好的情況，略過(guò)不必要的情況，達(dá)到降低復(fù)雜度的目的。其實(shí)就是優(yōu)化（也稱剪枝）。用優(yōu)先隊(duì)列實(shí)現(xiàn)dijkstra就是問題中的例子。建議上oj手寫一下，動(dòng)手做過(guò)更能理解。

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

選擇下一個(gè)E-結(jié)點(diǎn)的方式不同，則會(huì)有幾種不同的分支搜索方式：1.FIFO搜索；2.LIFO搜索；優(yōu)先隊(duì)列式搜索。

分支界限法的一般過(guò)程

由于求解目標(biāo)不同，導(dǎo)致分支界限法與回溯法在解空間樹T上的搜索方式也不相同?；厮莘ㄒ陨疃葍?yōu)先的方式搜索解空間樹T，而分支界限法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹T：

搜索策略

在擴(kuò)展結(jié)點(diǎn)處，先生成所有的子結(jié)點(diǎn)(分支)，然后從當(dāng)前的活結(jié)點(diǎn)表中選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)。為了有效的選擇下一個(gè)擴(kuò)展結(jié)點(diǎn)，以加速搜索的進(jìn)程，在每一活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值(限界)，并根據(jù)這些已經(jīng)計(jì)算出的函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò)展結(jié)點(diǎn)，使搜索朝著解空間樹上有優(yōu)異解的分支推進(jìn)，以便盡快找出一個(gè)優(yōu)異解。

分支界限法以廣度優(yōu)先或以最小耗費(fèi)(最大效益)優(yōu)先的方式搜索問題的解空間樹。問題的解空間樹是表示問題解空間的一棵有序樹，常見的有子集樹和排列樹。在搜索問題的解空間樹時(shí)，分支限界法與回溯法對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)所使用的擴(kuò)展方式不同。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)稱為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有子結(jié)點(diǎn)。在這些子結(jié)點(diǎn)中，那些導(dǎo)致不可行解或?qū)е路莾?yōu)異解的子結(jié)點(diǎn)被舍棄，其余子結(jié)點(diǎn)被加入活結(jié)點(diǎn)中。此后，從活結(jié)點(diǎn)表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所求的解或活結(jié)點(diǎn)表為空時(shí)為止。

對(duì)某個(gè)節(jié)點(diǎn)進(jìn)行搜索時(shí)，先估算出目標(biāo)的解，再確定是否向下搜索（選擇最小損耗的結(jié)點(diǎn)進(jìn)行搜索）在分支結(jié)點(diǎn)上，預(yù)先分別估算沿著它的各個(gè)兒子結(jié)點(diǎn)向下搜索的路徑中，目標(biāo)函數(shù)可能取得的界，然后把它的這些兒子結(jié)點(diǎn)和它們可能取得的界保存在一張結(jié)點(diǎn)表中，再?gòu)谋碇羞x擇界最小或最大的結(jié)點(diǎn)向下搜索。一般采用優(yōu)先隊(duì)列維護(hù)這張表。

延伸閱讀：

二、回溯法和分支界限法的區(qū)別

回溯法
1）（求解目標(biāo)）回溯法的求解目標(biāo)是找出解空間中滿足約束條件的一個(gè)解或所有解。
2）（搜索方式深度優(yōu)先）回溯法會(huì)搜索整個(gè)解空間，當(dāng)不滿條件時(shí)，丟棄，繼續(xù)搜索下一個(gè)兒子結(jié)點(diǎn)，如果所有兒子結(jié)點(diǎn)都不滿足，向上回溯到它的父節(jié)點(diǎn)。
分支限界法
1）（求解目標(biāo)）分支限界法的目標(biāo)一般是在滿足約束條件的解中找出在某種意義下的優(yōu)異解，也有找出滿足約束條件的一個(gè)解。
2）（搜索方式）分支限界法以廣度優(yōu)先或以最小損耗優(yōu)先的方式搜索解空間。
3）常見的兩種分支界限法
a.隊(duì)列式（FIFO）分支界限法（廣度優(yōu)先）：按照隊(duì)列先進(jìn)先出原則選取下一個(gè)結(jié)點(diǎn)為擴(kuò)展結(jié)點(diǎn)。
b.優(yōu)先隊(duì)列式分支限界法（最小損耗優(yōu)先）：按照優(yōu)先隊(duì)列規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)較高的結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。