byvoid魔獸世界模擬賽解題報告-資料下載頁
2024-11-25 19:28本頁面
【正文】 商品。我們可以購買一些商品放入倉庫。每天都有一個需要值，我們可以購買物品來滿足需求，也可以從倉庫中取出來滿足需求。 倉庫有一定的存儲費(fèi)用，物品的價值不斷變化。 這是一個很典型的多階段決策問題。 在 Dynamic+Programming+的 。 模型 潛入辛迪加 ?這是一道經(jīng)典的分層搜索問題。該題來自CTSC1999 拯救大兵瑞恩。 ?原題為走迷宮問題，要使用鑰匙開門。而該題仍然是走迷宮，破壞防御系統(tǒng)，與拿鑰匙開門本質(zhì)上是相同的。 問題簡述 ?在迷宮中只能上下左右四個方向移動，不能進(jìn)入障礙物和衛(wèi)兵的視線。不能進(jìn)入沒有被摧毀的監(jiān)視器。 ?摧毀供電裝置，對應(yīng)的監(jiān)視器失效。 ?起點為 (1,1)終點為（ N,N)。 問題簡化 ?可見，衛(wèi)兵的監(jiān)視范圍和障礙物是沒有區(qū)別的，我們可以把衛(wèi)兵的監(jiān)視范圍初始化為障礙物。 ?監(jiān)視器為一種特殊的障礙物，可以被摧毀。 算法設(shè)計 ?假如沒有監(jiān)視器的存在，這道題怎么做？ ?廣度優(yōu)先搜索！搜索從起點到終點的步數(shù)。記錄走過的點，不再訪問。 ?有了監(jiān)視器怎么辦？ 算法設(shè)計 ?還是廣搜。但是我們不能簡單的記錄走過的點一定不再走，因為我們會去專門破壞供電裝置，然后返回。 ?思考，什么情況下返回？ ?當(dāng)然，一般情況下，返回是毫無意義的，只有破壞了供電裝置 ，返回才是有必要的。 算法設(shè)計 ?用哈希表再加一維記錄當(dāng)前破壞的狀態(tài)下走過的頂點。 ?廣搜到新的位置時，如果改變了破壞狀態(tài)，那么用一維新的哈希表記錄走過的頂點。 算法設(shè)計 ?這就是分層搜索的思想，想象我們破壞了新的裝置時，進(jìn)入了新的一層地圖，一切腳步都要重走。 ?用二進(jìn)制表示裝置破壞的狀況，開辟 2^M個哈希表。 謝謝 ?作者： BYVoid ?歡迎訪問
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1