徽标
联盟百科
通讯
下载应用,请到 Google Play
新! 在您的Android™设备上下载联盟百科!
自由
比浏览器更快的访问!
 

CYK算法

指数 CYK算法

CYK算法(Cocke–Younger–Kasami algorithm,縮寫為CYK algorithm)是由約翰·科克,Younger和共同研究出来大约发表于1965年的一个算法,它是一个用来判定任意给定的字符串~w \in \Sigma^* 是否属于一个上下文无关文法的算法。普通的回溯法(backtracking)在最坏的情况下需要指数时间才能解决这样的问题,而CYK算法只需要多项式时间就够了(~O(n^3) , n 为字符串 w 的长度)。CYK算法采用了动态规划的思想。 对于一个任意给定的上下文无关文法,都可以使用CYK算法来计算上述问题,但首先要将该文法转换成乔姆斯基范式。.

5 关系: 动态规划上下文无关文法乔姆斯基范式回溯法約翰·科克

动态规划

动态规划(Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和性质的问题,动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再根据子问题的解以得出原问题的解。 通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指數增長时特别有用。.

新!!: CYK算法和动态规划 · 查看更多 »

上下文无关文法

上下文无关文法(context-free grammar,縮寫為CFG),在计算机科学中,若一个形式文法 G.

新!!: CYK算法和上下文无关文法 · 查看更多 »

乔姆斯基范式

在计算机科学中,一个形式文法是 Chomsky 范式的,当且仅当所有产生规则都有如下形式: 这里的 A, B 和 C 是非终结符,α 是终结符(表示常量值的符号),S 是开始符号,而 ε 是空串。还有,B 和 C 都不可以是开始符号。 所有的 Chomsky 范式的文法都是上下文无关,反过来,所有上下文无关文法都可以有效的变换成等价的 Chomsky 范式的文法。 除了(在文法可能生成空串的时候包括的)可选规则 S → ε 是例外,Chomsky 范式的文法的所有规则都是扩张的,就是说在字符串的整个导出过程中,每个终结符和非终结符的字符串比起前面导出的字符串要么同样长度要么多出一个元素。长度 n 的字符串的导出总是精确的 2n-1 步长。 Chomsky 范式得名于诺姆·乔姆斯基,他是发明乔姆斯基层级的美国语言学家。.

新!!: CYK算法和乔姆斯基范式 · 查看更多 »

回溯法

回溯法(backtracking)是暴力搜尋法中的一种。 对于某些计算问题而言,回溯法是一种可以找出所有(或一部分)解的一般性算法,尤其适用于约束满足问题(在解决约束满足问题时,我们逐步构造更多的候选解,并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解,转而测试其他的部分候选解)。 在经典的教科书中,八皇后问题展示了回溯法的用例。(八皇后问题是在标准国际象棋棋盘中寻找八个皇后的所有分布,使得没有一个皇后能攻击到另外一个。) 回溯法采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:.

新!!: CYK算法和回溯法 · 查看更多 »

約翰·科克

約翰·科克(John Cocke,),又譯為約翰·考克、約翰·寇克,生於美國北卡羅來納州夏洛特,計算機科學家,在電腦架構及編譯器最佳化技術方面有重大貢獻,因此獲得圖靈獎。曾提出CYK算法。在他主導的IBM 801計劃中,首次採用RISC架構,因此被稱為RISC架構之父。.

新!!: CYK算法和約翰·科克 · 查看更多 »

传出传入
嘿!我们在Facebook上吧! »