srcmini

2020-03-04半瓶木阅读(1310)评论(0)赞(0)

本文概述 KMP算法的组成部分 前缀功能（Π） 运行时间分析 KMP赛事 运行时间分析 Knuth-Morris和Pratt介绍了用于字符串匹配问题的线性时间算法。通过避免与先前与要匹配的模式“ p”的某个元素进行比较所涉及的“ S”元素进...

2020-03-04半瓶木阅读(1519)评论(0)赞(0)

Rabin-Karp字符串匹配算法为模式以及要比较的文本的每个M字符子序列计算哈希值。如果哈希值不相等, 则算法将确定下一个M字符序列的哈希值。如果哈希值相等, 则算法将分析模式和M字符序列。这样, 每个文本子序列只有一个比较, 并且仅当哈...

2020-03-04半瓶木阅读(1095)评论(0)赞(0)

幼稚的方法测试模式P [1 ……. m]相对于文本T [1 …… n]的所有可能位置。我们依次对每个移位s尝试移位s = 0, 1 ……. n-m。比较T [s + 1...

2020-03-04半瓶木阅读(1153)评论(0)赞(0)

字符串匹配算法也称为“字符串搜索算法”。这是一类至关重要的字符串算法, 其声明为“这是一种在较大的字符串中找到多个字符串的地方的方法”。 给定n个字符的文本数组T [1 ….. n]和m个字符的模式数组P [1 … ...

2020-03-04半瓶木阅读(1490)评论(0)赞(0)

图G的顶点覆盖是一组顶点, 使得G中的每个边均入射到这些顶点中的至少一个顶点上。 决策顶点覆盖问题已被证明是NPC。现在, 我们要解决顶点覆盖问题的最佳版本, 即, 我们要找到给定图的最小尺寸的顶点覆盖。我们称这种顶点覆盖为最佳顶点覆盖C ...

2020-03-04半瓶木阅读(1309)评论(0)赞(0)

本文概述 介绍 绩效比率 介绍 近似算法是解决NP优化问题的一种方法。此技术不能保证最佳解决方案。近似算法的目标是在最长时间后的合理时间内, 尽可能地接近最佳值。这样的算法称为近似算法或启发式算法。 对于旅行推销员问题, 优化问题是找到最短...

2020-03-04半瓶木阅读(1640)评论(0)赞(0)

证明：- 子集和 顶点覆盖≤ρ子集覆盖 子集覆盖≤ρ顶点覆盖 子集和ϵ NP 1）子集和 定义：-为获得并集而获得完整图形G的所有边之后的边子集数, 这称为子集覆盖。 根据图G, 你已经创建了Subset Cover = 2的大小 2）顶点...