14-回溯法-資料下載頁(yè)
2025-08-04 08:28本頁(yè)面
【正文】 右子樹(shù){ x[i]=0。KnapBacktrack(i+1)。}}}main(float c, int n, float w[],float v[], int x[]){ //主程序float cw=, cv=, bestv=。KnapBacktrack(1)。}l 有限界函數(shù)的算法－基本思想設(shè)r是當(dāng)前擴(kuò)展結(jié)點(diǎn)z的右子樹(shù)(或左子樹(shù))的價(jià)值上界，如果cv+r≤bestv時(shí)，則可以裁剪掉右子樹(shù)(或左子樹(shù))。一種簡(jiǎn)單的確定z的左、右子樹(shù)最優(yōu)值上界的方法（設(shè)z為第k層結(jié)點(diǎn)）：左子樹(shù)上界= i=kΣi=nvi ，右子樹(shù)上界=i=k+1Σi=nvi，－求經(jīng)擴(kuò)展結(jié)點(diǎn)z的可行解價(jià)值上界的方法計(jì)算至擴(kuò)展結(jié)點(diǎn)的當(dāng)前背包價(jià)值已知xi, i=1~k1，當(dāng)前背包價(jià)值cv=i=1Σi=k1vixi最后，經(jīng)z左子樹(shù)的可行解價(jià)值上界＝cv+左子樹(shù)上界經(jīng)z右子樹(shù)的可行解價(jià)值上界＝cv+右子樹(shù)上界－算法（略）l 排列生成問(wèn)題Backtrack(int t){if tn then output(x)。elsefor i=t to n do{ swap(x[t], x[i])。Backtrack(t+1)。swap(x[t], x[i])。}}main(int n){for i=1 to n do x[i]=i。Backtrack(1)。}
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1