科学网 › 标签 › 哈密顿回路

标签: 哈密顿回路

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

简单图的哈密顿回路答案: 热度 2 accsys 2016-3-22 18:40; 简单图的哈密顿回路答案姜咏江上次给出的简单图是哈密顿图，此图只能找到 2 条哈密顿回路。结果如下所示：图 1 解一图 2 解二 2016-3-22; 个人分类: 教学点滴|7009 次阅读|6 个评论

最小哈密顿图与非哈密顿图: 热度 1 accsys 2016-3-19 08:37; 最小哈密顿图与非哈密顿图姜咏江多连通图中将单路径用一个顶点代替，就可以得到最小的哈密顿回路和非哈密顿回路。 2016-3-19; 个人分类: 教学点滴|6717 次阅读|2 个评论

这100个顶点的哈密顿回路是如何求出的你想到了吗？: accsys 2016-3-13 21:15; 姜咏江随便给出一个顶点相互关联的图，是不是哈密顿图，只要找出哈密顿回路就可以了。下面这 100 个顶点的哈密顿回路，很快就可以求出来，你能够看出个究竟吗？粗实线是选择的路径。当作游戏来玩玩，是很有意思的事情。 2016 － 3 － 13; 个人分类: 教学笔记|4753 次阅读|0 个评论

150个顶点的图求哈密顿回路要若干年吗？: 热度 2 accsys 2016-3-8 19:52; 150 个顶点的图求哈密顿回路要若干年吗？姜咏江下面 150 个顶点的图求哈密顿回路，如果你掌握了方法，最多半小时可以搞定。有人说计算机求解 100 个顶点的哈密顿回路要好多年，是真的吗？图 1 原图图 2 求出的哈密顿回路图3 又解图4 再解此题各解差别较小，但已体现出哈密顿回路多解的特性。 2016-3-8; 个人分类: P/NP问题|4439 次阅读|3 个评论

两个哈密顿图回路的一些解: 热度 1 accsys 2016-3-6 22:07; 两个哈密顿图回路的一些解姜咏江上次给出的两个图是哈密顿图。下面是分别求出的 2 个不同回路。 2016-3-6; 个人分类: P/NP问题|4252 次阅读|2 个评论

判定哈密顿图: 热度 1 accsys 2016-3-4 19:08; 判定哈密顿图姜咏江判定一个图是不是哈密顿图，只要求出其哈密顿回路即可。有兴趣可研究一下下面的图是不是哈密顿图。 2016-3-4; 个人分类: 3SAT解法|4734 次阅读|1 个评论

