Re: [幾何] 遞迴的定義

[LPH66 ( )]

※ 引述《glmm (綠島(俺是復活島島主))》之銘言：
: 推 LPH66       : 簡單類比: 費氏數列也是由前兩項推及下一項          02/22 18:25
: → LPH66       : 遞迴是定義型式, 跟計算順序無關                    02/22 18:26
原 PO 來信提到是否能將此種推論模式推及到圖形尋徑上

答案是可以的, 而且還是個很常見的招術

在演算法領域裡有個被稱做「動態規劃」的做法

其核心就是「把大問題分成許多個相同的小問題, 再由小問題做法構成大問題結果」

跟這裡的在問的概念是一模一樣的

一般教科書上會提要使用動態規劃有兩個要件:

「最佳子結構」－－小問題做法能構成大問題結果

「重覆子問題」－－拆成的許多小問題會有很多相同的小問題

當中「最佳子結構」這個性質其實跟遞迴定義是一模一樣的:

小問題做法能構成大問題結果, 反過來說大問題結果可由小問題做法推得

因此本質上, 動態規劃其實就只是一個計算遞迴定義的方式而已

====

一般來說, 圖形的各種尋徑問題很常有「最佳的長路徑其部份的短路徑也是最佳」的性質

換句話說就是「最佳的長路徑可由最佳的短路徑構成」

這正是上面提的「最佳子結構」性質

而實際的構成方法也很容易寫成一個遞迴定義:

較長的最佳路徑可由已知的較短的最佳路徑經過增補比較後獲得

因此此類問題最常使用動態規劃來進行解題

一個經典的例子是戴克斯特拉演算法 (Dijkstra's Algorithm)

這個演算法可以在幾乎任何一個講演算法的教材中找到

這正是原 PO 所問的將遞迴邏輯應用在圖形尋徑上的一個例子

初學這個演算法的人可能不容易看出它的做法和遞迴計算之間的相似性

但這只不過是計算順序不同造成的差別而已

--
  'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
  'That makes me sound a lot cooler then I was,' Ron mumbled.
  'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
                               -- Harry Potter and the Deathly Hollows, P.308

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.181.180 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1708759467.A.875.html
→ mantour     : 不過在討論演算法的時候通常會把遞迴和動態規劃
→ mantour     : 當作兩種類型嗎
以前的我也會當成兩種類型, 但現在我比較是把它當成同一類問題的兩種計算順序

一般遞迴 (及記憶化) 是由大問題起往小問題拆, 動態規劃則是由小問題起往大問題蓋

哪一個好寫就去做哪一個

會當成兩種類型可能就只是因為計算順序不同的關係吧
※ 編輯: LPH66 (123.194.181.180 臺灣), 02/24/2024 16:03:08
→ mantour     : 不過我感覺演算法有時候就是在研究計算順序改變
→ mantour     : 的影響和選擇較好的順序, 不過遞迴如果加讓記憶化
→ mantour     : 的確感覺就跟動態規劃差不多
→ mantour     : 加上
推 cuteSquirrel: 推 學到後面+實作 覺得是一體兩面
→ cuteSquirrel: DFS + 記憶畫搜索 ~ DP 都是互通的 看切入觀點
→ cuteSquirrel: 又可以從計算順序得到對稱的 上到下 和 下到上 解法