问题标签 [backtracking]

这是我写的代码。

一点解释。我使用 int [8][8] 来表示棋盘，最初我在棋盘的每个方格中输入数字 -1。

当骑士移动时，它用计数器（int counter）标记他访问的方格，然后从那里（以及骑士可以采取的所有合法移动）进行递归调用以找到路径（目标是每个方格只访问一次）。

一旦计数器达到 64，该函数bool knighttour(square start,int &counter,int cb[][8]) 必须返回 true，然后主程序应该显示“骑士之旅”，因为它在 [8][8] 棋盘上被标记。

我相信我提供的上述代码在无限循环上运行。我让它运行了 3 分钟。

我想使用回溯来搜索允许可变长度匹配的长字符串中的所有子字符串——即允许最大给定数量的不匹配、插入和删除的匹配。我找不到任何有用的例子。我找到的最接近的是这里的这篇论文，但这非常复杂。任何人？

干杯，

马丁

考虑：

如果在以下任何位置相邻，i_index则字母与拼贴中的另一个字母相邻：j_indexi_indexj_index

这里所有的都*表示与 相邻的位置x。

任务是在图块中找到给定的字符串。条件是给定字符串的所有字符都应该是相邻的，并且拼贴中的任何一个字符都不能被多次使用来构造给定字符串。

我想出了一个简单的回溯解决方案，解决方案非常快，但最坏的情况时间真的更糟。

举个例子：假设瓷砖有 4x4 填充了所有a，因此是 16 个a，要查找的字符串是aaaaaaaaaaaaaaaab，即 15个 a和一个b。一种是消除带有未出现在图块中的字符的字符串。但是仍然会出现最坏的情况，例如瓷砖有ababababababababab并且要查找的字符串是abababababababbb。

我的尝试是这样的：

https://ideone.com/alUPf：

打印：

该函数sp完成工作，执行回溯。

有没有更好的办法 ？或者是否有可能降低最坏情况的时间？

在为 n-Queen 问题的所有可能解决方案实施算法时，我发现许多分支都达到了相同的解决方案。有没有什么好方法可以为 n-Queens 问题生成每个独特的解决方案？如何避免不同分支产生的重复解决方案（存储和比较除外）？

这是我尝试过的第一个解决方案： http ://www.ideone.com/hDpr3

代码：

为了生成所有可能的解决方案，我使用了相同的代码nqdfs_all ()函数，但没有将控件返回给父级，而是继续枚举和检查。调用此函数会显示不同分支达到的重复结果。

我目前正在研究递归回溯这个美丽的话题。我已经尝试过经典的例子，比如找到迷宫中的最短路径，或者 n-queens 问题。但是我现在正在处理的问题确实让我感到困惑：实际上，我认为解决一个简单的拼图游戏可能是一个简单的练习：我有一块大小为 n = a * b 的板，正好有这么多（ n) 件。
最后，我想让所有的棋子按照一定的顺序放在板上，它们遵守一定的限制（比如匹配他们的邻居）。相当容易，我想，我想出了以下算法：

基本上，这个算法做了它应该做的——但不幸的是它只适用于“小”板尺寸（n < 100）。因为如果我有一个像 10 x 10 正方形和 100 块的板，那么函数搜索和搜索直到 JVM 由于堆空间不足而崩溃时才结束。我什至尝试将 eclipse 的内存大小限制设置为 1.2g，这使得函数工作时间更长，但仍然不够。

所以我的问题是：是否可以优化上述算法以使其适用于 n > 100 的电路板尺寸？我究竟做错了什么？还是我采取了完全错误的方法？

非常感谢您提前提供的帮助。

这是我第一次在低级课程中将递归作为作业处理。我浏览了互联网，似乎找不到任何人使用与我想出的方法类似的方法（这可能说明了为什么这不起作用）。该错误是一个分段错误std::__copy_move...，我假设它是 c++ STL 中的某些内容。任何人，我的代码如下：

一段时间以来，我一直在试图解决这个问题，但我似乎无法弄清楚出了什么问题。任何建议都非常感谢！:)

我需要能够计算两个城市之间的最小距离，给定一个包含城市对之间距离的表格。两个城市可能不直接连接，而是通过第三个城市连接，依此类推。

这是我的表

和

我不知道在 pl/sql 中递归和回溯是如何工作的。

我无法弄清楚如何在不使用递归而是回溯的情况下从字符串列表中访问单个字符。

例如，我有这个字符串列表，我希望能够从这些字符串之一返回单个字符（'。''o'，'*'）。我正在处理的程序将其视为行和列。这是我的数据库中的一个事实，如下所示：

我有谓词：

它采用行号和列号（索引从 1 开始）并返回该特定行和列的条目 (TheEntry)。

我有一种感觉，我的谓词头可能没有正确构建，但我真的更专注于如何逐个字符地遍历列表中的每个字符串而不递归并返回它。

我是 prolog 的新手，对此我有很大的困难。

任何帮助将不胜感激！

谢谢！

我正在制作 ACM 竞赛的问题，以确定具有无向图 G 和属于每个组件的顶点的连接组件的数量。已经完成了 DFS 算法，计算了无向图的连接组件的数量（问题的难点），但我想不出任何东西来指示属于每个组件的节点或有节点的记录。

输入：第一行输入一个整数C，表示测试用例的个数。每个测试用例的第一行包含两个整数 N 和 E，其中 N 表示图中的节点数，E 表示图中的边数。然后沿着 E 行，每行有 2 个整数 I 和 J，其中 I 和 J 表示节点 I 和节点 J 之间存在一条边 (0 ≤ I, J

输出：在每个测试用例的第一行必须显示以下字符串“Case G: P component (s) connected (s)”，其中 G 表示测试用例的数量（从 1 开始），P 表示连接的组件数量在图中。然后是 X 行，每行包含属于连接组件的节点（按从小到大的顺序），由空格分隔。每个测试用例之后应该打印一个空行。输出应该写在“output.out”中。

例子：

输入：

输出：

这是我的代码：

我对如何携带属于每个连接组件或结构的节点的内存应该用来存储，我应该如何修改我的代码来做到这一点有疑问？我想听听建议，想法或伪代码中的任何实现。谢谢大家

我为我在上一篇文章中指定的问题实施了基于回溯的解决方案：将物品打包到固定数量的箱子中

（Bin 是一个简单的数据类型包装器，vector<int>带有 sum() 等附加方法）

尽管该算法运行速度很快，但对于大型数据集很容易出现堆栈溢出。

我正在寻找如何改进它的任何想法和建议。

编辑：

我决定尝试使用显式堆栈的迭代方法，但我的解决方案没有按预期工作 - 有时它会给出不正确的结果。

任何建议都受到高度赞赏。