P与NP问题的研究进展: 热度 1 accsys 2016-2-25 08:12; P 与 NP 问题的研究进展姜咏江自从 SAT 问题的子句消去法成功之后，我又转向了哈密顿回路的求解研究。我发现图的路径问题，同样可以转化为 SAT 问题来研究。所谓的哈密顿回路只不过是其 SAT 表达方式的一组有序全 1 特解而已。 1. 用数码 0 和 1 表示图在图的路径问题研究中，我发现将图的相邻顶点用数码 0 和 1 来表示，既简单，又明确。用 1 表示当前顶点，所有与之相邻的顶点用 0 表示。将每个顶点的这种表示做为一个子句，写到 SAT 表中（见表 1 和表 2 ），这就是图的 01 表示法。例如，将图 1（1）和图1（2）用 0 和 1 表达，则得到表 1 和表 2 的 SAT 表达式，最上面留出的一行用来标识顶点选取顺序。这种顶点选取顺序清楚地表达出了顶点到顶点间的路径。从表 1 和表 2 都可以看到， 01 表示的图所成 SAT 总有全为 1 的解。因而不难解释哈密顿回路问题是 SAT 问题解的条件特例。也就是说哈密顿回路的解一定是满足一定关联顺序条件的 SAT 全 1 解。表 1 图1（1）的SAT表示表 2 图1（2）的SAT表示 4 5 1 2 3 3 1 2 x 1 x 2 x 3 x 4 x 5 x 1 x 2 x 3 x 4 x 5 1 0 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 1 2. 求图路径的子句消去法在图的 01 表示 SAT 路径问题中，选择某一个顶点，就是将变量的值定为 1 。因为每个选择的顶点都要设定值为 1 ，选定变量的设定值就可以不写。我们不妨就用变量取值的位置来标注顶点选取的顺序。写上了顺序数，就代表选取了该顶点，没有顺序数的变量，就代表没有被选取。为了清晰体现子句消去法来求解图的路径，依据子句消去法，我们规定：路径上后面一个顶点确定之后，就将前面顶点的子句消去。以表 1 为例。我们选 3 号顶点为路径起始点。（ 1 ）找到 x3 值为 1 的子句（行），通过 0 值找到与这个顶点相邻的有 2 、 4 号顶点。（ 2 ）选择 2 、 4 号顶点的一个，并消去 x3=1 的子句（在此以底纹表示）。这里选的是 4 号顶点。（ 3 ）依据前面选定的子句，通过子句的 0 和 1 关联关系，如（ 2 ）去选择关联的顶点，直至不能够再选择为止或到达认定的终点。不难想象，如果全部顶点都能够被这种依据相邻的关系选中，并且可以确定最后选中的顶点与起始点相邻，那么该图就是一个哈密顿图，所选的闭合路径就是哈密顿回路。在得到哈密顿回路的时侯， SAT 的全部子句都会被消去（参考表 1 和图 1 （ 1 ））。不然，没有哈密顿回路， SAT 的子句也不会全部消去（参考表 2 和图 1 （ 2 ））。 3. 路径边消去法在图的路径问题研究中，我们可以从某点开始，除去起始点和终点之外，只将前面选择的顶点和关联边留下，其余的边都消去，这样就可以得到需要的路径（见图 2 和图 3 ）。如果我们要求解的是一条回路，那么起始点也是终点，最后要消去起始点所有未选中的边（见图 4 ）。很明显，图路径的边消去法，就是图 01 表示的子句消去法。 4. 求哈密顿回路依据子句消去法，并依据一定的规则就可以求出哈密顿回路。自然，当一个图不是哈密顿图时，也就求不出哈密顿回路。在客观上，这种方法找到了鉴别一个图是否是哈密顿图的方法。 SAT 的子句消去法是一种多项式时间复杂度的算法。图的边消去法求解哈密顿回路，也是一种多项式时间复杂度的算法。目前，本人对任意给出的图都能够求出是否有哈密顿回路，即可鉴别是否是哈密顿图。只是在理论证明上尚未完成。如有人愿意与本人一同合作研究，可以与我直接联系。邮箱： accsys@126.com 2016-02-24; 个人分类: P/NP问题|5372 次阅读|2 个评论

这个60个结点的哈密顿图求回路要多少时间？: accsys 2016-1-15 09:43; 这个 60 个结点的哈密顿图求回路要多少时间？给你一个 60 个结点的哈密顿图，用微软 Visio ， 15 分钟能够求出来吗？附上微软 Visio 文件。姜咏江 2016-1-15 附件： hmdhu.vsd; 个人分类: P/NP问题|2857 次阅读|0 个评论

