一種回溯算法入門教學(xué)思路(參考版)
2024-08-15 13:34本頁面
【正文】 參考文獻(xiàn)[1] 楊興旺．基于回溯法的排課算法[j]．電腦知識與技術(shù),2009(19):5196～5197,5209.[2] 黃麗華．在信息學(xué)奧賽中“回溯算法”教學(xué)的探究[j]．福建電腦,2005(8):158～159.。突破局限的關(guān)鍵在于如何生成當(dāng)前所有可能的選擇,這要根據(jù)具體問題進(jìn)行。3 結(jié)語本文提出的回溯法教學(xué)思路采用了相對明確、簡單的解題步驟,有一定局限性,因此只適用于入門教學(xué)。在遞歸邊界檢查是否需更新mc。后者可設(shè)立變量cost,例如:例1:設(shè)當(dāng)前最高價值為mv,背包物品總價值cv,剩余尚未決定的所有物品總價值rv,則若剪枝檢查有cv+rv=mc,顯然無須遞歸。(2)當(dāng)前選定后計算需付出的最少代價。剪枝用于求最優(yōu)解時,也在遞歸前用if檢查當(dāng)前選擇是否不可能優(yōu)于已知最優(yōu)解,若是則無需遞歸?？蓡为殞憴z查函數(shù)返回新加皇后是否滿足約束,遞歸前調(diào)用該函數(shù)檢查。設(shè)變量cw記錄當(dāng)前背包容量,只有背包容量不超限額時才遞歸。這樣入門時可繞過“活節(jié)點”、“擴展結(jié)點”等較抽象、復(fù)雜的概念。通過兩個手段:(1)根據(jù)題意約束。 優(yōu)化算法生成所有可能解后,只要檢查每個可能的解是否滿足題目要求即可,但
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1