※ 引述《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://webptt.com/cn.aspx?n=bbs/Math/M.1708759467.A.875.html 以前的我也会当成两种类型, 但现在我比较是把它当成同一类问题的两种计算顺序 一般递回 (及记忆化) 是由大问题起往小问题拆, 动态规划则是由小问题起往大问题盖 哪一个好写就去做哪一个 会当成两种类型可能就只是因为计算顺序不同的关系吧 ※ 编辑: LPH66 (123.194.181.180 台湾), 02/24/2024 16:03:08