一種回溯算法入門教學思路-資料下載頁
2025-08-04 13:34本頁面
【正文】 解,若是則無需遞歸。為此,需進行兩點修改:(1)到達遞歸邊界時記錄當前最優(yōu)解。(2)當前選定后計算需付出的最少代價。前者可用全局變量來記錄。后者可設立變量cost,例如:例1:設當前最高價值為mv,背包物品總價值cv,剩余尚未決定的所有物品總價值rv,則若剪枝檢查有cv+rv=mc,顯然無須遞歸。為此設任兩城市i和j間的旅費為c[i][j],初始化mc為1(表無窮大),cc為0。在遞歸邊界檢查是否需更新mc。遞歸前后同樣需更新、恢復cc的值,并在遞歸前進行該剪枝檢查。3 結語本文提出的回溯法教學思路采用了相對明確、簡單的解題步驟,有一定局限性,因此只適用于入門教學。但學生一旦掌握回溯算法的基本思想后,可進一步引導其思考如何突破排列問題和子集問題的局限性。突破局限的關鍵在于如何生成當前所有可能的選擇,這要根據(jù)具體問題進行。顯然,不論在什么情況下,本文提出的解題框架仍是非常有用的。參考文獻[1] 楊興旺．基于回溯法的排課算法[j]．電腦知識與技術,2009(19):5196～5197,5209.[2] 黃麗華．在信息學奧賽中“回溯算法”教學的探究[j]．福建電腦,2005(8):158～159.
環(huán)評公示相關推薦
鄂ICP備17016276號-1