在優(yōu)先級隊(duì)列分支限界法法中，何時為出接口，也就是while循環(huán)何時退出了？

解空間為[0,1,2…,n-1]，當(dāng)depth = n-1時，就可以記錄結(jié)果了，可以考慮循環(huán)體退出了（實(shí)際上能不能出，還要看他的權(quán)夠不夠大，不夠大的話，還是要老老實(shí)實(shí)的去選擇優(yōu)先級高的分支），換句話來說，一旦有一個一個葉子節(jié)點(diǎn)彈出了，循環(huán)體就結(jié)束了

然后就是最優(yōu)解和最優(yōu)解方案的追蹤

一般來說有兩種方案：
在每個活結(jié)點(diǎn)（就是要存入優(yōu)先級隊(duì)列的數(shù)據(jù)）中保存從root到當(dāng)前結(jié)點(diǎn)的路徑path，也就是一個數(shù)組，這個數(shù)組可以是一個等長的，前面保存的是走過的路徑，后面是還未走過的路徑，所以一旦得到彈出的葉節(jié)點(diǎn)，我們就可以從中得到path，注意這個結(jié)點(diǎn)結(jié)構(gòu)里沒有保存他的前驅(qū)結(jié)點(diǎn)的指針

另外一種實(shí)現(xiàn)方案：就是完全把解空間看出一個空間樹，樹的結(jié)點(diǎn)該有的信息，都保存下來，比如權(quán)重，用于結(jié)點(diǎn)優(yōu)先級排序，當(dāng)前的選擇，就是當(dāng)前你是選擇了那個分支或者叫做結(jié)點(diǎn)，最重要的是它的前驅(qū)結(jié)點(diǎn)是誰，不管是什么樹，他的前驅(qū)結(jié)點(diǎn)只有一個，我們得到了葉子結(jié)點(diǎn)，就可以從葉子追溯到root，實(shí)際上上述就是在***構(gòu)造部分解空間樹***

我們之前學(xué)習(xí)回溯法或者分支限界法，可能會有疑問，都說過解空間是一棵解空間樹，子集樹，完全n叉樹，排列樹，但是我們編碼的時候，連樹、結(jié)點(diǎn)的影子都沒看到。

回溯法樹隱藏在遞歸里，遞歸就是一棵樹，限界分支法我們大部分看到的例子是使用第一種方案，程序只要保持持續(xù)更新最優(yōu)值和路徑path數(shù)組，路徑path數(shù)組記錄了每一步的選擇，相當(dāng)于只是把結(jié)點(diǎn)里的當(dāng)前的選擇和parent,拿出來單獨(dú)更新了，拿出來更新的代價(jià)是，每一個加入到隊(duì)列的結(jié)點(diǎn)都要更新path數(shù)組，好處是可以很簡單的判斷那些解已經(jīng)走過了，那些沒有走過

總結(jié)

以上是生活随笔為你收集整理的限界分支法优先级队列方式出口和追踪解的两种方法总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。