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