问题标签 [backtracking]

权重顺序如何影响回溯算法中的计算成本？节点和搜索树的数量是相同的，但是当它是无序的时，它需要更多的时间，所以它正在做一些事情。

谢谢！

我正在用 Java 为 9x9 网格编写数独求解器。

我有以下方法：

• 打印网格

• 用给定的值初始化电路板

• 测试冲突（如果相同的数字在同一行或 3x3 子网格中）

• 一种逐个放置数字的方法，这需要最多的工作。

在我详细介绍该方法之前，请记住，我必须使用递归来解决它，以及回溯（以此处的小程序为例http://www.heimetli.ch/ffh/simplifiedsudoku.html）

另外，我通过垂直向下移动来解决这个数独，从左上角开始，通过第一列，然后通过第二列，等等。

到目前为止，我有以下内容：

我标记 BACKTRACKING 的地方是我认为我的代码的其余部分需要去的地方。

我想到了一些类似的东西：

• 如果值为 10，则将该值设置回零，返回一行，然后将该值增加 1

由于以下几个原因，这种回溯“策略”并不完全奏效：

1. 如果前一行是一个给定的值怎么办（也就是我不应该增加或触摸它，而是回到我放在那里的最后一个值）

2. 如果之前的值是 9 怎么办？如果我将它增加 1，现在我们是 10，这将不起作用。

有人可以帮我吗？

我正在尝试实现一个类，该类将在给定元素数量和组合大小的情况下生成所有可能的无序 n 元组或组合。

换句话说，当调用这个时：

print() 是在构造函数中设置的回调函数。输出应该是：

这是我到目前为止所拥有的：

这是递归函数的实现，Start() 只是一个启动函数，具有更清晰的接口，它只调用 add_element(0)；

如果我想生成恒定 N 大小的所有可能组合，可以说大小为 3 的组合，我可以这样做：

如果 N 不是常数，则需要一个递归函数，通过在其自己的框架中执行每个 for 循环来模仿上述函数。当for循环终止时，程序返回到前一帧，也就是回溯。

我总是遇到递归问题，现在我需要将它与回溯结合起来以生成所有可能的组合。我在做什么错的任何指示？我应该做什么或我忽略了什么？

PS：这是一项大学作业，其中还包括对有序 n 元组做同样的事情。

提前致谢！

///////////////////////////////////////// /////////////////////////////////

只是想跟进正确的代码，以防万一其他人想知道同样的事情。

对于有序 n 元组的情况：

谢谢杰森的彻底回复！

我正在编写这个函数，我想用整数打印给定列表的所有子列表。这些整数的总和应该等于给定的数字n。还有一个i从值 0 开始的帮助变量。列表和每个子列表都是ArrayList. 所以这个方法现在看起来像这样：

当然我已经有了方法sum()。该方法现在执行此操作：假设numbers = [1, 3 , 4]and n == 4，那么该方法应该打印[4]and [1 ,3]，但它只打印[1, 3]? 我认为 for 循环必须做到这一点，对吗？如果有人让我走上正轨，我将不胜感激。

更新：我赋予该方法的值：

更新 2：

我忘了说我希望它是递归的:)

我正在审查本地编程竞赛中的一个编程问题。

您可以在此处下载问题(pdf)。它是荷兰语，但图片将有助于理解它。

您收到 am*m 网格作为输入，其中包含一些管道和一些缺失点（问号）。其余的管道必须放置在网格中，以便它们与其他管道连接。

每个管道都用一个字母表示（参见第 2 页的图片）。字母“A”的值为 1，“B”的值为 2，..

我尝试通过回溯来解决它（它还不太好用）。但是由于网格可以是 10x10，这将太慢。有人可以提出更好（更快）的解决方案/方法吗？

问题是使用递归以最少的颜色数为给定的图形着色，这样相邻的顶点就不能具有相同的颜色。函数签名是静态字符串穷举（int color，String prefix），其中颜色是正在使用的颜色数在该迭代中，前缀是由每个节点的颜色组成的字符串（例如，如果有 3 个节点，其中节点 0 用颜色 0 着色，节点 1 用颜色 1 着色，节点 2 用颜色 2 着色；然后前缀将是 012）。当所有节点都着色时，该函数返回字符串前缀。第一次调用是使用参数 (0,"") 进行的，这意味着尝试用 0 种颜色着色。这是我写的代码。对于少于 34 个节点，它工作正常并返回正确答案，但对于大于 34 个节点，该函数不会返回到主节点。任何改进代码的想法将不胜感激。如果需要更多信息，请告诉我。

令 T(x,y) 为 X × Y 网格上的旅行次数，使得：

1. 游览从左上角的广场开始
2. 巡回赛由上、下、左或右一格的移动组成，
3. 游览每个广场只访问一次，并且
4. 游览在左下角的广场结束。

很容易看出，例如，T(2,2) = 1, T(3,3) = 2, T(4,3) = 0 和 T(3,4) = 4。 编写一个程序计算 T(10,4)。

• 我已经为此工作了好几个小时......我需要一个程序，将网格的尺寸作为输入并返回可能的旅行次数？关于我应该如何解决这个问题的任何想法？

令 T(x,y) 为 X × Y 网格上的旅行次数，使得：

1. 游览从左上角的广场开始
2. 巡回赛由上、下、左或右一格的移动组成
3. 游览每个广场只访问一次，并且
4. 游览在左下角的广场结束。

很容易看出，例如，T(2,2) = 1, T(3,3) = 2, T(4,3) = 0 和 T(3,4) = 4。 编写一个程序计算 T(10,4)。

我已经为此工作了好几个小时......我需要一个程序，将网格的尺寸作为输入并返回可能的旅行次数？

我已经为此工作了好几个小时......我需要一个程序，将网格的尺寸作为输入并返回可能的旅行次数？

我写了这段代码来解决这个问题......我似乎无法弄清楚如何检查所有方向。

@KarolyHorvath 的算法您需要一些数据结构来表示网格上单元格的状态（已访问/未访问）。

你的算法：

并以 step(0, 0, sizex*sizey) 运行

我听说回溯可用于查找给定单词是否存在于二维字母矩阵中，但不知道如何实现它。例如，如果我们有一个像这样的矩阵：

规则是一个人可以从任何位置水平、垂直和对角移动，那么我们需要判断上面的矩阵是否包含“GONE”这个词。在这里，我们可以首先存储所有 G 的位置（如果存在 >1 G）并从每个位置开始检查，但是如何使用回溯进行检查？谢谢。

我想从用户开始使用我的应用程序时开始跟踪有关我的 android 应用程序使用情况的完整信息。

就像我想跟踪用户经历的所有活动以及他/她输入的数据一样。我想将这些数据作为屏幕截图或其他内容发送到我的服务器。

我的目标是找到跟踪所有这些并将其发送到服务器的方法..

请提出一些实施思路

提前致谢