标签: backtracking

给定一个图像和一组标签附加到图像上的特定点,我正在寻找一种算法,以一定的约束将标签布局到图像的两侧(每侧标签大致相同,标签大致等距离,将标签连接到各自的点,没有线交叉的线.

现在,通过按Y坐标(它们所指的点)对标签进行排序,通常可以非常天真地找到近似解决方案,如本例所示(仅限概念证明,请忽略实际数据的准确度等)!

现在为了满足没有过境的条件,我想到了一些想法:

• 使用遗传算法找到没有交叉的标签的排序;
• 使用另一种方法(例如动态编程算法)来搜索这样的排序;
• 使用上述算法之一,允许间距和排序的变化,找到最小化交叉数和从均匀间距变化的解决方案;
• 也许有一些标准我可以用来在某些标准内粗略搜索标签的每个可能的排序(如果它们的距离大于X,不要重新排序两个标签);
• 如果所有其他方法都失败了,只需尝试数百万的随机排序/间距偏移,并选择一个给出最小交叉/间距变化的偏移量.(优点:直接进行编程,可能会找到一个足够好的解决方案;虽然不是一个显示停止的轻微劣势:也许不能在应用程序中动态运行它,以允许用户更改图像的布局/大小. )

在我开始其中之一之前,我会欢迎其他人的意见:有其他人遇到过类似问题并有任何信息来报告上述任何方法的成功/失败,或者他们是否有更好的/更简单的解决方案,我没有发生？感谢您的输入!

给定长度为N的字符串S，返回一个字符串，该字符串是将'?'字符串S中的每个字符替换为一个'a'或一个'b'字符的结果，并且不包含三个相同的连续字母（换句话说，处理后的字符串中'aaa'不可能'bbb'出现这两个字母）。

例子：

Given S="a?bb", output= "aabb"

Given S="??abb", output= "ababb" or "bbabb" or "baabb"

Given S="a?b?aa", output= "aabbaa"

1<=n<=500000

我使用回溯解决了这个问题，但是我的解决方案很慢并且不适用于更大的 N 值，有更好的方法吗？

我正在用Java编写一个用于9x9网格的数独求解器.

我有方法:

• 打印网格

• 用给定的值初始化电路板

• 测试冲突(如果相同的数字在同一行或3x3子网格中)

• 一种逐个放置数字的方法,这需要最多的工作.

在我详细介绍该方法之前,请记住我必须使用递归来解决它,以及回溯(在这里观看applet作为示例http://www.heimetli.ch/ffh/simplifiedsudoku.html)

此外,我正在通过垂直向下移动来解决这个数独,从左上角开始,到第一列,然后到第二列,等等.

到目前为止,我有以下内容:

public boolean placeNumber(int column){

    if (column == SUDOKU_SIZE){  // we have went through all the columns, game is over

        return true;

    }

    else
    {
        int row=0;  //takes you to the top of the row each time

        while (row < SUDOKU_SIZE)    loops through the column downwards, one by one
        {

            if (puzzle[row][column]==0){  //skips any entries already in there (the given values)

                puzzle[row][column]=1;   //starts with one

                while(conflictsTest(row,column)){   //conflictsTest is the method …

最近,我在Haskell中实现了一个天真的DPLL Sat解算器,改编自John Harrison的实用逻辑和自动推理手册.

DPLL是各种回溯搜索的,所以想要使用所述实验逻辑单子从奥列格Kiselyov等.但是,我真的不明白我需要改变什么.

这是我得到的代码.

• 使用Logic monad需要更改哪些代码？
• 额外奖励:使用Logic monad有什么具体的性能优势吗？

{-# LANGUAGE MonadComprehensions #-}
module DPLL where
import Prelude hiding (foldr)
import Control.Monad (join,mplus,mzero,guard,msum)
import Data.Set.Monad (Set, (\\), member, partition, toList, foldr)
import Data.Maybe (listToMaybe)

-- "Literal" propositions are either true or false
data Lit p = T p | F p deriving (Show,Ord,Eq)

neg :: Lit p -> Lit p
neg (T p) = F p
neg (F p) …

我从各种在线编码论坛中发现,有一种叫做"AC"的技术,看起来像"动态编程"或"后退跟踪",但不知道它是如何使用的.

有人有建议吗？

谢谢Joni:按照他/她的说法,它是"接受".现在它更有意义.

如何计算这些回溯算法的时间复杂度,它们是否具有相同的时间复杂度？如果不同怎么样？请详细解释并感谢您的帮助.

1. Hamiltonian cycle:

        bool hamCycleUtil(bool graph[V][V], int path[], int pos) {
            /* base case: If all vertices are included in Hamiltonian Cycle */
            if (pos == V) {
                // And if there is an edge from the last included vertex to the
                // first vertex
                if ( graph[ path[pos-1] ][ path[0] ] == 1 )
                    return true;
                else
                    return false;
            }

            // Try different vertices as a next candidate in Hamiltonian Cycle.
            // We don't try for 0 as …

我正在通过两个单独的调试工具调试^(A+)*B一个字符串上的正则表达式AAAC(例如来自rexegg.com):我有权访问:

1. regex101.com
2. RegexBuddy v4

以下是结果(左侧的regex101):

我的问题主要不在于对我来说同样重要的步骤数量,而是回溯的方式.为什么我们看到差异？(regex101使用PCRE lib并且我将RegexBuddy lib设置为相同)

全面的逐步解释对我有利.

我使用Backtracking方法在c ++中编写骑士游览算法.但它似乎太慢或陷入无限循环n> 7(大于7乘7棋盘).

问题是:该算法的时间复杂度是多少？如何优化它？!

骑士之旅的问题可以说明如下:

给定一个有n×n方格的棋盘,找到一个骑士的路径,每个方格只访问一次.

这是我的代码:

#include <iostream>
#include <iomanip>
using namespace std;

int counter = 1;
class horse
{
public:
  horse(int);
  bool backtrack(int, int);
  void print();
private:
  int size;
  int arr[8][8];
  void mark(int &);
  void unmark(int &);
  bool unvisited(int &);
};

horse::horse(int s)
{
  int i, j;
  size = s;
  for(i = 0; i <= s - 1; i++)
    for(j = 0; j <= s - 1; j++)
      arr[i][j] = 0;
} …

回溯和递归有什么区别？这个程序如何运作？

void generate_all(int n)
 {
    if(n<1) printf("%s\n", ar);
    else{
            ar[n-1]='0';        //fix (n)th bit as '0'
            generate_all(n-1);  //generate all combinations for other n-1 positions.
            ar[n-1]='1';        //fix (n)th bit as '1'
            generate_all(n-1);  //generate all combinations for other n-1 positions.
    }

我一直在寻找几个小时,但还没有为这种拼图找到一个完全可行的解决方案.所以我跟主教跟着类似的问题.

我需要做的是以这样的方式在棋盘上放置12个骑士,使得棋盘的所有自由方格都被至少一件攻击.

最终结果应如下所示:

问题是 我的程序只尝试与最后两个部分的不同组合,然后以某种方式崩溃. EDITED

到目前为止我做了什么:

#include <iostream>
using namespace std;
#define N 8

void fillChessBoard(int (&chessBoard)[N][N], int num);
void printChessBoard(int (&chessBoard)[N][N]);
void removeKnight(int (&chessBoard)[N][N], int i, int j);
void placeKnight(int (&chessBoard)[N][N], int i, int j);
bool allSpaceDominated(int (&chessBoard)[N][N]);
bool backtracking(int (&chessBoard)[N][N], int pos);

int main()
{
    int chessBoard[N][N];

    fillChessBoard(chessBoard, 0);
    backtracking(chessBoard, 0);

    return 0;
}

bool backtracking(int (&chessBoard)[N][N], int knightNum)
{
    if(knightNum==12)
    {
        if(allSpaceDominated(chessBoard))
        {
            printChessBoard(chessBoard);
            return true;
        }
        else return false;
    }
    else
    {
        for(int i=0; i<N; …