标签: hamiltonian-cycle

我指的是Skienna的算法书.

测试图是否G包含a的问题Hamiltonian path是NP-hard,哈密顿路径P是一个只访问每个顶点一次的路径.与汉密尔顿循环问题不同,从结束顶点到P的起始顶点不一定有G的边缘.

给定有向非循环图G(DAG),给出O(n + m)时间算法来测试它是否包含哈密顿路径.

我的方法,

我打算用DFS和Topological sorting.但我不知道如何将这两个概念联系起来解决问题.如何使用拓扑排序来确定解决方案.

有什么建议？

什么是在无向图中找到哈密顿循环的动态规划算法？我在某处看到存在一种具有O(n.2^n)时间复杂度的算法.

我正在阅读用于查找最小生成树的算法(在加权图的情况下)以及查找图是否具有哈密顿路径(这取决于哈密顿循环的存在).我把一切搞砸了.那哈密顿路径和生成树之间的区别是什么？两者都覆盖图中的所有顶点.虽然我们可以使用有效的算法来查找生成树(可能是最小的生成树),但为什么我们不能找到哈密顿电路的算法？我们可以继续一次添加和删除一个边缘,直到我们达到一个周期,也许,我们可以找到一个哈密顿周期？

我有一个连接的,非定向的图,有N个节点和2N-3边.您可以考虑将图形构建到现有的初始图形上,该图形具有3个节点和3个边缘.每个节点都添加到图表上,并与图中的现有节点有2个连接.当所有节点都添加到图形中时(总共添加N-3个节点),构建最终图形.

最初我被问到,这个图中可以访问一次的最大节点数是多少(初始节点除外),即给定图的最大哈密顿路径中包含的最大节点数是多少？(好吧,说最大哈密顿路径不是一个有效的短语,但考虑到问题的本质,我需要找到一次访问的最大节点数,并且行程在初始节点结束.我认为它可以被认为是子图是哈密顿量的,并且由最大节点数组成,因此最大可能的哈密顿路径).

由于我没有被要求找到路径,我应该首先检查是否存在给定数量节点的哈密顿路径.我知道平面图和循环图 s(C _n)是哈密​​顿图(我也知道哈密​​顿图的Ore定理,但我将要研究的图不会是一个概率很大的密集图,因此使得Ore定理很漂亮在我的情况下没用.)因此,我需要找到一种算法来检查图是否是循环图,即是否存在包含给定图的所有节点的循环.

由于DFS用于检测周期,我认为对DFS的一些小操作可以帮助我检测我正在寻找的内容,如跟踪已探索的节点,最后检查所访问的最后一个节点是否与初始节点有连接.不幸的是,我无法用这种方法取得成功.

我尝试的另一种方法是排除节点,然后尝试从其他相邻节点开始到达其相邻节点.根据所选择的相邻节点,该算法可能无法给出正确的结果.

我几乎被困在这里.你能帮我想一下另一个算法来告诉我图是一个循环图吗？

编辑

我在评论的帮助下意识到了(感谢你nm):

循环图由单个循环组成,具有N个边和N个顶点.如果存在包含给定图的所有节点的循环,那就是哈密顿循环. - nm

我实际上正在寻找哈密尔顿路径,我不打算这样做:)在第二个想法,我认为在构建它时检查图的哈密尔顿性质将更有效,这也是我也在寻找:时间效率.

经过一番思考后,无论节点数量是多少,由于节点添加标准,图形似乎都是哈密顿量.问题是我无法确定,我无法证明这一点.以这种方式添加节点,即添加具有将添加的节点连接到现有节点的2条边的新节点,是否会改变图的哈密顿特性？如果它不改变汉密尔顿属性,怎么会这样？如果它确实改变了,那又如何呢？谢谢.

编辑#2

我再次意识到,按照我描述的方式构建图形可能会改变哈密顿特性.考虑如下输入:

1 3
2 3
1 5
1 3

这些输入表示第4个节点连接到节点1和节点3,第5个节点连接到节点2和节点3...

第4和第7个节点连接到相同的节点,从而将可以访问的最大节点数减少一次,如果我检测到这些冲突(不包括输入,例如3 3,这是您建议的示例)因为问题表明新添加的边连接到其他2个节点)并且从N开始降低最大节点数,我相信我可以得到正确的结果.

看,我不选择连接,它们是给我的,我必须找到最大值.节点数量.

我认为在构建图形时计算相同的连接并从N中减去相同连接的数量会得到正确的结果吗？你能证实这个或者这个算法存在缺陷吗？

我正在寻找一种有效的算法,能够在双向N*M网格中找到尽可能随机的哈密​​顿路径.

