标签: backtracking

考虑:

a c p r c 
x s o p c 
v o v n i 
w g f m n 
q a t i t

字母表i_index是相邻于另一个字母j_index在瓦片如果i_index毗邻j_index在任何下列位置中:

* * *
* x *
* * *

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

任务是在tile中找到给定的字符串.条件是给定字符串的所有字符应该是相邻的,并且可以不多次使用图块中的任何一个字符来构造给定字符串.

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

举一个例子:假设瓷砖有4x4填充了所有的 s,因此16 a,并且要查找的字符串是aaaaaaaaaaaaaa,即15 a和1 b.一个是消除字符串中没有出现的字符串.但仍然最坏的情况仍然可以出现说瓷砖有abababababababab和找到的字符串是abababababababbb.

我的尝试是这样的:

https://ideone.com/alUPf:

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX 5 …

嘿,我正在寻找一些帮助来找到一个算法,将一组正数分成k部分,这样每个部分都有(大约)相同的总和...让我们说我们有

1,2,3,4,5,6,7,8,9 zh k = 3算法应该像这样划分它1,2,3,4,5 | 6,7 | 8,9的顺序元素无法更改...找到一个贪婪的算法很容易,但我正在寻找一个总是返回最佳解决方案的回溯版本...

Annyone得到了什么提示？

我正在尝试编写一个算法,用Java或Javascript创建一个合法的数独板.既不工作,也不完全确定原因.

从本质上讲,两个程序中的问题是x或y的增加量超过它应该增加(跳过正方形).我不能为我的生活弄清楚这是怎么回事.如果需要,我可以提供完成JS解决方案的HTML.

我最好的猜测是它与我如何使用递归创建堆栈有关,但据我所知,它应该工作.在我的旧代码中有一个不正确的for循环,我知道这一点.我粘贴了一个旧版本,现在已经修好了.

Java的:

import java.util.*;

