動態(tài)規(guī)劃dp的使用條件(文件)
【正文】 的這個狀態(tài)。[例3]圖3（b）給出了七個點問題的解。由于必然經(jīng)過最右邊的頂點7，所以一條路(P1P2)可以看成兩條路（P17）與(P27)的結(jié)合。例如，階段[3,4]中的道路可以由階段[3,5]中的道路加一條邊45得出，而階段[3,5]的狀態(tài)卻無法由階段[3,4]中的狀態(tài)得出，因為Bitonic旅行路線要求必須嚴(yán)格地由左到右來旅行。在例1中我們看到，動態(tài)規(guī)劃將原來具有指數(shù)級復(fù)雜度的搜索算法改進成了具有多項式時間的算法。動態(tài)規(guī)劃的時間復(fù)雜度為O(n2)，搜索算法的時間復(fù)雜度為O(n!) ，但從空間復(fù)雜度來看，動態(tài)規(guī)劃算法為O(n2)，而搜索算法為O(n)，搜索算法反而優(yōu)于動態(tài)規(guī)劃算法。這個性質(zhì)并不是動態(tài)規(guī)劃適用的必要條件，但是如果該性質(zhì)無法滿足，動態(tài)規(guī)劃算法同其他算法相比就不具備優(yōu)勢。
法律信息相關(guān)推薦
鄂ICP備17016276號-1