14-回溯法-資料下載頁
2025-08-04 08:28本頁面
【正文】 右子樹{ 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是當前擴展結(jié)點z的右子樹(或左子樹)的價值上界，如果cv+r≤bestv時，則可以裁剪掉右子樹(或左子樹)。一種簡單的確定z的左、右子樹最優(yōu)值上界的方法（設(shè)z為第k層結(jié)點）：左子樹上界= i=kΣi=nvi ，右子樹上界=i=k+1Σi=nvi，－求經(jīng)擴展結(jié)點z的可行解價值上界的方法計算至擴展結(jié)點的當前背包價值已知xi, i=1~k1，當前背包價值cv=i=1Σi=k1vixi最后，經(jīng)z左子樹的可行解價值上界＝cv+左子樹上界經(jīng)z右子樹的可行解價值上界＝cv+右子樹上界－算法（略）l 排列生成問題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號-1