标签: backtracking

我正在尝试解决一个需要递归回溯的问题,我的解决方案会产生堆栈溢出错误.我知道这个错误通常表示终止条件不好,但我的终止条件似乎是正确的.除了可能导致堆栈溢出错误的错误终止条件之外还有什么吗？我怎么能弄清楚问题是什么？

编辑:抱歉试图发布代码,但它太丑了..

我正在c + +中实现DFS算法以找到生成树,使用算法DFS的生成树的输出总是预先排序或者它是纯粹的巧合吗？

我有以下数组:

steps=[
    {from:1, to:8},
    {from:1, to:2},
    {from:2, to:7},
    {from:7, to:9},
    {from:8, to:9}
];

这个数组描述了两点之间的连接.例如,从1到7,有一种方式1-> 2-> 7.

在JavaScript中如何生成例如从1到9的最短路径？

更新

function calc_route(start, end, data)
    {           
        console.log(start+", "+end);
        console.log(data);              
        for(var i=0; i<data.length; i++)
        {

            if(data[i].topoint == end && data[i].frompoint == start)
            {
                console.log("Return");                  
                console.log(data[i]);
                return data[i];
            }
            else
            {
                if(data[i].frompoint == start)
                {                       
                    calcfor =   data.splice(i, 1);                                      
                    calc_route(calcfor[0].topoint, end, data);
                }
            }
        }
    }

这是我到目前为止所做的,我的问题是如何保存路径？

我正在尝试编写一个只返回第一个可能解决方案的数独求解器.我设法用void方法打印所有可能的解决方案,但我不能停止第一次找到.

我知道首选的方法是切换到布尔方法并返回true树 - 但我找不到正确的方法来编写它.

我试过的任何方式总是给出编译错误(method must return boolean).

public boolean recursiveSolve(int line, int column) {
    if(line == N) // N is the board size (9)
        return true;
    // if Cell is not empty - continue
    if(board1.getCell(line, column) != 0) { 
        return nextCell(line, column);
    }
    // if Cell empty - solve
    else { 
        for(int i = 1; i <= N; i++) {
            board1.setCell(line, column, i); // set value to cell
            if(board1.boardIsOk())           // check if the board is …

我正在对一个字符串测试两个几乎相同的正则表达式(在regex101.com上),我注意到他们采取的步骤数量存在巨大差异.这是两个正则表达式:

(Stake: £)(\d+(?:\.\d+)?)

(winnings: £)(\d+(?:\.\d+)?)

这是我跑他们对字符串(带修饰符g,i,m,u):

开始游戏,信用:£200.00游戏数量:1,赌注:£2.00旋转卷轴:NINE SEVEN KINGKING STAR ACEQUEEN JACK KINGtotal奖金:£0.00End游戏,信用:£198开始......

_{旁注:字符串/正则表达式不是我的,我只是从SE的其他地方拿走它们,看到这种情况发生了.它与这个问题无关,但我认为它需要归因.}

(注意:Regex101似乎得到了PHP的PCRE正则表达式的支持."优化关闭"设置可能PCRE_NO_START_OPTIMIZE | PCRE_NO_AUTO_POSSESS.感谢Lucas Trzesniewski解决这个问题并编写一些C#代码来测试它.)

优化:第一个需要304个步骤来匹配,而第二个需要21个步骤.这是我想知道的巨大差异.

优化关闭:第一个需要333步才能匹配,而第二个需要317步.这将表明第一个模式未能优化,而不是第二个模式.

有趣的是,没有u修饰符,第一个模式(优化开启)只需要40步.(但它不会改变其他任何东西的表现,也不会改变正则表达式的最终匹配.)

我想知道regex101的优化引擎(PCRE)在步数方面造成了这种差异.我特别在寻找u启用nicode 时较长的正则表达式减少步数的原因.

有没有理由发生这种情况,或者这是引擎中的错误？

如果比较回溯,我会期望以下情况应该始终如此,对吧？除非它进入无限循环!

 ?- Y=2 , random:random(1,3,X), X =\= Y.
 Y = 2,
 X = 1.

 ?- Y=2 , random:random(1,3,X), X =\= Y.
 false. 

但我弄错了!一般来说,我的问题是为什么不比较回溯？

感谢所有的答案.我的困惑似乎主要来自于我对随机保持产生新随机数的期望,所以我觉得比较不是回溯,相反,原因是随机只做一次它然后失败.我不知道某些谓词的半确定性.但现在我可以留意了;)这样的情况.再次感谢.

通常在回溯中,我们采用一个辅助函数,它接受一个初始状态,每个递归调用负责自己的计算并将结果传递给下一个递归调用.从理论上讲,我们通过看不见和看到的变量来表示这一点.

例如,在字符串的排列中,我们将使用此程序:

def permute(str)
  return str if str.length < 2 
  permute_helper(str, "")
end 

def permute_helper(unseen, seen)
  #base case
  if unseen.length <= 0
    p seen
    return
  else 
    (0..unseen.length-1).each do |i|
      buffer = unseen 
      buffer = buffer.split('')
      buffer.delete_at(i)
      buffer = buffer.join('')
      permute_helper(buffer, seen+unseen[i])
    end 
  end
end 

permute('abc')

你会打印出所需的结果.

在最近的一次采访中,我被要求在不使用两个变量的情况下这样做.没有在看到的变量中存储状态.当时我无法全脑思考,但我想问一下如何在不存储状态的情况下进行回溯？

假设我有以下数独：

problem <- matrix(c(
    5, 3, 0, 0, 7, 0, 0, 0, 0,
    6, 0, 0, 1, 9, 5, 0, 0, 0,
    0, 9, 8, 0, 0, 0, 0, 6, 0,
    8, 0, 0, 0, 6, 0, 0, 0, 3,
    4, 0, 0, 8, 0, 3, 0, 0, 1,
    7, 0, 0, 0, 2, 0, 0, 0 ,6,
    0 ,6 ,0 ,0 ,0 ,0 ,2 ,8 ,0,
    0 ,0 ,0 ,4 ,1 ,9 ,0 ,0 ,5,
    0 ,0 ,0 ,0 …

我想测试我是否理解回溯，所以我尝试了骑士问题。但是我的代码似乎不起作用。它似乎做了一个无限循环，所以也许我对路径的跟踪没有很好地执行。所以我想知道我对这个问题的理解有什么遗漏。

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


#define N 8

int board[8][8]=  {

     -1,-1,-1,-1,-1,-1,-1,-1, //1
     -1,-1,-1,-1,-1,-1,-1,-1, //2
     -1,-1,-1,-1,-1,-1,-1,-1, //3
     -1,-1,-1,-1,-1,-1,-1,-1, //4
     -1,-1,-1,-1,-1,-1,-1,-1, //5
     -1,-1,-1,-1,-1,-1,-1,-1, //6
     -1,-1,-1,-1,-1,-1,-1,-1, //7
     -1,-1,-1,-1,-1,-1,-1,-1, //8


};

bool isSafe(int x, int y)
{
    return ( x >= 0 && x < N && y >= 0 &&
             y < N && board[x][y] == -1);
}

int SolveKnight_From_One_Point (int x,int y , int number_Moov) {

    if (number_Moov == N*N)
        return 1;

    if (isSafe(x,y)){
        board[x][y] = number_Moov;
        if (SolveKnight_From_One_Point(x-2,y+1,number_Moov+1)==1) …