public class SudokuGenerator
{
//credit:cachao
//http://stackoverflow.com/questions/9959172/recursive-solution-to-sudoku-generator
public static final int BOARD_WIDTH = 9;
public static final int BOARD_HEIGHT = 9;

public SudokuGenerator() {
    board = new int[BOARD_WIDTH][BOARD_HEIGHT];
}
//Recursive method that attempts to place every number in a square
public int[][] nextBoard()
{
    nextBoard(0,0);
    return board;
}

public void nextBoard(int x, int y)
{
    int nextX = x;
    int nextY = y;
    //int[] toCheck = Collections.shuffle(Arrays.asList({1,2,3,4,5,6,7,8,9}));
    int[] toCheck = {1,2,3,4,5,6,7,8,9};
    Collections.shuffle(Arrays.asList(toCheck));

    for(int …

CLRS 似乎不包括反向跟踪/分支绑定。我在网上尝试了几个资源，虽然我明白了这些背后的想法，但我无法为背包问题编写代码。所以，我想要一些可以解决问题并用这 3 种方法解决它的东西，至少给出伪代码。或者您认为有用的任何资源。

我正在用Python实现一个PEG解析器生成器,到目前为止我已经取得了成功,除了"剪切"功能,其中任何人都知道Prolog必须知道的.

这个想法是在!解析了cut()符号之后,不应该在同一级别尝试替代选项.

expre = '(' ! list ')' | atom.

意味着在(看到之后,解析必须成功,或者在不尝试第二个选项的情况下失败.

我正在使用Python的(非常有效的)异常系统来强制回溯,所以我尝试了一个特殊的FailedCut例外,它将中止封闭的选择,但这不起作用.

任何指向如何在其他解析器生成器中实现此功能的指针都会有所帮助.

也许我遇到的问题是缺乏地方性.为规则的左侧部分生成的代码将类似于:

cut_seen = False
try:
    self.token('(')
    cut_seen = True 
    self.call('list')
    self.token(')')
except FailedParse as e:
    if cut_seen:
         raise FailedCut(e)
    raise

然后,为choice(|)运算符生成的代码将跳过以下选项,如果它捕获a FailedCut.我所说的缺乏地方性的意思是,捕捉的选择FailedCut可能会在通话中深入,因此产生的效果太难以辨别.

而不是为序列生成代码尝试通知封闭的切割选择,我可以让选择生成的代码提防它们.这会使剪辑的范围非常局部,与Prolog不同,但足以满足我在PEG解析器中的需求,即在看到某个令牌序列后提交选项,因此错误报告指的是该位置在源中,而不是可能已有其他选项的另一个位置.

我刚刚想到,如果为规则/谓词生成的代码捕获FailedCut并将其转换为正常FailedParse异常,则剪切将具有正确的范围.

在提到@false的问题时,这里是我想要工作的完整示例:

start = expre ;

expre = named | term ;

named = word ':' ! term;

term = word ;

在那个语法中,word可以通过named或者达到 …

我的数独求解方法存在问题.该计划的工作方式如下; 当电路板启动时,它是空的,用户在电路板上添加了几个数字,然后点击一个Solve按钮,程序试图解决它.如果我将相同的数字放在同一行中,一切正常.因此,如果用户添加1,1,0,0 ... 0.在拼图中它无法解决它,因为它的两个1彼此相邻并且将继续尝试找到一个沉闷,即使它是无法解决的难题.但是,如果它们都是0(空),它将立即解决它,就像Id在左上角放置1和2一样.如果我只是在其中放入一些随机数将检测到它无法解决(或者如果它是一个有效的谜题将解决它)

我正在考虑说什么theNumber == (row, col) equals thenNumber == (row+1, col),它应该return false是因为它是一个重复的数字.

这是我试图在solve方法中添加的代码,显然没有成功.

if ((puzzle.getNum(row, col) == a) == (puzzle.getNum(row + 1, col) == a)) {
   return false;
}

非常感谢帮助

我对搜索算法和回溯编程非常感兴趣.现在,我已经实现了算法X(请参阅我的其他帖子:确定无冲突集？)来解决确切的覆盖问题.这非常有效但我现在有兴趣用更基本的回溯变体来解决这个问题.我无法弄清楚如何做到这一点.问题描述与以前相同:

假设你有一堆集合,而每个集合都有几个子集.

Set1 = {(香蕉,菠萝,橙子),(苹果,羽衣甘蓝,黄瓜),(洋葱,大蒜)}

Set2 = {(香蕉,黄瓜,大蒜),(鳄梨,番茄)}

...

SetN = {...}

现在的目标是从每个集合中选择一个子集,而每个子集必须与任何其他所选子集无冲突(一个元素不包含在任何其他所选子集中).

作为一个例子,我写了两个Java类.集合由单个字符标识,元素是普通数字.

我特别有两个问题:

• 如何迭代所有集合/子集,以便可以使用启发式(选择具有最小元素的子集,最低成本,......)
• 如何维护选定的集+子集及其包含的元素.

我能找到的所有其他例子都是Sudoku或n-Queens,并且都使用固定的for循环.除此之外,我正在考虑一种相当普遍的方法,其中如果所选择的路径/集合可能与先前选择的子集/元素冲突,则可以使用函数"isPossiblePartialSolution"来检查.

以下是两个Java类:

import java.util.ArrayList;

public class Main {

public static void main(String[] args) {

    ArrayList<Set> allSets = buildRandomTest();

    for(Set r : allSets) {
        System.out.print("Set with id: " + r.id + " is subset in collection: " + r.name + " and contains: ");
        for(Integer n : r.listOfElements) {
            System.out.print(" " + n + " ");
        }
        System.out.println();
    }

}

public static …

任何人都可以解释,正则表达式引擎匹配的进程(aa)+\1反对aaaaaa？我知道当你使用时有一个叫做回溯的过程+,*但是我不确定它在这个例子中是如何工作的.

鉴于数据库中的以下事实:

foo(a, 3).
foo(b, 2).
foo(c, 4).
foo(d, 3).
foo(e, 2).
foo(f, 6).
foo(g, 3).
foo(h, 2).

我想收集所有具有最小第二个参数的第一个参数,加上第二个参数的值.第一次尝试:

find_min_1(Min, As) :-
    setof(B-A, foo(A, B), [Min-_|_]),
    findall(A, foo(A, Min), As).

?- find_min_1(Min, As).
Min = 2,
As = [b, e, h].

而不是setof/3,我可以使用aggregate/3:

find_min_2(Min, As) :-
    aggregate(min(B), A^foo(A, B), Min),
    findall(A, foo(A, Min), As).

?- find_min_2(Min, As).
Min = 2,
As = [b, e, h].

NB

如果我正在寻找最小数字,这只会给出相同的结果.如果涉及算术表达式,结果可能会有所不同.如果涉及非数字,aggregate(min(...), ...)将抛出错误!

或者,我可以使用完整的键排序列表:

find_min_3(Min, As) :-
    setof(B-A, foo(A, …

我正在尝试实施统一,但遇到问题......已经有很多例子,但他们所做的只是浑水.我比开明更困惑:

http://www.cs.trincoll.edu/~ram/cpsc352/notes/unification.html

https://www.doc.ic.ac.uk/~sgc/teaching/pre2012/v231/lecture8.html [以下代码基于此介绍]

http://www.cs.bham.ac.uk/research/projects/poplog/paradigms_lectures/lecture20.html#representing

https://norvig.com/unify-bug.pdf

如何在Java或C#等语言中实现统一算法？

Prolog的艺术......还有其他几个.最大的问题是我无法清楚地说明问题所在.更多的肮脏或lispy解释让我更加困惑.

作为一个良好的开端,遵循基于列表的表示似乎是个好主意(例如在lispy情况下),即:

pred(Var, val)  =becomes=> [pred, Var, val] 
p1(val1, p2(val2, Var1)) ==> [p1, val1, [p2, val2, Var1]]

除了你如何表示自己的名单!即[H | T]

我很乐意,如果你能告诉我一个Python伪代码和/或更详细的算法描述或指向一个.

我掌握的一些要点是需要在通用 - 统一和变量统一中分离代码,但后来我无法看到相互背叛的情况!... 等等.

作为旁注:我也很乐意提到你如何处理Backtracking上的统一.我认为我已经回归平方,但我知道在回溯时替换帧会发生一些事情.

添加了当前代码的答案.