一、前言
小伙伴們好军掂，說起來已經(jīng)好久好久好久沒見了呢轮蜕！之前一直忙著做其他事情去了（泛指學(xué)習(xí)一類），公眾號(hào)已經(jīng)落下好久好久了蝗锥。今天來寫點(diǎn)好玩的東西跃洛。
說起來，小編似乎就是做啟發(fā)式算法起家的终议。當(dāng)時(shí)記得老師是這么跟我說的汇竭，啟發(fā)式算法這東西很簡單，你不需要基礎(chǔ)穴张，有高中基礎(chǔ)就夠了（其實(shí)他想說的是初中……）细燎。后來小編一直在學(xué)這個(gè)東西，做了三四年了皂甘，用啟發(fā)式算法做過的大大小小的project已經(jīng)不記得有多少了玻驻，所以還算得上有一點(diǎn)點(diǎn)經(jīng)驗(yàn)。
因此今天就來寫寫偿枕，怎樣實(shí)現(xiàn)一個(gè)比較高效的啟發(fā)式算法吧~
二璧瞬、何為高效？
說到這個(gè)詞渐夸，相信大家一定不陌生嗤锉。高效意思就是達(dá)到相同效果或者更好的效果時(shí)，使用的時(shí)間更短墓塌，所需要的資源更少瘟忱。就拿小編來說，由于小編特別笨苫幢，學(xué)一樣?xùn)|西需要花一周的時(shí)間访诱，而群里的小伙伴只需要一天的時(shí)間就能學(xué)會(huì)。那么這位小伙伴是要比我高效的韩肝。
同樣的對(duì)于一個(gè)啟發(fā)式算法而言触菜，不同人實(shí)現(xiàn)出來，即使是使用同一編程平臺(tái)達(dá)到同樣的效果伞梯，運(yùn)行時(shí)間也會(huì)千差萬別玫氢，相差幾倍甚至幾十倍帚屉。這樣說出來大家可能還沒啥感覺，那么放一下我們之前做過的一些數(shù)值實(shí)驗(yàn)大家直觀感受下吧~
這是某個(gè)Java實(shí)現(xiàn)的求解VRP類問題的算法代碼漾峡，兩個(gè)算法都達(dá)到了同樣的效果攻旦，只不過綠色曲線對(duì)應(yīng)的算法在計(jì)算過程中去除了相關(guān)冗余，可以看到運(yùn)行時(shí)間直線下降生逸。根據(jù)我們的統(tǒng)計(jì)牢屋，消除冗余計(jì)算后可使計(jì)算時(shí)間降低約83%，對(duì)于工業(yè)化生產(chǎn)而言槽袄，提升哪怕一個(gè)小數(shù)點(diǎn)都能帶來巨大的收益烙无，何止是83個(gè)百分點(diǎn)呢。怎么說呢遍尺，這簡直是A small step forward截酷，one step civiliazation。
三乾戏、放碼過來迂苛？
不要一上來就是寫代碼，不加思考就上手寫代碼鼓择，你只會(huì)搓一坨屎山出來三幻，自己坑害自己。開始寫代碼之前一定要構(gòu)思好算法的整體架構(gòu)呐能，解的表示方式念搬，如何快速得到鄰居解等。建議是思考的時(shí)間一定要占總時(shí)間的一半以上摆出。
其實(shí)思路清晰寫代碼是非忱驶玻快的，比如每次在寫代碼的時(shí)候我都會(huì)先寫好注釋懊蒸，比如：
//1. 先獲取所有可行點(diǎn)的信息
//2. 對(duì)點(diǎn)按照成本進(jìn)行排序
//3. 貪心將各個(gè)點(diǎn)插入到解中
然后寫的時(shí)候我只需要按照這個(gè)思路往下走就可以了荣倾，這就跟你寫小學(xué)生作文一樣悯搔，起床刷牙到公園看鯨魚骑丸，一定要思路清晰。
四妒貌、鄰居解如何計(jì)算通危？
到了今天的核心問題，我們都知道灌曙，鄰域搜索過程中菊碟，鄰居解與當(dāng)前解相比往往只有細(xì)微的變化，因此迭代過程中絕大部分變量不需要重新計(jì)算在刺，消除了冗余計(jì)算逆害，可大大提高鄰域搜索效率头镊，降低運(yùn)行時(shí)間。聽不懂嗎魄幕？沒關(guān)系相艇，我舉例子，慢慢給你講解纯陨。
下面是一個(gè)VRP問題（沒有TW哦）的一個(gè)初始解
為了方便表示我們用
其中各條路徑的cost又可以表示為：
因此最后解的計(jì)算方式為：
為了方便比較我們將這種計(jì)算解cost的方式稱為
Algorithm1。
算一下量愧，Algorithm1在計(jì)算時(shí)遍歷了所有的客戶點(diǎn)胧弛，對(duì)于N個(gè)客戶點(diǎn)的解而已，算法的復(fù)雜度為O(N)侠畔，嗯结缚！還不賴。
好了現(xiàn)在解
可以看到該move就是將客戶19從路徑
1后面。
現(xiàn)在生成了一個(gè)鄰居解喘落，得知道這個(gè)鄰居解是好還是壞對(duì)吧茵宪，那么我們得比較
Algorithm1算出了利用Algorithm1對(duì)
優(yōu)化一下
觀察上面的解
微小的改變，整個(gè)解中有4條路徑团甲，只有兩條路徑發(fā)生了改變逾冬，因此在上面的式子中，只有
這樣一來，只需要計(jì)算變動(dòng)的路徑即可身腻，就不用重新計(jì)算所有路徑了产还。大大降低了鄰居解的計(jì)算時(shí)間復(fù)雜度。
進(jìn)一步優(yōu)化
細(xì)細(xì)觀察一下
紅色實(shí)線標(biāo)出來了，紅色虛線標(biāo)出來去件，那么我們將這兩條式子帶入下面的式子：
即可得到：
這個(gè)時(shí)間復(fù)雜度為
可能大家對(duì)這個(gè)
- 如果每個(gè)鄰居解你都使用
Algorithm1重新算一遍僻焚，那么大概要算5000*100=50萬次允悦。 - 如果你用優(yōu)化過的計(jì)算方法，只需要算5000*1=5000次虑啤。
這個(gè)差距有多大隙弛，大家動(dòng)動(dòng)屁股都知道了。當(dāng)然了咐旧，這只是理論上的分析驶鹉。實(shí)際上的差距和編程環(huán)境以及實(shí)現(xiàn)方式等都有很大關(guān)系绩蜻，但是只要差距超過10倍以上铣墨，都是能很明顯的感覺出來的。
五办绝、小結(jié)
關(guān)于如果去除冗余伊约，不是說一套方法通用的姚淆，需要根據(jù)算法工程師根據(jù)問題的特性，設(shè)計(jì)合適的解結(jié)構(gòu)屡律，再對(duì)鄰域算子進(jìn)行降冗余的思考與實(shí)現(xiàn)腌逢。降冗余的操作比較適合鄰域搜索類的啟發(fā)式算法，因?yàn)檫@類算法顯著特點(diǎn)就是鄰居解相比較當(dāng)前解而言超埋，變化非常細(xì)微搏讶。
當(dāng)然了，這需要豐富的編程經(jīng)驗(yàn)霍殴，所以大家有時(shí)間還是好好磨練下吧媒惕，相應(yīng)的學(xué)習(xí)代碼請(qǐng)點(diǎn)擊頭像獲取哦。
