在 Haskell 上实现回溯算法
我有一个在Haskell上进行回溯的问题，我知道如何编写递归函数，但在尝试获取多个解决方案或最佳解决方案（回溯）时遇到了麻烦。 有一个字符串列表，然后我需要获取从一个字符串到另一个字符串的解决方案，只改变一个字母。我会得到列表、第一个字符串和最后一个字符串。如果有解决方案，则返回它所用步骤的...
学习回溯法、分支定界和动态规划算法的好资源有哪些？
CLRS似乎没有涉及回溯/分支限界算法。虽然我尝试了几个在线资源，但我无法编写代码来解决例如背包问题这样的问题，尽管我理解了它们的理念。因此，我想要一个东西，可能需要使用这三种方法之一解决问题，并至少给出伪代码。或者任何您认为有帮助的资源。
在正则表达式中使用回溯比预期的更快。
根据 perlre 的说明，以下代码应该需要几秒钟才能执行完毕： $ time perl -E '$_="((()" . ("a") x 18; say "ok" if m{ \(([^()]+|\( [^()]* \))+\)}x;' real 0m0.006s user ...
从谓词中收集所有“最小”的解决方案
假设有以下这些数据库中的事实： foo(a, 3). foo(b, 2). foo(c, 4). foo(d, 3). foo(e, 2). foo(f, 6). foo(g, 3). foo(h, 2). 我希望收集所有第一个参数中，第二个参数最小的值，以及第二个参数的值。首先尝试： ...
使用回溯法求解最优权重子集和
我正在尝试解决一个问题。我有一些重量：[2,7,20,70,200,700]。给定一个输入，例如1507，它应该返回这些重量的最佳组合。在这种情况下，最佳组合应该是[700,200,200,200,200,7]。不幸的是，我的算法返回了[700, 700, 70, 20, 7, 2, 2, 2...
在递归下降解析器中实现"cut"
我正在使用Python实现PEG解析器生成器，在这方面我已经取得了一些成功，但是在“cut”功能上却遇到了问题，熟悉Prolog的人应该知道这个功能。 这个想法是，在解析到“cut”（!）符号后，就不应该尝试同一级别的其他备选项。 expre = '(' ! list ')' | atom...
使用启发式算法实现回溯搜索？
我对搜索算法和回溯编程非常感兴趣。目前，我已经实现了Algorithm X（请参见我在此处的其他帖子：确定无冲突集合？），以解决精确覆盖问题。这很有效，但我现在更想用一种更基本的回溯变体来解决这个问题。我只是想不出如何实现。问题描述与之前相同： 假设您有一堆集合，每个集合都有几个子集。 S...
如何使这个正则表达式不会导致“灾难性回溯”？
我正在尝试使用从http://daringfireball.net/2010/07/improved_regex_for_matching_urls获取的URL匹配正则表达式。 (?xi) \b ( # Capture 1: entire matc...
确定数独是否有唯一解
我正在努力研究一种回溯算法，以确定数独是否具有唯一的解决方案，或者它是否具有多个解决方案。以下是我使用的回溯代码： static boolean solve(int i, int j, int[][] cells) { if (i == 9) { i = 0;...
当我的正则表达式执行且无法匹配输入时，浏览器选项卡会卡住。
问题是这样的。我创建了一个带有验证的输入字段，这是有效数据： 1-12、14、16、22、25-35、41、49、55-90 1230-1992、2001-2099、9931 1-2 13 1、3、4、5、6、10 全部 基本上，任何这些数字的组合（范围、逗号分隔的范围、逗号分隔的数字...