迪傑斯特拉演算法(Dijkstra)的本質是貪心還是動態規劃?

01-14

老師說這是貪心可是我個人更傾向於動態規劃

貪心是一種特殊的動態規劃，動態規劃的本質是獨立的子問題，而貪心則是每次可以找到最優的獨立子問題。

貪心和動歸不是互斥的，而是包含的，貪心更快，但約束更強，適應範圍更小。

動歸和bfs的關係也是一樣的。

展開一點講，在求解最優化問題時，有多個解。而求解的過程類似一個樹，我們稱之為求解樹。

一般的求解樹真的是一棵樹，所以我們只能用bfs來搜索，頂多剪枝。

有些特殊的求解樹，中間很多結點是重合的，結點個數比所有搜索分支的個數少很多個數量級。這類問題較特殊，我們可以保存中間的搜索過程。而記憶化搜索和動態規劃本質上就是一個東西，快就快在可以不用重複計算很多中間結果（所謂的最優子問題）。

還有一些特殊的求解樹，更特殊，它們不止有很多重複結點，而且每次選擇分支的時候，我們可以證明只要選擇一個分支，這個分支的解就一定比其他選擇更優。這類問題就是貪心了，

所以bfs，dp，貪心三個方法都是解決最優化問題的方法，根據問題的不同，約束越大的問題可以用越快的方法，越慢的方法可以解決的問題越普適。

=========================更新===========================

換一種思路

動態規劃的狀態轉移函數，可以抽象成這樣一種函數：

f(x)=g(f(x1), f(x2), f(x3), ... f(xn))

其中f就是我們說的獨立問題，每個f都有一個唯一值，也就是沒有後效性。

貪心也是這個函數，但可以證明：

f(xi) &>= f(x1|x2|...|xn)

那麼我們就不用再去計算除了f(xi)以外的任何子狀態了，所以就更快

而標準的bfs，雖然也有

f(x)=g(f(x1), f(x2), f(x3), ... f(xn))

但是因為對於任意的f(x)，它的子問題f(xi)的輸入狀態xi都不同（換一種思路也可以說f(xi)在不同的路徑下值都不同，本質上是我們怎麼定義xi，到底是狹義的參數還是廣義的狀態），所以無法使用內存去換取時間，就只能去遍歷所有狀態了。

我認為 Dijkstra演算法的本質是廣度優先搜索，

而此處的廣度是定義在路程的cost之上的。

（就好比從圓心處向外擴散一個圓環，首次碰到的就是最近）

動態規劃泛指，重疊子問題與原問題的推算關係（學名：動態轉移方程），

貪心是極端情況的動態規劃，子問題獨一選擇性。

Dijkstra演算法的分解思路是

到達某節點的cost最小路徑 --（從這裡面選）--&> { 到達其相鄰節點的cost最小路徑 }

獨一選擇性:

只挑選： Min {到達其相鄰節點的最短路徑}

結論：的確是貪心策略

一般意義上的貪心演算法在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的僅是在某種意義上的局部最優解。

Dijkstra演算法顯然是從整體最優考慮，求出的最短路徑，一定是整體最優解，這是和一般意義上的貪心演算法相悖的地方。而且Dijkstra演算法符合動態規劃的這一特性：待求解的問題分解為若干個子問題，前一子問題的解，為後一子問題的求解提供了有用的信息。在我看來，Dijkstra演算法更接近動態規劃。

從維基百科也可以看到這樣的說明：

From a dynamic programming point of view, Dijkstra"s algorithm is a successive approximation scheme that solves the dynamic programming functional equation for the shortest path problem by the Reaching method.

請看演算法導論第16章222頁的第三段。

我不知道你是不是在搞OI或者ACM

從OI/ACM上來說……這個必然會被認為是貪心……

動態規劃最重要的是狀態和轉移……dijk實在談不上有狀態……更不用提轉移了。

而貪心範圍就比較廣了，比如dijk就是沒次選去最近的進行擴展。

然而在方奇國家集訓隊《動態規劃》論文里最短路是當例題講的。。

貪心最優介於兩者之間雖然其中缺乏狀態但是還是有子問題解決的思路

典型的動態規劃。

這個演算法顯然可以得到全局最優，而不是每一步只做當前看來最好的決定，這一點就與貪心演算法不同。

事實上，這個演算法中每個結點的狀態可以看作當前這個點到起點的距離（或cost），搜索所有的點一步步更新狀態正是典型的動態規劃的過程，因為跳出更新的具體過程，更新結束後每個點的最終狀態就是形同fn=min｛fn-1 + cost｝這個函數的結果。

貪心演算法的實質是每次選出當前的最優解，不管整體，是基於一定假設下的最優解。

動態規劃是講問題拆分為多個子問題，通過狀態變換求解，dijkstra每一次的更新都是由前一狀態的最優解獲得的，符合子問題與狀態轉變的問題。

另外的確也符合基於複合權值的廣度優先搜索。

我個人理解，動態規劃是全局最優解包含局部最優解，貪心則是當下能選擇的最的最優解，但是貪心演算法不一定是全局最優解。

貪心演算法選擇的策略無後效性，從這一點來說，dijkstra算是貪心演算法

兩種方法都是由子問題的求解最終得到總問題的解。動態規劃主要是解決多階段決策問題，並且階段間存在著相互影響。貪心演算法則強調不對後面的選擇產生影響，解是各個子問題最優解的組合。最短路徑中問題中，dijkstra演算法將子問題劃分為從起點出發到各點的最短路徑，然後綜合得到最優解。

可以看一下演算法導論16章...動態規劃本身擁有貪心選擇的特性。

有沒有人可以簡單通俗的說一下迪杰特斯拉演算法的原理，以前做過，但不是很理解

A* search的特例。其本質是搜索方法。。。貪心同樣可以理解為A* search的特例......

貪心~~

我個人覺得，既是DP，也是廣搜……