标签: backtracking

当为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] …

有没有办法在Scala中定义stream一个backtracking算法？

例如,以下backtracking算法打印给定大小的所有"二进制"字符串.

def binaries(s:String, n:Int) {
  if (s.size == n)
    println(s)
  else {
    binaries(s + '0', n)
    binaries(s + '1', n)
  }
}

我相信我可以stream使用另一种迭代算法定义一个给定大小的"二进制"字符串.不过我想知道我是否可以将上面的回溯算法转换为stream.

我是ANTLR的新手.我有一个非常简单的语法:

start   :
('A' 'B' 'C' '1'
|'A' 'B' 'C' '2' 
|'A' 'B' 'C' '3'
)
;

我认为我已经理解了前瞻和后退概念的基础知识(它与句法谓词一起使用).所以这个语法适用于k = 4或backtrack = true.但究竟是什么区别,主要问题是我何时使用什么？我试图在互联网上找到答案,但没有成功.

我正在尝试编写一个函数来查找产生指定金额的所有可能的硬币组合,例如它计算所有可能的方式来从1p,2p,5p,10p的面额列表中更改2英镑的金额, 20P,50P,1pound,2pound.我坚持这个,找不到合适的解决方案.

我希望main函数是递归的,因为我想更好地理解递归.该算法必须回溯,如果在某个时刻发现的组合超过了要匹配的量,则程序应该返回到先前的步骤并从不同的点开始.

到目前为止,我已经编写了一个普通(非递归)函数,如果每个硬币仅使用一次,则计算给定国家中所有可能的硬币组合(这相当简单).我并没有试图找到一个给定数额的正确组合,只是所有可能的硬币组合.

def calcCoins(coins):
    """ 
    returns all possible combinations of coins, when called with 
    [1,2,5,10,20,50,100,200] returns a list of 126 Counters containing 
    for instance Counter{1:1}, Counter{1:1,2:1,5:1}, Counter {50:1,100:1} etc
    """
    i,combs = 1, []
    while i < len(coins):
        for x in combinations(coins,i):
            combs.append(Counter(x))
        i += 1
    return combs

现在我有一个笨拙的递归函数,它接受一个组合和所需的数量作为参数,并返回所有可能的方式,其中可以给出等于此数量的更改.

def findSum(comb,goal,rightOnes):
    if rightOnes == None:
        rightOnes = []
    if sum(comb.elements()) == goal:
        comb_ = Counter(comb)
        if comb_ in rightOnes:
             # probably a cycle, return combinations gathered and exit …

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

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

我目前正在学习一些面试,并遇到了一些完全困扰我的算法问题.我想知道你是否有人可以帮助解释解决这个示例问题的策略或可能提供任何伪代码.

谢谢你!

问题:您是一名自由职业承包商,您的可用工作每周都会发生变化.这些工作分为两组,ls和hs.如果你从hs选择一份工作,你必须事先准备一周,不做任何工作.Ls工作不需要这样的准备.

确定最佳工作计划,给定两个大小为n的阵列l和h,其中n是周数.

所以根据我的理解,给出一个表格如下:

???????????????????????????????????
?   ?  ? 0  ? 1  ? 2  ?  3  ?  4  ?
???????????????????????????????????
? l ?  ? 30 ?  5 ? 20 ?  25 ? 500 ?
? h ?  ?  0 ? 50 ? 70 ? 100 ? 110 ?
???????????????????????????????????

最佳路径是NHNHL,奖励为650.但我很难知道如何在一个紧凑的高效算法中做到这一点.

问题如下:考虑三个输入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代码的字符串？

在有向图中,我们正在寻找具有最低平均边权重的周期.例如,具有节点1和2的图表具有从长度2的1到2和长度4的2到1的路径将具有3的最小平均周期.

不是寻找复杂的方法(Karp),而是通过修剪解决方案进行简单的回溯.当当前运行平均值大于最佳找到的平均重量循环成本时,给出了解释为"具有重要修剪回溯的可解决方案".

但是,为什么这种方法有效呢？如果我们在一个周期的中途并且重量超过最佳找到的平均值,那么在重量较小的边缘我们是否可能达到我们当前周期可能低于最佳平均值的情况？

编辑:以下是一个示例问题:http://uva.onlinejudge.org/index.php？option = onlinejudge&page = show_problem & problem = 2031

我给出了像这样的等式:

n = 7
1 + 1 - 4 - 4 - 4 - 2 - 2

如何以最佳方式替换运算符,使方程的总和等于零,或打印   -1.我想到了一种算法,但它不是最优的.我有一个想法,强调所有案件的复杂性O(n*2^n),但是(n < 300).

以下是问题的链接:http://codeforces.com/gym/100989/problem/M.

input:
max_weight = 550
n = 4
x_i = [120, 175, 250, 150]

output:
2  
// [[250, 175, 120], [150]]

我最初的印象是,这看起来非常类似于动态编程硬币更换/背包问题,但它不是硬币更换(这将要求最少数量的重量来制作精确数量),而且它不是背包(重量没有值,就像我可以有超过1背包).

这个问题有一个共同的名称/解决方案吗？