快速排序去重？计算机专家与程序员的不同

热度 2 姜咏江 2016-8-1 05:46

快速排序去重？计算机专家与程序员的不同 姜咏江 n 个数排序算法时间复杂度是多少？一般程序员会脱口而出： O( n !) 。这是按照数学家的想法，从小到大，或者从大到小，一一比较得到的算法。如果你是一位计算机专家，不是一般的程序员，就可以用 O( n ) 时间复杂度得出结果。不 ...

个人分类: P/NP问题|4155 次阅读|9 个评论 热度 2

图01表示的性质及在同构中的应用

姜咏江 2016-4-11 10:58

姜咏江 将图的每个顶点用 1 表示，而与其相邻的顶点用 0 表示，这样形成的表就表示了一个顶点与周围顶点的相邻关系。全部顶点相邻关系的 01 表示就形成了一张行列数相同的表。 1. 图 01标准表 例如，图 1 的两个图直观来看，它们 ...

个人分类: P/NP问题|4394 次阅读|没有评论

你知道这些哈密顿图哪几个同构吗？

姜咏江 2016-4-10 08:11

你知道这些哈密顿图哪几个同构吗？ 姜咏江 顶点数相同，每个顶点的关联度（相邻顶点数）相同，都是哈密顿图，它们是否同构？下面的 8 个图，有哪几个同构？ 2016-4-10

个人分类: P/NP问题|5490 次阅读|没有评论

证明两个图同构的例题

姜咏江 2016-4-9 21:47

证明两个图同构的例题 姜咏江 下面的这两个图同构，用 01 同表法给出证明。提示：当前顶点用 1 表示，与其相邻顶点用 0 表示。 1. 用 0 和 1 表示图 1 图 1 的 01 表示如表 1 所示。复制表 1 的 01 表示，并去除表头顶点编号（见表 2 ），然后寻找两图顶点的一一对应关系。 表 1 图 ...

个人分类: P/NP问题|11356 次阅读|没有评论

哈密顿图同构的证明

姜咏江 2016-4-8 08:51

哈密顿图同构的证明 姜咏江 一个图是不是著名的哈密顿图？采用图的 01 表示方法可以做到。将当前顶点用 1 表示，与其相邻的顶点用 0 表示，并将它们放在一张表中，这就是图的 01 表示法。 1. 证明过程 要证明下面的图 1 和图 2 同构，只要将其中的一个图的 ...

个人分类: P/NP问题|4969 次阅读|没有评论

图同构01表示的多项式时间证明方法

姜咏江 2016-4-7 21:05

图同构01表示的多项式时间证明方法 姜咏江 人们一直认为图同构的证明是一个 NP 类问题（见附录），果真如此吗？运用本人发明的图 0 和 1 表示法（参阅 http://blog.sciencenet.cn/blog-340399-958453.html ），通过对一个图顶点的排列，就能够证明两个顶点和边数都相同的图是否同构。 下面给个例子说明证 ...

个人分类: P/NP问题|5228 次阅读|没有评论

子句消去法如何破解P与NP难题

热度 4 姜咏江 2016-3-9 10:47

子句消去法如何破解 P 与 NP 难题 姜咏江 子句消去法是能够在多项式时间求出 SAT 问题满足解的一种算法。也就是说斯提芬 . 库克理论认定的 NP-complete 问题之 3-SAT 问题，实际是可以在多项式时间求出解的 P 类问题。依据 NP-complete 问题的定义，就可以得出 P=NP 。我以前写出的子句消去法博文，分成了若干篇， ...

个人分类: P/NP问题|3829 次阅读|12 个评论 热度 4

150个顶点的图求哈密顿回路要若干年吗？

热度 2 姜咏江 2016-3-8 19:52

150 个顶点的图求哈密顿回路要若干年吗？ 姜咏江 下面 150 个顶点的图求哈密顿回路，如果你掌握了方法，最多半小时可以搞定。有人说计算机求解 100 个顶点的哈密顿回路要好多年，是真的吗？ 图 1 原图 图 2 求出的哈密顿回路 图3 又解 ...

个人分类: P/NP问题|4420 次阅读|3 个评论 热度 2

关联度全是3的图求哈密顿回路

姜咏江 2016-3-8 18:25

关联度全是 3 的图求哈密顿回路 姜咏江 2016-3-8

个人分类: P/NP问题|2427 次阅读|没有评论

本页有 1 篇博文因作者的隐私设置或未通过审核而隐藏