标签: backtracking

假设我正在N-Queen通过回溯来解决问题(例如).如果我想找到唯一的(第一个)解决方案而不是全部解决方案,该怎么办？

我想我可以命令性地执行它(例如使用可变的布尔标志).我想知道我怎么能在功能上做到这一点.

我正在尝试编写一个算法,用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 …

我正在用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或者达到 …

假设以下程序:

nat(0).
nat(s(N)) :- nat(N).

/* 0+b=b */
plus(0,B,B) :- nat(B).
/* (a+1)+b = c iff a+(b+1)=c */
plus(s(A),B,C) :- plus(A,s(B),C).

它适用于添加两个数字,但是当我尝试查询以下类型时:

plus(Z,Z,s(0)).

它继续搜索可能的值Z很长时间后应该很明显没有解决方案(即Z>s(0))

我熟悉cut(!)运算符,我的直觉说解决方案与它有关,我只是不确定如何在这种情况下使用它.

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

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上的统一.我认为我已经回归平方,但我知道在回溯时替换帧会发生一些事情.

添加了当前代码的答案.

在反汇编函数时,gdb将在基数16中显示存储器地址,但在基数10中显示偏移量.

例:

(gdb) disassemble unregister_sysctl_table
Dump of assembler code for function unregister_sysctl_table:
   0x00037080 <+0>: push   %ebp
   0x00037081 <+1>: mov    %esp,%ebp
   0x00037083 <+3>: sub    $0x14,%esp
   0x00037086 <+6>: mov    %ebx,-0xc(%ebp)
   0x00037089 <+9>: mov    %esi,-0x8(%ebp)
   0x0003708c <+12>:mov    %eax,%ebx
   0x0003708e <+14>:mov    %edi,-0x4(%ebp)

函数偏移量是<+N>地址的旁边,正如您所看到的,它们位于基数10中.

当Linux内核崩溃时,它会显示使用base 16的回溯:

 [    0.524380]  [<c10381d5>] unregister_sysctl_table+0x65/0x70

将回溯地址从基数16转换为基数10以便能够找到所需指令是非常烦人的.

可以告诉gdb显示基本16偏移的反汇编输出吗？

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

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

码:

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

/* crude */

#define QUEEN 'Q'
#define BLANK '.'

int is_valid (char **board, int n, int a, int b)
{
  int i, j;

  for (i=0; i<n; i++)
  {
    if (board[a][i] == QUEEN)
      return 0;
    if (board[i][b] == QUEEN)
      return 0;
  }

  for (i=a, j=b; (i>=0) && (j>=0); i--, j--)
  {
    if (board[i][j] == QUEEN)
      return 0;
  }

  for (i=a, j=b; (i<n) && (j<n); i++, j++)
  {
    if (board[i][j] …

如何让SWI-Prolog解释器自动执行分号？由于回溯,我有很多结果(大约300个),我不想为所有这些都推分号.

我不想要所有解决方案的列表,我只是不想推分号或空格,所以我可以让程序在背景上打印回溯的解决方案.

问题如下:考虑三个输入A,B,C,找到一个带AND,OR和NOT门的布尔电路,使输出不是(A),不是(B),不是(C)最多使用2 NOT大门.

我想找一个带prolog的电路.我的想法是计算一个带有函数的谓词"可访问",并说它是否存在计算f的电路.

我有以下谓词:

not([],[]).
not([H|T],[G|S]) :- G #=# 1-H, not(T,S).

or([],[],[]).
or([0|T],[0|S],[0|R]) :- or(T,S,R).
or([1|T],[0|S],[1|R]) :- or(T,S,R).
or([1|T],[1|S],[1|R]) :- or(T,S,R).
or([0|T],[1|S],[1|R]) :- or(T,S,R).

and([],[],[]).
and([1|T],[1|S],[1|R]) :- and(T,S,R).
and([0|T],[1|S],[0|R]) :- and(T,S,R).
and([1|T],[0|S],[0|R]) :- and(T,S,R).
and([0|T],[0|S],[0|R]) :- and(T,S,R).

accessible(_,_,0) :- !,fail.
accessible([0,1,0,1,0,1,0,1],[12],_) :- !.
accessible([0,0,1,1,0,0,1,1],[11],_) :- !.
accessible([0,0,0,0,1,1,1,1],[10],_) :- !.
accessible(F,L,C) :- CC is C-1, or(G,H,F), accessible(G,M,CC), accessible(H,N,CC), L=[0, [M,N]].
accessible(F,L,C) :- CC is C-1, and(G,H,F), accessible(G,M,CC), accessible(H,N,CC), L=[1,[M,N]].
accessible(F,L,C) :- CC is C-1,  not(F,X), accessible(X,M,CC), L=[2,M].

我想计算11,12之间的函数xor,所以我尝试了以下目标:accessible([0,1,1,0,0,1,1,0],X,4).

但prolog运行了一段时间才得到了好的答案.我想知道如何改进程序以使其更快.

PS如何使用GNU prolog打印没有ASCII代码的字符串？

我想在缩进代码中搜索不以井号(#)开头的行.

目前,我正在使用^\s*([^\s#].*)带有多行选项的正则表达式.

我的问题是在非注释行上它完美地工作.

在注释行上,正则表达式引擎执行回溯,因为\s*从注释符号一直到行的开头,这有时会导致40或50个回溯步骤.

正则表达式完全适用于python代码.由于发动机引起的回溯,它效率不高.

关于如何避免它的任何想法？

奖励:有趣的是,正则表达式引擎无法识别它正在[^\s]逐个搜索\s*并导致这种回溯的事实.使重新发动机工作的挑战是什么？

奖励2:仅使用stdlib re模块.因为我无法添加第三方.(我在技术上使用sublime文本搜索,但想知道如何在Python中一般地使用它)