科学网，攀登者的宿营地: 热度 4 Babituo 2015-1-25 13:01; 科学网，攀登者的宿营地 “围棋是一种哈密顿回路的构建比赛”，这是这几天看了科学网老杜的博客文章，让我联想起早些年研究电脑围棋的一些想法，让我有了这个新的感悟。老杜钻研哈密顿回路算法已经好多年了，写了好些博文介绍自己的成果。我知道，我的科学网的另一位博友杨真傻研究这个问题也很有心得，我正是通过杨真傻的博客链接找到老杜的。一直感觉科学网因为有这么一群人而可爱。他们，一直把科学网当作科学探险者的宿营地来享用，他们每个人都有自己的探险目标，他们不怕失败，不怕出错，持之以恒的朝着一个自己认定的目标勇敢地攀登。他们肯讲真话，敢直接了当晒出自己的心得体会和成果，爱和同好热烈讨论攀登的技巧并相互学习借鉴。他们每天都在自己的领地内攀登着，每当间歇下来，便回到科学网这个宿营地，找几个伙伴一起攀谈切磋，取长补短，训练提高。攀谈中，他们诙谐轻松，谈吐真诚，有时还不乏幽默。在科学网上，他们不求自己的博文被“加精”，但对自己的博文多以原创精品的要求来认真创作，求的只是一两个知己。至于大众影响，他们认为，如果能有，可能也是大众的福祉，他们并不介意大众能分享到少数攀登者的乐趣，毕竟不是有很多人有机会并敢于亲身体验攀登的乐趣，但他们认为，这更应该是科学网编辑的责任和义务范围和对他们执业水平的考验。我知道的这样的博主已经有好些个了：邹晓辉，张学文，杨正瓴，姜咏江，杜立智等，还有好些我不是很熟知的，不敢列出他们的名字来。我很想给这群人一个称号：“科学网敢死队”，如果说这个称号有些太张扬，就叫“科学网探险队”也不错。我知道，我这个想法一定会引发某种被我鄙视的那种鄙视联想，说出来，就是不怕他们对号入座。我还清楚地记得，小学教室墙壁上挂着的那位先哲的话： “在科学的领域，没有平坦的大道，只有那些不畏艰险，努力攀登的人，才有希望到达那光辉的顶点” 。如果说，年轻时是被这句话中的“顶点”所激励的话，那么，如今，当人到或刚过中年，激励我们的不再是这句话中的“顶点”，而是“希望”。而究竟是什么希望能如此地吸引人？只有真正攀登过的人才能理解，那种 “绝地还可缝生” 的希望感受，是一种怎样的，无以言状的终极感受。有多少人能知晓，一个人，为这样的“希望”而生存，会比为“顶点”而生存，能更加持久地乐活着？还想和老杜多聊几句哈密顿回路和电脑围棋的关系问题。从事人工智能研究领域研究的人大都知道，电脑围棋是比电脑国际象棋更难征服的电脑博弈的高峰。这里面真的是乐趣无穷。闲暇时，我一直在寻找围棋背后的数学模型，实际上就是探寻围棋信息模型的本质。我相信，可以把围棋转化为某种真正的数学运算。尽管我职业上从事软件开发这么多年，也知道著名的哈密顿回路算法问题，但由于自己一直在职业上以解决实际问题为目标，加上这个问题不一般，研究起来很费精力，所以，没太敢对这个算法感兴趣。加上一直未能把它和业余爱好电脑围棋挂钩起来，所以，业余也没考虑研究它。看了老杜的博文，也不是直接受文字上哪句话的启发，反正头脑中忽然冒出个念头：围棋子在棋盘上做的一个“眼”，正是一条哈密顿回路。换个角度看围棋，两个棋手在下棋的时候，他们绝对想不到的是：实际上，他们是在和对手进行着一场哈密顿回路的搜寻和构建的比赛！电脑围棋只是以战胜人类选手为目标，而不是以证明PNP关系问题为目标，也就是说，如果职业围棋高手和算法高手来比拼哈密顿路径寻找和构建技能的话，加上算法高手和电脑配合的优势，谁输谁赢可说不定了，这可能意味着，哈密顿回路算法的研究可以在电脑围棋中试试水。有空时我会好好琢磨下这个问题，当然要向老杜多取经。能这样和博友探讨问题，这正是我喜欢科学网这个“宿营地”的原因，而不是每篇博文都被加精。我的博文只为有心者而写，“每篇博文至少都是自己的精品，但必须没有一篇被加精。”这或许已经是我在科学网上的一种享受和追求了，尽管这背后的想法有点坏，有点对不起编辑，真的还是很怕编辑会打破我的这个纪录。我发现，老杜似乎也享受着这种特殊待遇呢。最近流行挑战，我也向老杜挑战一把，看谁先被加精，先被加精者输。唯一的规则是：不能故意把博文写差，让编辑会感到以给你加精为耻，不违规反着做的，是“让对手四子”。输者欠对方一顿地方小吃，我知道武汉的小吃也蛮不错的哦。也欢迎其他还有资格的博主选手加入这场比赛。让我们也比赛一把，好波？呵呵。邱嘉文 2015-1月于珠海诚开智能; 个人分类: 电脑围棋|2420 次阅读|3 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 哈密顿回路

相关帖子

相关日志

关闭安全验证