有谁知道我在哪里可以找到,或者如何构建这样的算法？

我已经找到了一种有效的方法(见下图).这里的最终结果是哈密顿循环.删除随机边缘将使其成为哈密尔顿路径.该算法是有效的,但不提供足够的随机性.这种方法总是让路径的起点和终点彼此相邻,而我希望将它们放在随机位置. 空间填充曲线http://img593.imageshack.us/img593/8060/sfc.png 图片取自http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&rep=rep1&type= PDF格式

我知道之前有人问过,但我没有在任何帖子中找到答案.有人可以建议我一个算法,列出图中的所有汉密尔顿路径？

一点背景:我正在研究一个问题,我必须列举每个汉密尔顿路径,做一些分析,然后返回结果.为此,我需要能够列举所有可能的哈密尔顿路径.

谢谢.

我在期中考试时遇到了一个问题.任何人都可以澄清答案吗？

问题A:给定一个完整的加权图G,找到一个最小权重的汉密尔顿游.

问题B:给定一个完整的加权图G和实数R,G是否具有最多R的哈密顿巡回训练？

假设有一台机器可以解决B.我们可以多少次调用B(每次给出G和实数R),用该机器解决问题A？假设G中边缘的总和达到M.

1)我们不能这样做,因为有无数的状态.

2)O(| E |)次

3)O(lg m)次

4)因为A是NP-Hard,这是不可能做到的.

我有相对较小的(40-80个节点)立方(3-regular)平面图,我必须决定它们的汉密尔顿性.我知道这个任务是NP完全的,但我希望渐近指数时间算法对我感兴趣的图形大小来说非常快.

有许多谜题是经典的"7 Bridges of Konigsberg"拼图的变体,你必须在没有两次使用门的情况下找到通过一组房间的路线.

这是一个没有解决方案的例子.

...... 正如你在这里看到的那样,它是一个有一点解决方案的解决方案.

我对解决这类问题的程序化方法感兴趣,虽然有很多方法可以确定房间和门的特定配置没有解决方案,但我有兴趣计算要访问的门列表来解决难题.查看问题的一种方法是将其配置转换为图形并求解哈密顿量.然而,这种问题需要加强不优雅的逻辑,因为禁止"U-Turns"的约束.

我在几分钟内修复了一个解决方案以显示问题.这是一个蛮力的解决方案,将"房间"分组,增加的不变量,你不能从一个"门"移动到同一个房间的另一个"门"(这将需要做一个掉头).

我觉得必须有一个更好的抽象来表示这个问题,而不是诉诸于以下"技巧":

1. 当路径刚刚来自那个房间时,有额外的逻辑来移除同一房间内的门作为有效选择.

2. 生成与输入房间配置不同构的图形.

3. 过滤所有不满足掉头约束的配置.(#1的变体)

是否存在解决这类问题的现有文献,如果是这样,他们的结论是什么？房间问题是否与最知名的图算法采用的方法基本不一致,因此它需要这种特殊的逻辑？如果有一个更好的解决方案不是对图表的转换,我也很乐意听到这一点.

这是现有的代码,它们起作用,组代表第一个问题,被注释掉的组代表后一个问题:

// I renamed "groups" to rooms to make the code more clear.
var rooms = {
    1: ['A','B','C','D'],
    //1: ['A','B','C','D','P'],
    2: ['E', 'D', 'F', 'G'],
    3: ['F','I','J','H'],
    //3: ['F','I','P','J', 'H'],
    4: ['I', 'M', 'N', 'O'],
    5: ['C','J','M','L','K'],
    OUTER: ['A', 'B', 'E', 'G', 'H', 'O', 'N', 'L', 'K']
}

class Graph {
    constructor(rooms) {
        // This is a map of a door …

我正在使用统一成本网格,只允许在正交方向上移动.这被用作游戏蛇的基地,蛇必须不断移动并尝试在棋盘上吃苹果.使用经典的AStar算法完成食物的位置和避免碰撞,以找到蛇头和食物之间的最短路径.然而,这种方法有时导致蛇去食物,导致它没有通往下一个食物的明确路径.蛇最终卡在一个不规则形状的矩形中,此时没有未来的模拟.

我的问题是:有没有办法找到不规则矩形内最长的动作链,以便保持最长的活动,并且可能让蛇的尾巴阻挡通往下一个食物的路径？我看过汉密尔顿算法试图访问所有节点,但似乎没有不规则形状的解决方案.解决方案不一定是完美的,但它应该总是试图让蛇最好的机会逃离陷阱.

有什么想法吗？