昨天做了一道算法題給大家分享了下我的解法，有給出建設性意見的，有支持的還有看得一知半解的。自己想了想的確有可以優化的地方，貼出優化方案。原題和解答過程在這里http://www.cnblogs.com/xianyudotnet/p/5887304.html。
題目要點：
給出一個0,1矩陣，矩陣中的1就是路徑，左右移動消耗體力1，上移消耗3，下移不消耗。給定一個體力值求左上角到右上角的最小消耗路徑。為了方便測試建立了一個8*8的矩陣如圖。
路徑是這樣的
原方法的結果：
上一篇中解題思路就是：遞歸模擬路徑的移動，探索出給定體力值所有可移動路徑，然后選取體力消耗最小的路徑。
我修改了一下代碼，控制了輸入輸出，就跑上圖的矩陣用于對比測試，結果是這樣的。
優化方案：
1.首先解決循環路徑問題。原方法中只要體力沒消耗完，循環路徑依然循環直至體力消耗完畢，這是相當的不科學。于是移動后檢查當前坐標是否在路勁中，在說明循環了，直接放棄此路徑。
2.其次是體力值問題。如果已經有找到一條可行路徑且得知消耗了體力p，那么接下來所有移動后消耗體力大于p的路徑也放棄。
有同學提到從最小體力值不斷增加循環做遞歸直到找到路徑則這個體力值就是最優解。當然是可行的，但是解很靠后的話，效率是不如原方法固定體力值。后來我又提到用分治的方法固定體力值，后來發現我也是naive了。因為一次遞歸如果找出解那就是最優了，沒找出再調整體力范圍，再遞歸查找，重復計算太多，而且是針對原方法的情況。新方法第二條優化已經是動態調整體力限制，外部再調整體力范圍沒有意義且作用不大。所以優化后的效率是這樣的。
優化結果：
代碼：
好多人說用這種算法，那種算法，一大堆名詞。。。我看著那些公式真的頭疼。我有時間和精力一定努力提高自己學習先進姿勢水平。我的野生算法就是這樣，經過優化后感覺效率也還說得過去吧。
想測試的依舊github上自取，兩個版本的代碼都有：https://github.com/631320085/Algorithm
這題我覺得再提高，可能就是要用數據結構那一套，建立路徑模型，用上高大上的公式分分鐘屌炸天是吧。我今后努力試試。
文章列表
留言列表
