-
0 votesanswersviews
简单图中的递归回溯
想象下面的简单图： 每个实体都有一个索引开始计数0（所以A有索引0，B有索引1，依此类推） . A和B相连，所以它们之间的距离是1，所以f.e . A和D之间的距离是2，因为它们都与F相连 . 如何在java中实现一个方法，它接受两个索引和一个距离作为参数，并执行递归回溯，以便找出给定距离内两个给定实体是否可达？ 所以，如果我用参数（3,0,2）调用方法，那么它应该返回true，因为3是D而0... -
0 votesanswersviews
利用负循环查找图上两个节点之间零/负权重的路径
我真的很难在 Headers 中描述这个，但我会用更长的格式来试试 . 我真的很难解决这个问题，我不是在寻找答案，只需要一些帮助或一些特定的主题来阅读 . 我所拥有的是一个带有各种权重边缘的有向图，包括负数和正数 . 我试图做的是编写一个算法，该算法提供有两个位于图上的节点（并假设它们已连接）在它们之间找到一条路径，导致路径的总权重为零或负 . 该路径可以多次包括节点（希望允许路径偏移所包含边的正... -
0 votesanswersviews
图表回溯复杂性
我试图分析回溯图的复杂性，以便找到最长的路径 . 我的算法包括拓扑排序，然后从每个顶点回溯，以找到最长的路径 . 如果有帮助，算法基本上是：拓扑排序（G），为每个顶点计算彼此顶点的距离，返回最大距离 无论如何，我真的不知道回溯操作的最坏情况复杂性是什么 . 有什么建议？ 提前致谢！ -
8 votesanswersviews
生成集合[1]的所有分区
对于A = {1, 2, 3, ..., n}形式的集合。这称为集合A的分区，集合k<=n的元素遵循以下定理： a)A所有分区的并集是A b)A的 2 个分区的交集是空集(它们不能共享相同的元素)。 例如。 A = {1, 2,... n}我们有分区：{1, 2, 3} {1, 2} {3} {1, 3} {2} {2, 3} {1} {1} {2} {3} 这些理论概念已在我的算法教科书中... -
1 votesanswersviews
我的讲师给了我这些作为深度第一个问题的答案，我认为他们错了
Tree graph and search tree 问题是： 对于讲义中的图形，标记使用时搜索（生成）节点的顺序： a）深度优先搜索 . b）深度优先，回溯搜索 . c）广度优先搜索 . 这些问题的答案显然是， a）深度优先搜索 . a，b，d，d，e，l，c，f，h，n，p，q，z，j，m，z，k，q，p，q，z，z，c，f，h， n，p，q，z . b）深度优先，回溯搜索 . a... -
-1 votesanswersviews
使用递归查找所有k个子集
我试图找到一种方法来制作递归算法，该算法将给出一组数字（0 - > n）的所有k长度子集，但我不能将该列表作为参数发送给该函数 . 最终我想返回一个列表列表 我想从最后开始，使用某种DP . 我尝试过的东西都没有接近它 谢谢 -
6 votesanswersviews
在回溯方面解释BFS和DFS
Wikipedia about Depth First Search: 深度优先搜索（DFS）是用于遍历或搜索树，树结构或图的算法 . 一个从根开始（在图形情况下选择一个节点作为根）并在回溯之前尽可能地沿着每个分支进行探索 . So what is Breadth First Search? “选择起始节点的算法，检查所有节点回溯，选择最短路径，选择邻居节点回溯，选择最短路径，最终找到最佳路... -
2 votesanswersviews
在有向图中使用DFS进行循环检测绝对需要回溯吗？
我遇到了这个SO post，其中建议在有向图中使用DFS进行循环检测由于回溯而更快 . 在这里，我引用该链接： 深度优先搜索比广度优先搜索更有效，因为您可以更快地回溯 . 如果使用调用堆栈，它也更容易实现，但这依赖于不会溢出堆栈的最长路径 . 此外，如果您的图表是定向的，那么您不仅要记住您是否访问过某个节点，还要记得您是如何到达那里的 . 否则你可能会认为你已经找到了一个循环，但实际上你所拥有的... -
6 votesanswersviews
回溯和暴力搜索之间的差异
我目前正在学习算法课程，而且我很难理解蛮力搜索和回溯的确切定义 . 据我了解，以下情况属实： 暴力搜索（BFS）是一种算法，它计算问题的每个可能的解决方案，然后选择满足要求的解决方案 . 显式约束为每个选项提供可能的值（例如，选项1-3限于 {1, 2} ，选项4限于 {3, 4, 5} 等），这决定了搜索的"execution tree"的形状 . 隐式约束将不同... -
14 votesanswersviews
如何计算回溯算法的时间复杂度？
如何计算这些回溯算法的时间复杂度，它们是否具有相同的时间复杂度？如果不同怎么样？请详细解释并感谢您的帮助 . 1. Hamiltonian cycle: bool hamCycleUtil(bool graph[V][V], int path[], int pos) { /* base case: If all vertices are included ... -
0 votesanswersviews
回溯算法解决数独难题的时间复杂度
我正在实施一个回溯算法来解决数独谜题，我需要对算法进行实证分析 . 但是，我发现很难理解这种回溯算法的时间复杂度来解决数独谜题 . 数独板是一个9乘9的网格，因此每个空格可以取1-9的值，但它首先检查行，列，3x3框以查看是否安全，并且有m个空格 . 我逐行遍历网格寻找一个空格，然后循环编号1-9，检查哪个数字是安全的 . 如果数字是安全的，我把它放在那里然后再次调用我的函数（重复）来检查下一个空... -
0 votesanswersviews
使用递归和DP的最长公共子串
我正在尝试使用递归和DP找到两个字符串的最长公共子串 . 请注意，我不是指最长的连续子序列 . 所以，如果这两个字符串是 String s1 = "abcdf"; String s2 = "bzcdf" Longest Common Substring == "cdf" (not "bcdf"). Basically... -
-3 votesanswersviews
使用列表进行Prolog练习
如果有人帮助我进行下面的练习，我将不胜感激 如果我有prolog谓词 **split_list(Limit,List,High,Low) (split_list/4)** ，它有一个整数列表 List ，和一个整数 Limit ，"returns"列出 High 列表List的所有数据大于或等于 Limit ，列表Low低于 Limit 的数据 . 例如： ?- split_l... -
1 votesanswersviews
反向跟踪算法设计技术定义
我正在阅读有关回溯算法设计技术的文章 . 提到如下 . 回溯是蛮力方法的改进，它系统地在所有可用选项中搜索问题的解决方案 . 它通过假设解决方案由值的向量（v1，v2，...，vm）表示并且以深度优先的方式遍历向量的域直到找到解决方案来这样做 . 我对以上文字的质疑如下 . 作者用解决方案表示什么意思？ 作者对载体的含义是什么意思？ 谢谢你的澄清 . -
0 votesanswersviews
C中的Sudoku Solver程序在某些情况下会停止，我不知道为什么
我正在研究c中的程序，用于解决数独谜题的类 . 我们应该实现三种方法，首先它将正确的数字放在每个只有一个可能选择的方块中，重复直到它再也找不到 . 接下来它使用蛮力，在每个方格中放置尽可能少的数字 . 我有这两种方法 . 最后的方法是具有反向跟踪的强力，这是强力函数的一部分 . 它的工作方式与常规蛮力相同，除了它到达一个方形，它不能放置一个数字，它移动到前一个方格并放置下一个最高的数字 . 一旦实... -
0 votesanswersviews
数独回溯算法（Java）
我已经创建了一个数独求解器，它可以解决数独作为人类的可能性 - 通过检查与被检查的方格相对应的方块中的可能值 . （来源：http://pastebin.com/KVrXUDBF） 但是，我想创建一个随机的Sudoku生成器（来自空白网格），因此决定使用回溯算法 . 我理解回溯的概念，但我对一件事感到困惑： 一旦我知道某个解决方案不被允许，我怎么知道返回（和更改）哪个先前节点？我应该简单地返回上一... -
5 votesanswersviews
树结构中的递归回溯
我有这个算法，我想使用递归回溯实现图搜索 . 首先我的代码： public static boolean buildTree(GenericTreeNode<String> inputNode){ while(!interruptFlag) { try { Thread.sleep(200); } catch(InterruptedException e)... -
1 votesanswersviews
深度优先搜索和回溯拼图
我正在尝试在我的算法中添加深度优先搜索以找到Peg Solitaire游戏的解决方案 . 现在看来，当我的算法尚未找到解决方案时，它的退出速度太快了 . 如果电路板上只剩下1个挂钩，则会找到解决方案 . 下面是我的函数 findSolution() ，这是一个递归函数 . direction 包含在电路板上向上，向下，向左和向右移动的所有坐标 . doJump 在参数板上移动 . un... -
1 votesanswersviews
深入理解算法设计技术
“为给定的应用程序设计正确的算法是一项艰巨的任务 . 它需要一个重大的创造性行为，解决问题并从以太中解决问题 . 这比采取其他人的想法并修改它或将其调整为更难 . 让它变得更好 . 你可以在算法设计中做出的选择空间是巨大的，足以让你有足够的自由来悬挂自己“ . 我研究了几种基本的算法，如分而治之，动态编程，贪婪，回溯等 . 但是，当我遇到某些编程问题时，我总是无法认识到适用的原则 . 我想掌握算法... -
5 votesanswersviews
计算变化的Baktracking函数超过最大递归深度
我正在尝试编写一个函数来查找产生指定金额的所有可能的硬币组合，例如它计算所有可能的方式来从1p，2p，5p，10p的面额列表中更改2英镑的金额， 20P，50P，1pound，2pound . 我坚持这个，找不到合适的解决方案 . 我希望main函数是递归的，因为我想更好地理解递归 . 该算法必须回溯，如果在某个时刻发现的组合超过了要匹配的量，则程序应该返回到先前的步骤并从不同的点开始 . 到目前... -
1 votesanswersviews
哈密顿循环
使用回溯的哈密顿循环问题的最坏情况时间复杂度是多少？是O（n！）还是O（n ^ n）？因为我试图找出复杂性并且它出现了O（n×n！），它更像是O（n ^ n），而不是O（n！） .