貝爾曼方程
貝爾曼方程（），也被稱作動態規劃方程（），由理查德·貝爾曼發現。貝爾曼方程是動態規劃這種數學最佳化方法能夠達到最佳化的必要條件。此方程將「決策問題在特定時間點的值」以「來自初始選擇的報酬及由初始選擇衍生的決策問題的值」的形式表示。藉這個方式將動態最佳化問題變成較簡單的子問題，而這些子問題遵守由貝爾曼所提出的「最佳化原理」。 貝爾曼方程最早應用在工程領域的控制理論及其他應用數學領域，而後成為經濟學上的重要工具。 幾乎所有可以用最佳控制理論…
标签：#动态规划
共 15 篇文章
动态规划
动态规划（，简称）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量…
最长公共子序列
最长公共子序列（LCS）是一个在一个序列集合中（通常为两个序列）用来查找所有序列中最长子序列的問題。这与查找最長公共子串的问题不同的地方是：子序列不需要在原序列中占用连续的位置 。最长公共子序列问题是一个经典的计算机科学问题，也是程序，比如Diff工具，和生物信息学应用的基础。它也被广泛地应用在版本控制，比如Git用来调和文件之间的改变。 定義 一个数列S，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则S称为已…
字符串近似匹配
在计算机科学中， 字符串近似匹配（通常俗称为字符串模糊查询)，是一种字符串查找技术，用来近似匹配一个模式，而不是完全匹配。 概览 匹配的近似度用如下方法来度量：把字符串转换成完全匹配的字符串所需要的基本操作步数。这个数量被称为编辑距离。通常基本操作有： 插入: cot → coat 删除: coat → cot 替换: coat → cost 这三个操作可以泛化为使用NULL字符来替换原来的字符（这里使用来表示）： 插入: co****…
自动换行
显示文字時，换行（line wrap）是指文字在一行已满後转到新行，使每行都可在視窗范围看到，不需水平滚动。 自动换行（word wrap）是大多数文字編輯器、文書處理器、和网页浏览器的附加功能。用于在行间或一行里的单词间隔处分行，不考虑單一单词超过一行长度的情况。 它通常是在看文档或打印的时候实时完成，所以没有储存或手工插入的换行代码。如果改变文档边缘，编辑器就会自动重排换行符的位置，保证全部文字都处于可见状态，或者给用户提供一些便捷…
维数灾难
维数灾难（，又名维度的詛咒）是一个最早由美國應用數學家理查德·贝尔曼在考虑优化问题时首次提出来的术语，用来描述当（数学）空间维度增加时，分析和组织高维空间（通常有成百上千维），因体积指数增加而遇到各种问题场景。这样的难题在低维空间中不会遇到，如物理空间通常只用三维来建模。 举例来说，100个平均分布的点能把一个单位区间以每个点距离不超过0.01采样；而当维度增加到10后，如果以相邻点距离不超过0.01小方格采样一单位超正方体，则需要10…
尼德曼-翁施算法
尼德曼-翁施算法（）是基于生物信息学的知识来匹配蛋白序列或者DNA序列的算法。这是将动态算法应用于生物序列的比较的最早期的几个实例之一。该算法是由 Saul B. Needlman和 Christian D. Wunsch 两位科学家于1970年发明的。本算法高效地解决了如何将一个庞大的数学问题分解为一系列小问题，并且从一系列小问题的解决方法重建大问题的解决方法的过程。该算法也被称为优化匹配算法和整体序列比较法。时至今日尼德曼-翁施算法…
萊文斯坦距離
莱文斯坦距离（）是编辑距离的一种。指两个字串之間，由一个转成另一个所需的最少编辑操作次数。 允许的编辑操作包括： 将一个字符替换成另一个字符 插入一个字符 刪除一个字符 俄羅斯科學家弗拉基米尔·莱文斯坦在1965年提出這個概念。 定义 如果分别用 |a| 和 |b| 表示 a, b 两个字符串的长度，那么它们的列文斯坦距离为 \operatorname{lev}_{a,b}(|a|,|b|)，它符合： :\qquad\operatorn…
最长递增子序列
在计算机科学中，最长递增子序列（）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。许多与数学、算法、、表示论相关的研究都会涉及最长递增子序列。解决最长递增子序列问题的算法最低要求O(n log n)的時間複雜度，这里n表示输入序列的规模。 例子 对于以下的原始序列 :0, 8, 4, 12, 2, 10, 6, 14, 1…
最大子数列问题
在计算机科学中，最大子数列问题（）的目标是在数列的一维方向找到一个连续的子数列，使该子数列的和最大。例如，对一个数列[−2, 1, −3, 4, −1, 2, 1, −5, 4]，其连续子数列中和最大的是[4, −1, 2, 1], 其和为6。 [[File:Maximum_Subarray_Visualization.svg|缩略图|展示[2, 3, -1, -20, 5, 10]子数列之和随着子序列起始位置变化而改变，图中每条线的一…
粘性解
数学中，粘性解是20世纪80年代早期由皮埃爾-路易·利翁和Michael G. Crandall作为对偏微分方程（PDE）经典解的扩展而引入的。粘性解在PDE的许多应用中作为解是非常自然的，例如优化控制中的一阶偏微分方程（哈密顿-雅可比-贝尔曼方程），微分对策中（Hamilton–Jacobi–Isaacs equation），前端演化问题（front evolution problem），还有二阶方程，例如在随机优化控制或随机微分博弈…
维特比算法
维特比算法（）是一种动态规划算法。它用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列，特别是在马尔可夫信息源上下文和隐马尔可夫模型中。 术语“维特比路径”和“维特比算法”也被用于寻找观察结果最有可能解释相关的动态规划算法。例如在统计句法分析中动态规划算法可以被用于发现最可能的上下文无关的派生（解析）的字符串，有时被称为“维特比分析”。 维特比算法由安德鲁·维特比于1967年提出，用于在数字通信链路中解卷积以消除噪音。此算法被…
史密斯-沃特曼算法
）]] 史密斯-沃特曼算法（Smith-Waterman algorithm）是一种进行局部序列比对（相对于全局比对）的算法，用于找出两个核苷酸序列或蛋白质序列之间的相似区域。该算法的目的不是进行全序列的比对，而是找出两个序列中具有高相似度的片段。 该算法由坦普尔·史密斯和迈克尔·沃特曼于1981年提出。史密斯-沃特曼算法是尼德曼-翁施算法的一个变体，二者都是动态规划算法。这一算法的优势在于可以在给定的打分方法下找出两个序列的最优的局部…
部分可觀察馬可夫決策過程
部分可觀察馬可夫決策過程（Partially Observable Markov Decision Process，缩写：POMDP），是一種通用化的馬可夫決策過程。POMDP模擬代理人決策程序是假設系統動態由MDP決定，但是代理人無法直接觀察目前的狀態。相反的，它必須要根據模型的全域與部分區域觀察結果來推斷狀態的分佈。 因為POMDP架構的通用程度足以模擬不同的真實世界的連續過程，應用於機器人導航問題、機械維護和不定性規劃。架構最早由…
最长公共子串
在计算机科学中，最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的，而子串却必须是。 样例 字符串"ABABC"，"BABCA"以及"ABCBA"的最长公共子串是"ABC"。其他的公共子串包括"A"、"AB"、"B"、"BA"、"BC"以及"C"。 ABABC ||| BABCA ||| ABCBA 问题定义 给定两个字符串，长度为m的字符串S以及长度为n的字符串T，求最长的子串…