程序员经验分享-hwhale

如何在图中找到哈密顿循环

2023-12-03

我正在尝试解决哈密顿循环问题。我能够找到一条包含所有顶点的路径，但无法完成循环。

有人可以为我提供一种找到循环的算法吗？


确定图是否有哈密​​顿循环是一个 NP 完全问题。这意味着我们可以check如果给定路径是多项式时间内的哈密顿循环，但我们不知道有任何多项式时间算法能够finding it.

唯一可用于查找哈密顿循环的算法是指数时间算法。他们之中有一些是

  • 暴力搜索
  • 动态规划
  • 您可以找到其他指数但更快的算法here
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Algorithm

Graph

如何在图中找到哈密顿循环 的相关文章

  • Diamond-Square 算法的平滑问题

    我正在使用菱形方形算法来生成随机地形 它工作得很好 除了我让这些大圆锥形状要么伸出或伸入地形 问题似乎在于 时不时会有一个点被设置得太高或太低 Here is a picture of the problem And it can be b

  • 在Python中确定句子中2个单词之间的邻近度

    我需要确定 Python 句子中两个单词之间的接近度 例如 在下面的句子中 the foo and the bar is foo bar 我想确定单词之间的距离foo and bar 确定之间出现的单词数foo and bar 请注意 该词

  • 比较两棵树的伪代码

    这是我遇到过几次的问题 并且不确信我使用了最有效的逻辑 例如 假设我有两棵树 一棵是文件夹结构 另一棵是该文件夹结构的内存 模型 我希望比较两棵树 并生成一棵树中存在的节点列表 而不是另一棵树中存在的节点列表 反之亦然 是否有公认的算法来处

  • 如何用线条在一个Excel散点图中绘制多个分组数据

    我在 Excel 中的一张图表 带线的散点图 中绘制分组数据 按索引 时遇到一些困难 我将非常感谢您的帮助 我的数据分为三列 第一列是数据或组的索引 即每组数据的唯一编号 第二列是时间 第三列是数据 Group Time Data 1 1

  • 如何使用networkx删除有向图中的所有相关节点？

    我不确定我的问题的正确术语是什么 所以我只会解释我想做的事情 我有一个有向图 删除节点后我希望所有独立相关的节点也被删除 这是一个例子 假设我删除节点 11 我希望节点 2 也被删除 在我自己的示例中 它们将是 2 以下的节点 现在也必须删

  • 您将如何显示/布局企业应用程序之间的数据流？

    我的雇主是一家大型瑞士电信公司 我们有许多系统用于为不同任务传输数据 例如性能管理 故障管理 配置管理等 为了向 管理 尖头等 解释这些系统如何交互 我将有关数据流 格式 协议的信息收集到 数据库 逗号分隔的说服者 中 然后为 Graphv

  • java中的Anagram算法

    我想做字谜算法但是 这段代码不起作用 我的错在哪里 例如 des 和 sed 是字谜 但输出不是字谜 同时我必须使用字符串方法 不是数组 public static boolean isAnagram String s1 String s2

  • 使用 Haskell 绘制图表

    是否可以使用 Haskell 绘制一个简单的图表 你们中的任何人都可以告诉我该怎么做吗 该图应至少包含 3 个点 Haskell 图表 https github com timbod7 haskell chart似乎不错 The wiki

  • 打印从 1 到 100 的质数

    此 C 代码打印出以下素数 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 但我不认为这就是我的书所希望的写作方式 它提到了一些关于数字的平方根的内容

  • n的渐近增长选择下限(n/2)

    如何找到 n select Floor n 2 的渐近增长 我试过 使用扩展并得到它等于 n n 1 floor n 2 1 n floor n 2 知道我该如何从那里去吗 感谢任何帮助 更喜欢提示而不是答案 我同意上面的答案 但想提供更多

  • 用于时间线数据的类似 gnuplot 的程序

    我正在寻找一个类似 gnuplot用于在时间轴中绘制数据图表的程序 类似 gnuplot 在 Linux 上运行 命令行功能 GUI 对我帮助不大 可编写脚本的语法 输出为 jpg png svg 或 gif 输出应该是这样的 set5 s

  • 仅使用两个变量交换两个数字

    它如何执行交换 a a b b a b a b a 我不同意把它换成书 书中的选项包括 a和b的值的补集 否定和b 希望这些选项也不能满足它 正确的算法应该是 a a b b a b a a b

  • 读取4个点的坐标。他们做一个正方形吗？

    我计算点之间的距离 如果距离相等 则点构成一个正方形 否则不 仅当我按以下顺序读取坐标 A x y B x y C x y D x y 或相反时 我的代码才有效 但是如果我这样读 例如 A x y B x y D x y C x y 它将不

  • 大小为 n 的数组，其中一个元素 n/2 次

    给定一个由 n 个整数组成的数组 其中一个元素出现超过 n 2 次 我们需要在线性时间和恒定的额外空间中找到该元素 YAAQ 又一个数组问题 我有一种偷偷的怀疑 这类似于 在 C 中 We don t need an array publi

  • iOS绘图3D图形库[关闭]

    Closed 这个问题不符合堆栈溢出指南 help closed questions 目前不接受答案 我正在搜索一个可以帮助我绘制 3D 图表的库 我想要类似的东西这一页 http www math uri edu bkaskosz fla

  • 找到一个恰好出现了 N/2 次的数字

    这是我的面试问题之一 给定一个包含 N 个元素的数组以及元素出现的位置正好 N 2次 其余 N 2 个元素是unique 您如何找到运行时间更好的元素 请记住 元素未排序 您可以假设 N 是偶数 例如 input array 10 2 3

  • javascript - 找到在一定限制下给出最大总和的子集（子集总和）

    我有一个包含一些整数值的数组 我需要获取它们的子集 该子集给出小于给定值的最大总和 假设我有这个数组 40 138 29 450 我想获得该数组的一个子集 使总和最大化 但低于用户给出的限制 比如说 250 在这种情况下 它应该返回 139

  • std::__gcd 和 std::gcd 有什么区别？

    Many https www geeksforgeeks org stdgcd c inbuilt function finding gcd websites https codeforces com submissions Madiyar

  • 单词预测算法

    我确信有一篇关于此问题的帖子 但我找不到提出这个确切问题的帖子 考虑以下 我们有字典可供使用 我们收到了许多单词段落 我希望能够根据此输入预测句子中的下一个单词 假设我们有几个句子 例如 你好 我的名字是汤姆 他的名字是杰瑞 他去了没有水的

  • 为什么我的 Python 散点图不起作用？

    我使用 pylab 创建了一个非常简单的散点图 pylab scatter engineSize fuelMile pylab show 该程序的其余部分不值得发布 因为正是该行给我带来了问题 当我将 散点 更改为 绘图 时 它会绘制数据图

随机推荐

热门标签